1. 개요
선입선출(先入先出, First In First Out; FIFO)의 자료구조. 대기열이라고도 한다. Queue[1]라고도 하는데, Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.
스택과 비슷하지만 조금 다르다. 위에서도 나와있듯 '표를 사기 위해 줄을 서는 사람들'을 생각하면 된다.
롯데 자이언츠 경기를 보기 위해 매표소에 가장 먼저 줄을 선 사람(First In)이 가장 먼저 표를 구매하고 가장 먼저 매표소를 빠져나갈 것(First Out)이다.
데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다.)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다.)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다. 우선순위 큐, 원형 큐 등의 베리에이션이 존재한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다[2].
2. 구현
보통의 배열을 사용해서 큐를 구현하면 Enqueue와 Dequeue을 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이를 해결하기 위해 원형 버퍼를 사용한다. 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue를 하는 형태. 대신 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓는다.연결 리스트를 사용하면 배열에 비해 매우 쉽게 구현이 가능하다.
STL에는 선형 큐가 이미 알고리즘으로 구현되어 있지만, STL의 알고리즘을 이용해 원형 큐를 구현하는 것은 상당히 힘들다. 3번째 Jeremy Jurksztowicz의 답변(영어)
2.1. 라이브러리(c++)
c++에서 헤더 <queue>를 포함하면 std::queue로 구현된 큐 자료구조를 사용할 수 있다.이 라이브러리는 상당히 스택 라이브러리와 비슷하다.
선언 :
queue<원하는 자료형(구조체 가능)> (큐 이름, 배열도 가능)
입력 : 큐의 제일 앞에 값을 삽입한다.
(큐 이름).push(<>안 자료형에 맞는 값);
값 제거 : 큐의 마지막 값을 제거한다.
(큐 이름).pop();
여기서 중요한것은 큐가 비어있을 때 실행하면 오류난다. 아래에서 서술할 empty 함수와 함께 사용해야 한다.
큐의 크기(반환값 정수)
(큐 이름).size();
큐가 비었는지 확인(반환값은 bool[3]) : 큐가 비었으면 1
(큐 이름).empty();
2.1.1. 예시 소스코드
2.2. 파이썬
Python의 리스트를 이용하면 쉽게 구현할 수 있다.#!syntax python
from typing import Any
class Queue:
def __init__(self, *args: Any):
self.__items: list[Any] = list(args)
self.__size: int = len(self.__items)
def enqueue(self, item: Any):
self.__items.append(item)
self.__size += 1
def dequeue(self):
if self.empty():
raise IndexError("dequeue from empty queue")
item: Any = self.__items.pop(0)
self.__size -= 1
return item
def empty(self):
return not self.__size
def __str__(self):
return f"{self.__items}"
def __repr__(self):
return f"{self.__items}"
def __len__(self):
return self.__size
def __iter__(self):
if self.empty():
return None
for item in self.__items:
yield item
하지만 이렇게 힘든 일을 할 필요도 없는게, 파이썬 기본 라이브러리에 큐가 구현되어 있다.
#!syntax python
from queue import Queue
Q = Queue() #큐 Q 생성
Q.put(1) #큐 Q에 1을 enqueue
Q.put(2) #큐 Q에 2를 enqueue
x = Q.get() #Q에서 dequeue해서 x에 대입
print(x) #1
양방향 큐도 있다.
#!syntax python
from collections import deque
dq = deque([1, 2, 3]) #값이 (1, 2, 3)인 양방향 큐 생성
dq.append(4) #dq의 오른쪽에 4 enqueue
x = dq.pop() #dq의 오른쪽 값을 dequeue해서 x에 대입
dq.appendleft(0) #dq의 왼쪽에 0을 enqueue
y = dq.popleft() #dq의 왼쪽 값을 dequeue해서 y에 대입
print(x, y) #4 0
3. 특수한 형태의 큐
3.1. 원형 큐[4]
큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게 된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다. 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하지만 시작과 끝이 연결되어 있다는 데서 차별성을 띤다. 링 버퍼 (ring buffer)라고 부르기도 하는데, 자료구조는 동일하지만 버퍼나 캐시 등을 목적으로 쓰는 경우 그렇게 부르는 편.기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다.[5]그래서 앞쪽에 공간이 남아 있다면 다음 그림과 같이 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐다.
<파이썬 알고리즘 인터뷰> p.260, 책만, 2020
동작하는 원리는 투 포인터와도 비슷하다. 그림과 같이 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. enQueue()를 하게 되면 rear 포인터가 앞으로 이동하고, deQueue()를 하게 되면 front 포인터가 앞으로 이동한다. 이렇게 enQueue()와 deQueue()를 반복하게 되면 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 된다. 이 그림의 enQueue(60) 이후에는 rear 포인터가 원래의 front 포인터 자리까지 도달해 빙글빙글 돌고 있는 모습을 확인할 수 있다. 만약 rear 포인터가 front 포인터와 같은 위치에서 서로 만나게 된다면, 다시 말해 만나는 위치까지 이동했다면, 그때는 정말로 여유 공간이 하나도 없다는 얘기가 되므로 공간 부족 에러를 발생시킨다.
단 생각 없이 구현할 경우 큐에 완전히 원소가 없을 때와 큐가 꽉 찼을 때를 구분할 수 없다는 단점이 생긴다.[6] 이 때문에 원소를 실제 공간보다 한 칸 적게 채우는 방법이 있고, 따로 비었는지 여부를 플래그를 붙이는 방법이 있다.
3.2. 우선순위 큐
우선순위 큐는 말 그대로 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것이다. 이 경우에 만약 우선순위가 낮은 원소가 들어간다면(Enqueue) 빼낼 때에는(Dequeue) 정말로 들어갈 땐 마음대로지만 나갈땐 아닌 상황이 된다. 대표적인 예로 heap이 있다. 자세한 내용은 힙 트리 항목 참조.3.3. 데크(Deque; Double Ended Queue)
<파이썬 알고리즘 인터뷰> p.266, 책만, 2020
일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해, 데크는 양쪽에서 모두 삽입/인출이 가능한 스택과 큐의 특징을 모두 갖고 있다. 이 추상 자료형(ADT)의 구현은 배열이나 연결 리스트 모두 가능하지만, 특별히 그림과 같이 이중 연결 리스트(Doubly Linked List)로 구현하는 편이 가장 잘 어울린다. 이중 연결 리스트로 구현하게 되면, 그림처럼 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 주기만 하면 된다. 당연히 연결 후에는 포인터를 이동하면 된다.
4. 용도
어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용된다.
5. 관련 이론
[1]
스펠링은 5개인데 그 중 뒤의 3개(eue)가 묵음, 그리고 Q 자체가 "큐"라고 읽히니 실질적으론 뒤에 붙은 ueue가 싹 다 묵음인 기묘한 단어라 가끔 농담 소재가 된다. 원어민 중에서도 "큐웨웨"(...) 같은 식으로 잘못 발음하는 사람이 가끔 있다고.
[2]
간혹
스택과 동일하게 Push와 Pop을 쓰기도 하고, Push와 Pull을 사용하는 경우도 있다.
[3]
true 혹은 false
[4]
혹은 환형 큐라고도 부른다. 무환동력과는 관련 없다
[5]
쉽게 이해해서
롯데자이언츠 표를 구매하려고 서있던 사람이 앞의 줄이 표를 구매하고 다 빠졌는데도
스마트폰을 보느라 정신이 팔려 있어 앞으로 안가고 있는 상태라고 생각하면 된다. 물론 예시기 때문에 그냥 그렇다는 정도로만 알자.
[6]
두 상황 모두 rear == front라서 발생하는 문제이다.