[자료구조] 큐(Queue)

큐(Queue)란?

큐(Queue)는 선입선출(FIFO, First‑In First‑Out) 방식으로 작동하는 추상 자료구조이다.

즉, 먼저 넣은 데이터가 가장 먼저 나온다는 뜻이다.

이는 앞서 다룬 스택(Stack)의 후입선출(LIFO)과는 반대되는 개념으로,

큐에서는 가장 오래된 요소를 가장 먼저 처리한다.

실생활에선 대기열을 떠올리면 쉽다.

예를 들어 은행 창구나 놀이공원 줄을 서는 상황을 생각해보자

먼저 줄을 선 사람이 가장 먼저 서비스를 받고,

나중에 온 사람은 맨 뒤에 줄을 서서 앞사람이 빠져나갈 때까지 기다린다.

이러한 특성이 바로 큐의 FIFO 원리이다.

큐 작동 원리

queue

큐는 한쪽 끝(front)에서는 데이터를 꺼내고, 반대쪽 끝(rear)에서는 데이터를 넣는 구조로 동작한다.

front는 현재 큐에서 가장 오래된 요소(가장 먼저 들어온)가 위치한 곳
rear는 가장 최근에 추가된 요소가 위치한 곳

새로운 데이터를 넣을 때는 rear 위치 뒤에 이어 붙이고(enqueue 동작),

데이터를 제거할 때는 front 위치의 요소를 꺼낸다(dequeue 동작).

큐에 아무도 없는 빈 상태에서는 front와 rear가 동일한 곳을 가리키며, 새로운 요소가 들어오면 그 요소가 front이자 rear가 된다.

이후 요소가 추가로 들어오면 rear가 뒤쪽으로 한 칸씩 이동하며 큐의 크기가 늘어나고, 요소를 제거할 때마다 front가 한 칸씩 앞으로 이동하며 큐의 크기가 줄어든다.

이러한 작동 원리 덕분에 큐는 ”데이터의 입력 순서를 그대로 보존”하면서 처리할 수 있다.

큐 메서드 소개

큐가 제공하는 주요 연산은 다음과 같다.

스택의 push/pop과 유사하게 큐에서는 주로 enqueue/dequeue 라는 메서드를 사용한다.

메서드	설명
`enqueue(x)`	큐 맨 뒤(rear)에 요소 `x`를 추가
`dequeue()`	큐 맨 앞(front)의 요소를 제거하고 반환. 비어 있으면 `IndexError` 등 예외 발생
`peek()`	큐 맨 앞의 요소를 확인만 (제거하지 않음). 비어 있으면 예외 발생
`is_empty()`	큐가 비어 있으면 `True`, 아니면 `False`

⚠️ 주의 사항

빈 큐에서의 dequeue()/ peek(): 스택과 마찬가지로 반드시 예외 처리 또는 조건 검사로 안정성 확보

실제 코드로 구현 (Python list로 구현)

