큐 (자료 구조)

3. 종류

큐에는 선형과 환형이 있다.^[1] 이론적으로 큐는 특정 용량이 정해져 있지 않아, 이미 포함된 요소의 수에 관계없이 항상 새 요소를 추가할 수 있다. 또한, 큐가 비어 있을 수도 있는데, 이 경우에는 새 요소를 다시 추가하기 전까지는 요소를 제거할 수 없다.

배열을 닫힌 원 형태로 만들고, 머리(head)와 꼬리(tail)가 그 원 안에서 끊임없이 이동하도록 하는 방식으로 큐를 구현할 수 있다. 이 방법은 고급 프로그래밍 언어에서 큐를 구성하는 개념적으로 가장 간단한 방법 중 하나이다. 제한된 큐는 고정된 수의 항목으로 제한된 큐이다.^[1]

FIFO 큐를 효율적으로 구현하는 방법에는 여러 가지가 있다. 효율적인 구현은 큐에 요소를 추가(en-queue)하거나 제거(de-queue)하는 작업을 O(1) 시간에 수행할 수 있는 구현이다.

• 연결 리스트
• 이중 연결 리스트는 양쪽 끝에서 O(1) 시간 안에 삽입 및 삭제가 가능하므로 큐를 구현하기에 적합하다.
• 일반적인 단일 연결 리스트는 한쪽 끝에서만 효율적인 삽입 및 삭제가 가능하다. 그러나 첫 번째 노드 외에 '마지막' 노드를 가리키는 포인터를 추가하면 효율적인 큐를 구현할 수 있다.
• 수정된 동적 배열을 사용하여 구현된 양방향 큐

3. 1. 선형 큐 (Linear Queue)

| style="vertical-align:middle;" |

| style="vertical-align:middle;" |

| style="vertical-align:middle;" |

| style="vertical-align:middle;" |

| style="vertical-align:middle;" |

|}

3. 2. 환형 큐 (Circular Queue)

|-

| 2 || ENQ(B)

|-

| colspan="2" |

|-

| 3 || ENQ(C)

|-

| colspan="2" |

|-

| 4 || ENQ(D)

|-

| colspan="2" |

|-

| 5 || DEQ(A)

|-

| colspan="2" |

|-

| 6 || ENQ(E)

|-

| colspan="2" |

|}

4. 구현

큐는 데크의 특수한 경우로 간주되어 별도로 구현되지 않거나, 자료형으로 구현될 수 있다. 예를 들어, Perl과 Ruby에서는 배열의 양쪽 끝에서 요소를 추가하고 제거하는 기능을 제공하여, `push`와 `shift` 함수 (또는 `unshift`와 `pop`)를 통해 큐처럼 사용할 수 있다.^[2]

C++의 표준 템플릿 라이브러리는 `queue` 템플릿 클래스를 제공하며, 이는 푸시/팝 연산만 허용한다. Java 라이브러리는 `Queue` 인터페이스를 포함하며, `LinkedList`와 `ArrayDeque` 등의 구현 클래스를 제공한다. PHP에는 `SplQueue` 클래스와 함께 beanstalk'd, Gearman과 같은 외부 라이브러리를 활용할 수 있다.

4. 1. 배열 기반 구현

4. 2. 연결 리스트 기반 구현 (Linked Queue)

• 연결 리스트
• 이중 연결 리스트는 양쪽 끝에서 O(1) 삽입 및 삭제가 가능하므로 큐 구현에 적합하다.
• 일반 단일 연결 리스트는 한쪽 끝에서만 효율적인 삽입 및 삭제가 가능하다. 그러나 첫 번째 노드뿐만 아니라 ''마지막'' 노드를 가리키는 포인터를 추가하면 효율적인 큐를 구현할 수 있다.

5. 우선순위 큐 (Priority Queue)

우선순위 큐는 큐에 추가하는 요소에 우선순위를 부여하고, 우선순위에 따라 큐 내에서 정렬하는 것이다. 속도 향상을 위한 다양한 알고리즘이 연구되고 있으며, 또한 여러 다른 알고리즘에서 간접적으로 사용된다.

6. 큐의 응용

