Ch.4 스택과 큐
큐와 덱 (FIFO)
줄 서기의 원칙 먼저 온 사람이 먼저 나간다
편의점 계산대 앞 줄을 떠올려보세요. 먼저 줄 선 사람이 먼저 계산합니다. 이것이 큐(Queue)의 FIFO 원리이고, 덱(Deque)은 양쪽에서 넣고 뺄 수 있는 확장판입니다.
Python list로 큐를 만들면 왜 느릴까?
list.pop(0)은 O(n) — collections.deque가 해답입니다.
핵심 개념
큐(Queue)
선입선출(FIFO) 방식의 자료구조
덱(Deque)
양쪽 끝에서 삽입/삭제가 가능한 자료구조
핵심 내용
큐(Queue) = 줄 서기 먼저 들어간 것이 먼저 나옵니다
스택 vs 큐 스택: LIFO — 마지막에 넣은 것 먼저 (접시) 큐: FIFO — 먼저 넣은 것 먼저 (줄 서기)
큐의 핵심 연산 enqueue(넣기)와 dequeue(빼기)
* list.pop(0)은 O(n)! deque.popleft()는 O(1)입니다
Python에서 큐가 필요하면 collections.deque를 쓰세요
from collections import deque
# 큐로 사용
q = deque()
q.append(10) # enqueue: 뒤에 추가
q.append(20)
q.append(30)
print(q) # deque([10, 20, 30])
front = q.popleft() # dequeue: 앞에서 제거
print(front) # 10
print(q) # deque([20, 30])덱(Deque)은 양쪽에서 넣고 빼는 것이 모두 O(1)입니다
from collections import deque
d = deque([1, 2, 3])
# 오른쪽 끝
d.append(4) # [1, 2, 3, 4]
d.pop() # 4 → [1, 2, 3]
# 왼쪽 끝
d.appendleft(0) # [0, 1, 2, 3]
d.popleft() # 0 → [1, 2, 3]
print(d) # deque([1, 2, 3])큐에서 원소를 꺼내는 연산은?
Python에서 큐를 구현할 때 list.pop(0) 대신 쓰는 메서드는?
deque.___() → O(1)로 앞에서 제거
deque의 appendleft()와 popleft()는 모두 O(n)이다
큐와 덱 마스터!
핵심 용어
큐(Queue)
선입선출(FIFO) — First In, First Out
덱(Deque)
Double-Ended Queue — 양쪽에서 삽입/삭제
enqueue(x)
뒤쪽에 x 추가 — O(1)
dequeue()
앞쪽 원소 제거 및 반환 — O(1)*
front/peek
앞쪽 원소 확인 — O(1)
list.pop(0)
O(n) — 전체 원소 이동 필요
deque.popleft()
O(1) — 이중 연결 리스트 기반
list.insert(0, x)
O(n)
deque.appendleft(x)
O(1)
정리 노트
큐와 덱 (FIFO)
핵심 개념
- 큐
- FIFO — First In, First Out
- 덱
- 양쪽에서 삽입/삭제 가능
- Python 구현
- collections.deque 사용
deque 주요 메서드
- append(x)
- 오른쪽에 추가 — O(1)
- appendleft(x)
- 왼쪽에 추가 — O(1)
- pop()
- 오른쪽에서 제거 — O(1)
- popleft()
- 왼쪽에서 제거 — O(1)
면접에서 큐가 필요하면 from collections import deque를 바로 쓰세요!
시각 자료
핵심 정리
- 1큐 = FIFO, 덱 = 양방향 큐
- 2collections.deque로 O(1) 큐 구현
- 3list.pop(0)은 O(n) — 절대 큐로 쓰지 말 것!
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작