anonymous.rs

자료구조: 큐 (Queue)

7 min read

큐 (Queue) 자료구조 완벽 가이드

스택(Stack)과 함께 프로그래밍에서 가장 빈번하게 사용되는 선형 자료구조인 **큐(Queue)**에 대해 알아보겠습니다.

1. 큐(Queue)란?

큐는 놀이공원에서 놀이기구를 타기 위해 서 있는 ‘줄’과 같은 자료구조입니다. 한쪽 끝에서는 데이터가 삽입되고, 반대쪽 끝에서는 데이터가 삭제되는 양방향 선형 구조를 가집니다.

가장 중요한 특징은 선입선출 (FIFO: First-In, First-Out) 원칙을 따른다는 것입니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나갑니다.

데이터가 삽입되는 쪽을 Rear (또는 Back), 데이터가 빠져나가는 쪽을 **Front (또는 Head)**라고 부릅니다.

2. 큐의 주요 연산 및 시간 복잡도

큐의 주요 연산 역시 스택과 마찬가지로 대부분 의 시간 복잡도를 가집니다.

연산설명시간 복잡도
Enqueue (Push)큐의 맨 뒤(Rear)에 새로운 데이터를 삽입합니다.
Dequeue (Pop)큐의 맨 앞(Front)에 있는 데이터를 제거하고 반환합니다.
Peek (Front)큐의 맨 앞(Front)에 있는 데이터를 제거하지 않고 반환(확인)합니다.
isEmpty큐가 비어있는지 확인합니다.

3. 큐의 구현과 주의점

큐 역시 배열이나 연결 리스트로 구현할 수 있습니다. 하지만 일반적인 배열을 사용하여 큐를 구현할 때 주의할 점이 있습니다.

배열 기반 큐에서 Dequeue 연산을 수행하여 맨 앞(인덱스 0)의 데이터를 제거하면, 뒤에 있는 모든 데이터를 한 칸씩 앞으로 당겨야 하므로 의 시간 복잡도가 발생할 수 있습니다. 이를 해결하기 위해 원형 큐(Circular Queue) 형태를 사용하거나, 연결 리스트 기반의 큐를 사용하는 것이 효율적입니다.

파이썬에서의 효율적인 큐 사용 (collections.deque)

파이썬에서는 일반 리스트(list)의 pop(0)을 사용하면 이 걸리므로 큐 구현에 적합하지 않습니다. 대신 **collections.deque (Double-Ended Queue)**를 사용하는 것이 표준입니다. deque는 양쪽 끝에서의 삽입과 삭제가 모두 에 수행되도록 최적화되어 있습니다.

from collections import deque
 
# 덱(deque)을 활용하여 큐 생성
queue = deque()
 
# 데이터 삽입 (Enqueue) - O(1)
queue.append(1)
queue.append(2)
queue.append(3)
print(f"현재 큐: {list(queue)}") # [1, 2, 3]
 
# 맨 앞 데이터 확인 (Peek) - O(1)
front_element = queue[0]
print(f"Front 데이터: {front_element}") # 1
 
# 데이터 추출 (Dequeue) - O(1)
# 큐의 맨 앞(왼쪽)에서 꺼냄
dequeued_element = queue.popleft()
print(f"추출된 데이터: {dequeued_element}") # 1
print(f"Dequeue 이후 큐: {list(queue)}") # [2, 3]

4. 큐의 종류

  • 선형 큐 (Linear Queue): 기본적인 일자 형태의 큐입니다. 배열로 구현 시 빈 공간을 재활용하지 못하는 단점이 있습니다.
  • 원형 큐 (Circular Queue): 배열의 끝과 처음이 연결된 것처럼 논리적으로 원형으로 구성하여 공간의 재사용성을 높인 큐입니다.
  • 우선순위 큐 (Priority Queue): FIFO 원칙이 아닌, 우선순위가 높은 데이터가 먼저 나가는 큐입니다. (일반적으로 힙(Heap)으로 구현)
  • 덱 (Deque, Double-Ended Queue): 양쪽 끝(Front, Rear) 모두에서 데이터의 삽입과 삭제가 가능한 유연한 큐입니다.

5. 큐의 활용 사례

큐는 데이터를 ‘들어온 순서대로’ 공평하게 처리해야 할 때, 또는 서로 다른 속도로 동작하는 두 장치/프로세스 사이에서 버퍼(Buffer) 역할을 할 때 널리 사용됩니다.

  1. 너비 우선 탐색 (BFS, Breadth-First Search): 그래프나 트리에서 같은 레벨(너비)의 노드들을 먼저 탐색하기 위해 큐를 사용합니다.
  2. 프린터 스풀링 (Print Spooling): 여러 문서의 인쇄를 요청했을 때, 프린터는 큐에 문서들을 저장해 두고 요청된 순서대로 인쇄합니다.
  3. 프로세스 스케줄링: 운영체제가 준비 상태인 프로세스들을 레디 큐(Ready Queue)에 넣고 순서대로 CPU를 할당합니다.
  4. 캐시 (Cache) 구현: LRU (Least Recently Used) 알고리즘 같은 캐시 교체 정책을 구현할 때 큐의 개념이 응용됩니다.
  5. 비동기 데이터 전송 / 메시지 큐: 생산자(Producer)와 소비자(Consumer) 패턴에서 데이터를 임시로 저장하고 순차적으로 처리하는 메시지 브로커(RabbitMQ, Kafka 등)의 근간이 됩니다.

요약

큐(Queue)는 “먼저 들어온 것이 먼저 나가는(FIFO)” 원칙을 따르는 자료구조입니다. 순서가 보장되어야 하는 작업 대기열, 버퍼, BFS 탐색 알고리즘 등에서 핵심적인 역할을 합니다. 구현 시 성능 문제(배열 이동 등)를 고려하여 연결 리스트 기반 또는 원형 큐, 파이썬의 경우 deque를 적절히 활용해야 합니다.

Graph View