개념
FIFO (First In First Out) 구조의 자료구조
가장 먼저 들어온 데이터가 가장 먼저 나감 (선입선출)
시간복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| enqueue | O(1) | 큐의 뒤에 데이터 추가 |
| dequeue | O(1) | 큐의 앞에서 데이터 제거 |
| front/peek | O(1) | 큐의 맨 앞 데이터 조회 |
| isEmpty | O(1) | 큐가 비었는지 확인 |
특징
장점
- 공정한 처리: 먼저 온 데이터를 먼저 처리
- 빠른 연산: 모든 연산이
O(1) - 순서 보장: 입력 순서대로 처리
단점
- 제한된 접근: 앞과 뒤에서만 접근 가능
- 중간 접근 불가: 특정 위치의 데이터에 접근 어려움
활용 분야
- BFS (너비 우선 탐색)
- 프린터 대기열
- 프로세스 스케줄링
- 네트워크 패킷 처리
Python 구현
1. collections.deque 사용 (가장 추천)
from collections import deque
# 큐 생성
queue = deque()
# enqueue (추가)
queue.append(1)
queue.append(2)
queue.append(3)
# dequeue (제거)
print(queue.popleft()) # 1
# front (맨 앞 조회)
print(queue[0]) # 2
# size
print(len(queue)) # 2
# 시간복잡도: 모든 연산 O(1)2. 리스트로 구현 (비추천 - dequeue가 O(n))
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item) # O(1)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0) # O(n) - 비효율적!
return None
def front(self):
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)3. 원형 큐 (Circular Queue) 구현
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0
self.rear = 0
self.count = 0
def enqueue(self, item):
if self.is_full():
return False
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.count += 1
return True
def dequeue(self):
if self.is_empty():
return None
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.count -= 1
return item
def peek(self):
if self.is_empty():
return None
return self.queue[self.front]
def is_empty(self):
return self.count == 0
def is_full(self):
return self.count == self.capacity
def size(self):
return self.count
# 사용 예시
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue()) # 1
print(cq.peek()) # 2핵심: 배열을 원형으로 사용하여 공간 효율성 증가
큐의 종류
1. 일반 큐 (Linear Queue)
기본적인 FIFO 구조
2. 원형 큐 (Circular Queue)
배열의 끝과 시작이 연결된 형태
3. 우선순위 큐 (Priority Queue)
우선순위가 높은 데이터가 먼저 나감
4. 덱 (Deque - Double Ended Queue)
양쪽 끝에서 삽입/삭제 가능
자주 나오는 문제 유형
1. 요세푸스 문제 (Josephus Problem)
문제: N명이 원형으로 앉아 K번째마다 제거될 때, 제거 순서 구하기
from collections import deque
def josephus(n, k):
queue = deque(range(1, n + 1))
result = []
while queue:
# k-1번 회전
for _ in range(k - 1):
queue.append(queue.popleft())
# k번째 사람 제거
result.append(queue.popleft())
return result
# 테스트
print(josephus(7, 3))
# [3, 6, 2, 7, 5, 1, 4]
# 시간복잡도: O(n*k)
# 공간복잡도: O(n)핵심: 큐를 회전시키며 K번째 요소를 제거
2. 카드 뒤집기
문제: N장의 카드에서 맨 위 카드를 버리고, 그 다음 카드를 맨 뒤로 이동
from collections import deque
def last_card(n):
queue = deque(range(1, n + 1))
while len(queue) > 1:
queue.popleft() # 맨 위 카드 버리기
queue.append(queue.popleft()) # 다음 카드를 맨 뒤로
return queue[0]
# 테스트
print(last_card(6)) # 4
# 과정: [1,2,3,4,5,6] → [3,4,5,6] → [4,5,6,3] → [5,6,3] → [6,3,5] → [3,5] → [5,3] → [3] (틀림)
# 실제: [1,2,3,4,5,6] → [2,3,4,5,6] → [3,4,5,6,2] → [4,5,6,2] → [5,6,2,4] → [6,2,4] → [2,4,6] → [4,6] → [6,4] → [4]
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 큐의 회전 연산 활용
3. 최근 요청 횟수 계산
문제: 최근 3000ms 이내의 요청 개수를 반환
from collections import deque
class RecentCounter:
def __init__(self):
self.queue = deque()
def ping(self, t):
self.queue.append(t)
# 3000ms 이전의 요청 제거
while self.queue and self.queue[0] < t - 3000:
self.queue.popleft()
return len(self.queue)
# 테스트
counter = RecentCounter()
print(counter.ping(1)) # 1 (1ms에 요청)
print(counter.ping(100)) # 2 (100ms에 요청)
print(counter.ping(3001)) # 3 (3001ms에 요청)
print(counter.ping(3002)) # 3 (1ms 요청이 범위 밖)
# 시간복잡도: 평균 O(1)
# 공간복잡도: O(n)핵심: 슬라이딩 윈도우를 큐로 구현
4. 큐로 스택 구현 (Implement Stack using Queues)
문제: 두 개의 큐로 스택(LIFO) 구현
from collections import deque
class StackWithQueues:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x):
# q2에 새 요소 추가
self.q2.append(x)
# q1의 모든 요소를 q2로 이동
while self.q1:
self.q2.append(self.q1.popleft())
# q1과 q2를 교환
self.q1, self.q2 = self.q2, self.q1
def pop(self):
return self.q1.popleft() if self.q1 else None
def top(self):
return self.q1[0] if self.q1 else None
def empty(self):
return len(self.q1) == 0
# 테스트
stack = StackWithQueues()
stack.push(1)
stack.push(2)
print(stack.top()) # 2
print(stack.pop()) # 2
print(stack.pop()) # 1
# 시간복잡도: push O(n), pop O(1)핵심: 새 요소를 항상 앞에 위치시켜 LIFO 구현
5. 프로세스 스케줄링 (Round Robin)
문제: 각 프로세스에 time quantum만큼 실행 시간을 주고 순환
from collections import deque
def round_robin(processes, quantum):
queue = deque(processes) # [(process_id, remaining_time), ...]
execution_order = []
while queue:
process_id, remaining = queue.popleft()
# quantum만큼 실행
executed = min(quantum, remaining)
execution_order.append((process_id, executed))
# 남은 시간이 있으면 다시 큐에 추가
remaining -= executed
if remaining > 0:
queue.append((process_id, remaining))
return execution_order
# 테스트
processes = [('P1', 10), ('P2', 5), ('P3', 8)]
result = round_robin(processes, 3)
print(result)
# [('P1', 3), ('P2', 3), ('P3', 3), ('P1', 3), ('P2', 2), ('P3', 3), ('P1', 3), ('P3', 2), ('P1', 1)]
# 시간복잡도: O(n)핵심: 큐를 이용한 공정한 자원 분배
추천 연습 문제
기초
중급
- 백준 1966번 - 프린터 큐
- 백준 11866번 - 요세푸스 문제 0
- LeetCode 933 - Number of Recent Calls
- LeetCode 225 - Implement Stack using Queues
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | FIFO (First In First Out) |
| 연산 | enqueue, dequeue, front 모두 O(1) |
| 구현 | collections.deque 사용 추천 |
| 활용 | BFS, 스케줄링, 대기열 시스템 |
스택 vs 큐
| 특성 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 구조 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입 | push (맨 위) | enqueue (뒤) |
| 삭제 | pop (맨 위) | dequeue (앞) |
| 활용 | 함수 호출, 괄호 검사 | BFS, 작업 대기열 |
| Python | list 사용 가능 | deque 사용 필수 |
중요 포인트
Python에서 큐를 구현할 때는 반드시
collections.deque를 사용
list의pop(0)은O(n)시간이 걸려 비효율적