• 메시지 큐: 컴퓨터 시스템 내에서 프로세스 간 통신(IPC)에 사용되는 메시지를 저장하는 큐이다.^[1]
• UNIX에서는 `msgsnd` 및 msgrcv 시스템 콜을 통해 데이터를 송수신할 수 있다. 데이터를 전송하는 대상은 동일한 프로세스일 수도 있고, 다른 프로세스일 수도 있다.
• Microsoft Windows에서는 이벤트 루프를 가진 스레드 또는 프로세스에 이벤트를 전송하는 데 사용되어, 이벤트 구동 프로그래밍을 실현한다. 특히 GUI 애플리케이션에서 필수적이며, 프로그램은 수신한 이벤트 메시지를 하나씩 메시지 루프 내에서 가져와서 적절한 프로시저(이벤트 핸들러)에 배포하고, 이벤트에 대응하는 동작을 실행한다. 메시지 정보는 MSG구조체에 의한 인터페이스를 통해 제공된다.
• 명령 큐: 소프트웨어나 하드웨어에 여러 명령을 전송하여 비동기적으로 실행하기 위한 큐이다.^[1]
• 예를 들어 그래픽 하드웨어 (GPU)와의 양방향 통신에는 시간이 걸리므로, 처리량을 향상시키기 위해 대부분의 그리기 명령은 응답이 필요 없는 단방향 형식이 되어, 일단 명령 큐에 큐잉되어, 일괄적으로 비동기적으로 배치 처리된다.
• 명령 큐는 하드웨어에 가까운 장치 드라이버 계층에서 구현되어 있으며, 상위 레벨의 API나 미들웨어를 이용하는 애플리케이션 계층에서는 의식하지 않아도 될 때도 있지만, 하위 레벨의 API에서는 미들웨어나 애플리케이션 측에서 명시적으로 명령 큐를 이용하기도 한다.
• 태스크 큐: 워커 스레드 또는 서비스 프로세스에 위임하는 처리를 일시적으로 저장해두기 위한 큐이다.^[1]

7. 큐 머신 (Queue Machine)

큐 머신은 중간 결과를 저장하기 위해 큐를 사용하는 계산 모델이다.

연산은 큐에 저장된 데이터를 사용하여 수행되며, 결과는 다시 큐에 저장된다. 따라서 스택 머신과 마찬가지로 0-주소 명령어 형식을 사용할 수 있다.

또한, 큐 머신은 데이터 흐름에 따라 명령을 실행하는 특징을 가진다.

8. 프로그래밍 언어 지원

다양한 프로그래밍 언어에서 큐 자료 구조를 지원하거나 큐와 유사한 기능을 제공한다.

• C++의 표준 템플릿 라이브러리는 "queue" 템플릿 클래스를 제공하며, 이 클래스는 푸시(push) 및 팝(pop) 연산으로 제한된다.
• Java의 라이브러리(J2SE5.0부터)는 큐 연산을 지정하는 인터페이스를 포함한다. 구현 클래스에는 LinkedList와 (J2SE 1.6부터) ArrayDeque가 있다.
• PHP에는 [http://www.php.net/manual/en/class.splqueue.php SplQueue] 클래스가 있으며, beanstalk'd 및 Gearman과 같은 타사 라이브러리도 있다.
• Perl과 Ruby는 배열의 양쪽 끝에서 푸시와 팝을 허용하므로, '''push'''와 '''shift''' 함수를 사용하여 목록을 큐에 넣고 빼낼 수 있다(또는 반대로 '''unshift'''와 '''pop'''을 사용할 수 있다).^[2]

참조

_[1] 웹사이트 Queue (Java Platform SE 7) http://docs.oracle.c[...] Docs.oracle.com 2014-05-22
_[2] 웹사이트 Array (Ruby 3.1) https://ruby-doc.org[...] 2022-05-11
_[3] 웹사이트 Purely Functional Data Structures https://doc.lagout.o[...]
_[4] 논문 Real-time queue operations in pure Lisp 1981-11
_[5] 문서 FIFO
_[6] 문서 enqueue
_[7] 문서 dequeue
_[8] 문서 double-ended queue
_[9] 문서 LIFO
_[10] Microsoft Docs MSG (winuser.h) - Win32 apps https://docs.microso[...]
_[11] Microsoft Docs Design Philosophy of Command Queues and Command Lists - Win32 apps https://docs.microso[...]
_[12] Microsoft Docs Queue サービスを作成する https://docs.microso[...]