언제 stack을 쓰고 언제 queue를 써야 하나요? 실제 예시를 들어주세요.

Question

Accepted Answer

둘 다 양 끝이 O(1)인 선형 ADT이지만, **제거 순서**가 반대입니다. **stack은 LIFO**(가장 최근 것 먼저)이고, **queue는 FIFO**(가장 오래된 것 먼저)입니다. 문제가 요구하는 순서에 구조를 맞추세요.

## 핵심 차이

```text
Stack (LIFO):  push 1,2,3  -> pop 순서 3,2,1
Queue (FIFO):  enq  1,2,3  -> deq 순서 1,2,3
```

## 실제 예시

| STACK을 쓸 때... | QUEUE를 쓸 때... |
|---|---|
| Undo/redo(최신 동작 먼저) | 잡 스케줄링(도착 순서) |
| 브라우저 뒤로 가기 버튼 | 프린트 스풀러 / 작업 큐 |
| 함수 호출/재귀 | 그래프에서 BFS / 최단 경로 |
| 괄호 짝 맞추기, 파싱 | 서비스 간 메시지 버퍼링 |
| DFS(가장 깊은 것 먼저 탐색) | 속도 제한 / 요청 처리 |

## 코드 대조

```python
# DFS는 stack을 사용: 가장 새로운 분기를 먼저 탐색
stack = [start]
while stack:
    node = stack.pop()        # LIFO -> 깊이 우선
    for nb in graph[node]: stack.append(nb)

# BFS는 queue를 사용: 가장 가까운 것을 먼저 탐색
from collections import deque
q = deque([start])
while q:
    node = q.popleft()        # FIFO -> 레벨 단위
    for nb in graph[node]: q.append(nb)
```

## 왜 중요한가

LIFO 대 FIFO 선택은 알고리즘 동작을 직접 바꿉니다. *같은* 그래프 순회가 stack을 쓰면 DFS가 되고 queue를 쓰면 BFS가 됩니다.

문제가 "가장 최근" 또는 "가장 오래된 것 먼저"를 필요로 하는지 인식하면 즉시 올바른 구조를 떠올릴 수 있습니다.

Undo/redo(최신 동작 먼저)	잡 스케줄링(도착 순서)
브라우저 뒤로 가기 버튼	프린트 스풀러 / 작업 큐
함수 호출/재귀	그래프에서 BFS / 최단 경로
괄호 짝 맞추기, 파싱	서비스 간 메시지 버퍼링
DFS(가장 깊은 것 먼저 탐색)	속도 제한 / 요청 처리