자료구조 - 큐(Queue)

큐란 무엇일까?

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이를 FIFO(First In, First Out) 구조라고 부릅니다.

가장 먼저 들어온 데이터가 가장 먼저 처리되기 때문에, 일상 속 줄 서기(대기열)와 비슷한 원리로 동작합니다.

큐의 구조

큐는 주로 두 가지 기본 연산을 수행합니다:

• enqueue(인큐): 데이터를 큐의 뒤쪽 에 추가합니다.
• dequeue(디큐): 큐의 앞쪽 에 있는 데이터를 꺼냅니다.

추가로 자주 쓰는 연산:

• peek(피크): 삭제하지 않고 가장 앞에 있는 데이터를 확인합니다.

큐는 리스트처럼 인덱스로 직접 접근하는 것이 아니라, 앞에서 꺼내고 뒤에 추가하는 구조입니다.

큐 동작 예시

1. 큐가 비어 있습니다. → []
2. enqueue(10) → [10]
3. enqueue(20) → [10, 20]
4. enqueue(30) → [10, 20, 30]
5. dequeue() → 10 꺼냄 → [20, 30]
6. peek() → 20 확인 → [20, 30]

큐 예시 (Python)

from collections import deque

queue = deque()  # 큐 생성

# enqueue (데이터 추가)
queue.append(10)
queue.append(20)
queue.append(30)

# dequeue (데이터 꺼내기)
print(queue.popleft())  # 출력: 10

# peek (맨 앞 데이터 확인)
print(queue[0])         # 출력: 20

💡 파이썬의 deque(double-ended queue)는 큐 구현에 최적화된 자료구조입니다.

큐의 시간복잡도

연산	시간복잡도	설명
enqueue	O(1)	뒤쪽에 데이터를 빠르게 추가합니다.
dequeue	O(1)	앞쪽 데이터를 빠르게 꺼냅니다.
peek	O(1)	앞쪽 데이터를 빠르게 확인할 수 있습니다.

큐의 장점과 단점

장점

• 순서대로 데이터를 처리할 수 있어 일괄 처리에 적합합니다.
• 구조가 단순하고 직관적입니다.

단점

• 중간 데이터 접근이 불가능합니다.
• 크기가 고정된 큐에서는 오버플로우(overflow)가 발생할 수 있습니다.

큐가 활용되는 예시

활용 분야	설명
프린터 인쇄 대기열	먼저 요청한 문서가 먼저 출력됩니다.
운영체제 작업 스케줄러	먼저 도착한 작업부터 처리합니다.
BFS 탐색 알고리즘	너비 우선 탐색에서 큐를 사용해 다음 노드를 순차적으로 탐색합니다.
고객 대기 시스템	순서대로 고객을 호출하거나 처리하는 데 사용됩니다.

실생활 예시로 이해하기

🧍 큐는 줄 서기와 비슷합니다. 먼저 줄 선 사람이 먼저 서비스를 받고, 뒤에 온 사람은 기다립니다.

예: 은행 번호표, 놀이공원 대기줄, 프린터 인쇄 대기줄 등

정리

항목	큐
데이터 처리 방식	FIFO (First In, First Out)
주된 연산	enqueue, dequeue, peek
주요 특징	앞에서 꺼내고, 뒤에서 넣음
활용 예시	작업 스케줄링, BFS, 고객 대기 시스템 등

스택과 큐의 차이점 및 선택 기준

항목	스택 (Stack)	큐 (Queue)
처리 방식	LIFO (후입선출)	FIFO (선입선출)
삽입 위치	맨 위 (Top)	뒤쪽 (Rear)
삭제 위치	맨 위 (Top)	앞쪽 (Front)
접근 제한	오직 맨 위만 접근 가능	앞과 뒤에서만 접근 가능
사용 예시	실행 취소, 함수 호출, 되돌리기 기능	BFS 탐색, 인쇄 대기열, 작업 스케줄링

언제 어떤 구조?

• 가장 최근의 작업을 먼저 처리해야 한다면 → 스택
• 먼저 들어온 작업을 먼저 처리해야 한다면 → 큐

예를 들어 함수 호출 처리, 실행 취소 기능은 스택이 적합하고, 인쇄 요청 처리, 고객 응대 시스템처럼 순서를 지켜야 하는 상황에는 큐가 적합합니다.