class Queue:
    def __init__(self):
        self._data = []

    def enqueue(self, x):
        """큐 맨 뒤에 x 추가"""
        self._data.append(x)

    def dequeue(self):
        """큐 맨 앞 요소 제거 후 반환"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._data.pop(0)  # 리스트의 0번 인덱스 제거

    def peek(self):
        """큐 맨 앞 요소 확인"""
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self._data[0]

    def is_empty(self) -> bool:
        """큐가 비어 있는지 검사"""
        return not self._data

    # 추가 옵션: len(Queue) 사용 가능
    def __len__(self):
        """큐의 크기 확인"""
        return len(self._data)

위처럼 list를 이용한 큐 구현은 개념을 이해하기에는 쉽지만…

내부적으로 pop(0) 연산이 리스트의 모든 요소를 한 칸씩 당기는 O(n) 작업이므로 비효율적일 수 있다.

큐의 추상적 동작은 enqueue/dequeue 모두 O(1)이 되는 게 이상적이며,

파이썬에서는 이러한 연산을 빠르게 수행하기 위해 collections.deque와 같은 별도 자료구조를 제공한다 (아래 원형 큐와 deque 항목 참고).

큐의 시간 복잡도

연산	시간 복잡도	메모리 사용
`enqueue(x)`	O(1)	O(1) 추가
`dequeue()`	O(1)	O(1) 제거
`peek()`	O(1)	O(1) 읽기만
`is_empty()`	O(1)	O(1) 확인
전체 요소 n개 저장	—	O(n) 총 사용

이상적인 큐의 기본 연산들은 현재 큐의 크기와 상관없이 대부분 상수 시간에 실행된다.

즉 새로운 요소 추가, 제거, 맨 앞 확인, 비었는지 검사 등의 연산은 모두 O(1)이다.

물론 위 구현처럼 파이썬 list로 큐를 만들 경우 dequeue()가 O(n)으로 느려질 수 있지만 😱😢

추상적으로 바라본 큐의 연산 비용은 O(1)로 간주한다 👀

큐의 변형 구조

원형 큐 (Circular Queue)

circle-queue-init 배열 기반 큐의 공간 및 시간 낭비 문제를 해결한 구조가 원형 큐이다.

원형 큐에서는 배열의 마지막 위치가 다시 처음 위치와 연결되어 원 형태로 동작한다.

이렇게 하면 front와 rear 포인터가 배열 끝에 도달하더라도, 빈 공간이 있으면 앞으로 돌아가서 사용하게 된다

예를 들어 크기가 n인 배열로 원형 큐를 구현할 경우,

새 요소를 추가할 때 인덱스 계산을 (rear + 1) % n로 수행한다.

원형 큐에서 큐가 가득 찼는지 여부는 일반 큐와 달리

front == (rear + 1) % n인지 확인하는 방식 등으로 판단한다 (또는 요소 개수를 별도로 관리하기도 한다).

circle-queue-full 이러한 구조는 시간 복잡도를 향상시켜 주기 때문에, 언어나 라이브러리에 따라 원형 큐를 기본 구현으로 제공하기도 한다.
(파이썬의 deque도 내부적으로 연결 리스트와 원형 기법을 사용하여 양 끝 삽입/삭제를 효율적으로 지원한다.)

덱(deque, Double-Ended Queue)

덱은 앞뒤 모두에서 삽입과 삭제를 효율적으로 수행할 수 있는 큐의 확장 형태이다.

일반적인 큐가 한쪽 끝(rear)에서만 삽입, 다른 한쪽(front)에서만 삭제가 가능한 것에 반해,

덱은 양쪽 끝 모두에서 enqueue와 dequeue가 가능하다.

따라서 덱을 사용하면 스택처럼 동작시킬 수도 있고,

일반 큐처럼 쓸 수도 있으며, 앞뒤 양 방향으로 자유롭게 데이터 처리가 가능하다.

파이썬에서는 collections.deque 클래스로 덱을 제공하고 있으며, 리스트 대비 매우 빠른 양 끝 연산 성능을 갖고 있다.

deque.append(x)를 하면 오른쪽 끝에 요소를 추가하고, deque.appendleft(x)를 하면 왼쪽 끝에 추가한다.

마찬가지로 pop()은 오른쪽 끝에서 제거, popleft()는 왼쪽 끝에서 제거한다.

즉 deque를 이용하면 한 자료구조로 스택과 큐 양쪽 동작을 모두 지원할 수 있다.

개발 시 큐 사용 사례

🔍 대표 사용 예시

운영체제의 프로세스 스케줄링: CPU 할당을 기다리는 프로세스들을 큐로 관리하여, 먼저 도착한 프로세스부터 CPU를 배정

캐시(Cache) 구현: 일정 크기의 캐시에서 가장 오래된 데이터부터 교체하는 FIFO 전략에 큐를 활용 (예: FIFO 페이지 교체 알고리즘 등)

큐 알고리즘 유형 예시

1. 너비 우선 탐색 (BFS)

그래프 탐색 알고리즘인 BFS(Breadth-First Search)는 큐를 활용하여 구현할 수 있는 대표적인 예시이다. BFS에서는 시작 정점으로부터 가까운 노드들부터 차례로 탐색해나가는데, 먼저 발견된 이웃들을 먼저 방문하기 위해 선입선출 구조인 큐를 사용한다.

아래 코드는 간단한 그래프를 BFS로 탐색하는 예시이다.

Queue 클래스를 이용해 이웃 노드를 enqueue하고, 방문 순서대로 dequeue하면서 탐색을 진행한다.

# 인접 리스트로 표현한 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

def bfs(start):
    q = Queue()           # 우리가 구현한 Queue 사용
    q.enqueue(start)
    visited = [start]      # 방문한 노드를 기록
    while not q.is_empty():
        v = q.dequeue()     # 큐에서 다음 노드를 꺼냄
        for nv in graph[v]: # 모든 이웃 노드에 대해
            if nv not in visited: # 아직 방문되지 않았다면
                visited.append(nv)
                q.enqueue(nv) # 큐에 추가하여 다음 레벨 탐색
    return visited

print(bfs('A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

위 코드에서 'A'부터 시작하여 BFS를 수행하면, 큐에 들어간 순서대로 A -> B -> C -> D -> E -> F 순으로 탐색하게 된다. 즉, 루트에 가까운 노드일수록 먼저 처리되어 출력됨을 볼 수 있다.

결론

큐(Queue)는 스택과 마찬가지로 쉽게 떠올릴 수 있는 생활 속 개념을 기반으로 한 덕분에 직관적이고 배우기 쉬우면서도, 다양한 알고리즘 및 시스템 구현에 필수적인 자료구조이다.

들어온 순서대로 처리해야 하는 모든 상황에서 큐를 활용할 수 있기 때문에, 프로그래밍 전반에서 쓰임새가 매우 넓다. 특히 BFS처럼 입력된 순서를 보존해야 하는 알고리즘에서는 큐가 핵심 역할을 한다.

스택과 함께 큐를 이해했다면, 이제 이들의 원리를 응용한 구조들(원형 큐, 덱, 우선순위 큐 등)도 자연스럽게 다가올 것이다.

큐의 개념을 확장하면 중요도가 높은 요소를 먼저 처리하는 우선순위 큐(Priority Queue) 등의 구조로도 나아갈 수 있다. 다음에는 이러한 우선순위 큐에 대해 살펴보도록 하자.