Queue

• Queue는 FIFO (First In, First Out) 원칙을 따르는 선형 자료구조입니다.
• 가장 먼저 들어온 요소가 가장 먼저 나가는 구조입니다.
• 은행에서 번호표를 뽑고 자신의 순서를 기다리는 모습, 마트에서 계산하기 위해 줄을 서는 모습에서 “대기줄”을 의미하는 Queue를 찾아볼 수 있습니다.

Queue의 주요 연산

• Enqueue : Queue의 맨 뒤에 원소를 추가하는 연산입니다. $O(1)$
• Dequeue : Queue의 맨 앞에 있는 원소를 제거하고 반환하는 연산입니다. $O(1)$
• Peek : Queue의 맨 앞에 있는 원소를 확인합니다. $O(1)$
• IsEmpty : Queue가 비어 있는지 확인합니다. $O(1)$

사용 상황

OS CPU Scheduling

운영 체제에서는 다양한 프로세스가 동시에 실행될 수 있도록 스케줄링을 합니다. Scheduling에서 사용되는 큐는 정확하게는 Priority Queue입니다. 우선순위 큐는 이러한 작업 스케줄링에서 우선순위에 따라 프로세스를 관리하고 CPU에 할당하는 순서를 결정하는 데 사용됩니다.

여기서 P1, P2, P3은 프로세스들이며, P1이 현재 CPU에 할당된 상태입니다. P2는 다음에 실행될 프로세스입니다.

[ P1 ] -> [ P2 ] -> [ P3 ]  (Queue)
CPU <--- (Front of the Queue)

프린터 대기열

여러 문서나 파일을 프린트할 때, 먼저 요청된 작업부터 순차적으로 프린트하기 위해 Queue가 사용됩니다.

Breadth-First Search

너비 우선 탐색에서는 시작 노드부터 시작하여 그 노드의 모든 이웃을 먼저 탐색합니다. 큐는 이런 방식으로 노드를 순차적으로 저장하고 처리하는 데 사용됩니다.

이 그림에서 A부터 시작하여 B, C, D 순으로 큐에 추가하고, 순차적으로 탐색합니다.

             A
           / | \
          B  C  D
         / \
        E   F
        
Queue: [A] -> [B] -> [C] -> [D] -> [E] -> [F]

주문 처리 시스템

전자상거래 시스템에서 사용자의 주문은 순서대로 처리되어야 합니다. 주문이 들어올 때마다 큐에 추가되고, 백엔드 시스템은 큐에서 순차적으로 주문을 처리합니다.

첫 번째 주문(Order1)이 현재 처리 중이고, 그 다음에는 Order2, Order3 순서로 처리됩니다.

Order Queue: [ Order1 ] -> [ Order2 ] -> [ Order3 ]
             (First In)                   (Last In)

Data Streaming

실시간 데이터 스트리밍 시스템에서는 데이터 패킷을 순서대로 처리해야 합니다. 이 때, 큐를 사용하여 패킷들을 순차적으로 정리하고 처리할 수 있습니다.

Packet1이 먼저 처리되며, 그 후 Packet2, Packet3 순서로 처리됩니다.

Packet Queue: [ Packet1 ] -> [ Packet2 ] -> [ Packet3 ]
               (First In)                   (Last In)

Load Balancing

큐를 사용하여 들어온 요청을 여러 서버에 공평하게 분배합니다. 이를 통해 서버의 부하를 균등하게 분산시킬 수 있습니다. 각 요청(Req)이 큐에 들어가고, 서버들에 순차적으로 분배됩니다.

Request Queue: [ Req1 ] -> [ Req2 ] -> [ Req3 ] -> [ Req4 ]
                 Server1   Server2    Server1    Server2

Messaging

메시징 기술은 시스템 간에 데이터를 교환할 때 사용하는 통신 방식입니다. 메시징 시스템에서, Producer(또는 Publisher)는 메시지를 생성하고, 이를 메시징 시스템에 전달합니다. 메시징 시스템은 이 메시지를 Queue에 저장합니다.

Consumer(또는 Subscriber)는 이 메시지를 메시징 시스템에서 가져와서 처리합니다. 예를 들어, RabbitMQ, Kafka, ActiveMQ 등이 있습니다.

Queue의 종류와 특징

선형 큐 (Linear Queue)

• 가장 기본적인 큐의 형태로, FIFO (First-In, First-Out) 원칙을 따릅니다.
• 삽입 연산은 큐의 뒤쪽(rear)에서, 삭제 연산은 큐의 앞쪽(front)에서 수행됩니다.

순환 큐 (Circular Queue)

• 배열을 기반으로 하는데, 배열의 마지막 요소 다음에는 배열의 첫 번째 요소가 옵니다.
• 환형 큐의 주요 이점은 공간을 재사용할 수 있다는 것입니다. 즉, 배열의 앞부분이 비어 있고 뒷부분이 꽉 찼을 때, 새로운 요소를 배열의 앞부분에 넣을 수 있습니다.

우선순위 큐 (Priority Queue)

• 각 항목이 우선순위와 함께 저장되는 큐입니다.
• 큐에서 요소를 꺼낼 때 가장 높은 우선순위의 요소가 먼저 나옵니다.
• 힙(Heap) 같은 특별한 자료구조를 사용하여 구현될 수 있습니다.
• 예) 응급실의 환자 대기열, 운영체제 프로세스 스케쥴링

Double-ended Queue (Deque, 데크)

• 양쪽 끝에서 추가 및 제거가 모두 가능한 큐입니다.
• Deque는 스택 및 큐의 특징을 모두 가지고 있습니다.
• 배열 또는 연결 리스트로 구현될 수 있습니다.
• 예) 최근에 방문한 사이트 주소 기록, 문서 작성 툴에서 undo/redo 기록