큐(Queue)

개요

큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 선입선출(First-In, First-Out, FIFO) 구조를 가지는 선형 자료구조이다. 데이터는 **뒤(Rear)**에서 삽입되고, **앞(Front)**에서 삭제되며, 일상적인 줄서기, 프로세스 스케줄링, 버퍼 처리 등에 널리 사용된다. 파이썬에서는 collections.deque, 리스트, 큐 모듈 등을 통해 구현할 수 있다.

---

1. 개념 및 정의

항목	설명
구조	선형적, 한쪽에서는 삽입, 반대쪽에서는 삭제 수행
주요 연산	enqueue(삽입), dequeue(삭제), peek(앞 요소 확인), isEmpty
원리	FIFO (First-In, First-Out)

---

2. 큐 연산 동작 예시

초기: []
enqueue(10) → [10]
enqueue(20) → [10, 20]
dequeue() → [20] (10 제거)
enqueue(30) → [20, 30]
peek() → 20

---

3. 파이썬 구현 예시 (deque 기반)

from collections import deque

queue = deque()
queue.append(10)  # enqueue
queue.append(20)
print(queue.popleft())  # dequeue → 10
print(queue[0])  # peek → 20
print(not queue)  # isEmpty → False

deque는 양쪽에서 삽입/삭제가 가능한 큐 구조로 성능이 우수하다.

---

4. 시간 및 공간 복잡도

연산	시간 복잡도
enqueue	O(1)
dequeue	O(1)
peek	O(1)
isEmpty	O(1)

deque, queue.Queue는 리스트보다 더 효율적인 큐 구현을 제공한다.

---

5. 큐의 종류

종류	설명
일반 큐	가장 기본적인 FIFO 구조
원형 큐	큐의 크기를 고정하여 반복적으로 연결
우선순위 큐	값의 우선순위에 따라 먼저 꺼냄 (heap 기반)
이중 큐(Deque)	양쪽에서 삽입/삭제가 가능한 큐

---

6. 큐 vs 스택 비교

항목	큐(Queue)	스택(Stack)
구조	선입선출 (FIFO)	후입선출 (LIFO)
삽입 위치	뒤쪽(Rear)	위쪽(Top)
삭제 위치	앞쪽(Front)	위쪽(Top)
사용 예시	대기열, CPU 스케줄링	함수 호출, 수식 계산

---

7. 활용 사례

분야	활용 예시
운영체제	프로세스 관리, CPU 스케줄링
네트워크	패킷 큐, 버퍼
그래프 탐색	BFS(너비 우선 탐색)
웹 서버	요청 처리 큐
데이터 처리	이벤트 큐, 대기열 관리

---

8. 큐의 장단점

항목	장점	단점
구조	단순, 직관적인 흐름 관리 가능	임의 위치 접근 불가
효율	enqueue/dequeue 모두 O(1)	일반 리스트로 구현 시 비효율 발생 가능
유연성	다양한 큐 구조 확장 가능	복잡한 우선순위 처리에는 부적합 (일반 큐 기준)

---

9. 결론

큐는 선입선출이라는 간단한 구조 속에 다양한 활용 가능성을 지닌 자료구조이다. 운영체제, 네트워크, 알고리즘 BFS 등 다양한 분야에서 필수적으로 사용되며, 파이썬에서는 deque, queue.Queue, PriorityQueue 등으로 쉽게 구현 가능하다. 스택과 함께 자료구조 학습의 핵심 개념 중 하나이다.