🎯 1. 스택과 큐 기본 개념 ⭐⭐⭐

스택 (Stack) - LIFO (Last In First Out)

# 스택: 나중에 들어간 것이 먼저 나옴 (접시 쌓기)
#
#     ┌───┐
#     │ 3 │ ← top (가장 나중에 들어옴)
#     ├───┤
#     │ 2 │
#     ├───┤
#     │ 1 │ ← bottom (가장 먼저 들어옴)
#     └───┘
#
# push(3) → pop() → 3이 나옴

# 스택 연산
# - push: 맨 위에 추가
# - pop: 맨 위에서 제거
# - peek/top: 맨 위 요소 확인 (제거 안 함)

큐 (Queue) - FIFO (First In First Out)

# 큐: 먼저 들어간 것이 먼저 나옴 (줄서기)
#
#  front                    rear
#    ↓                        ↓
#  ┌───┬───┬───┬───┐
#  │ 1 │ 2 │ 3 │ 4 │
#  └───┴───┴───┴───┘
#
# enqueue(4) → dequeue() → 1이 나옴

# 큐 연산
# - enqueue: 뒤에 추가
# - dequeue: 앞에서 제거
# - front: 맨 앞 요소 확인 (제거 안 함)

리스트로 스택/큐 구현의 문제

# 스택: 리스트로 구현 가능 (O(1))
stack = []
stack.append(1)      # push - O(1) ✅
stack.append(2)
stack.pop()          # pop - O(1) ✅

# 큐: 리스트로 구현하면 느림!
queue = []
queue.append(1)      # enqueue - O(1) ✅
queue.append(2)
queue.pop(0)         # dequeue - O(n) ❌ 느림!

# 왜? pop(0)은 앞 요소 제거 후 모든 요소를 한 칸씩 앞으로 이동!
# [1, 2, 3, 4, 5]
# pop(0) → [2, 3, 4, 5]  # 모든 요소 이동 O(n)

🎯 2. deque 기본 사용법 ⭐⭐⭐

deque란?

from collections import deque

# deque (Double-Ended Queue)
# - 양쪽 끝에서 O(1)로 추가/삭제 가능
# - 스택과 큐를 모두 효율적으로 구현 가능

dq = deque([1, 2, 3, 4, 5])

양쪽 끝 추가/제거 (핵심!) ⭐⭐⭐

from collections import deque

dq = deque([1, 2, 3])

# 오른쪽 끝 추가/제거
dq.append(4)         # deque([1, 2, 3, 4]) - O(1)
dq.pop()             # 4 반환 - O(1)

# 왼쪽 끝 추가/제거
dq.appendleft(0)     # deque([0, 1, 2, 3]) - O(1) ✅
dq.popleft()         # 0 반환 - O(1) ✅

# 이게 리스트와의 핵심 차이!
# 리스트의 pop(0)은 O(n)이지만
# deque의 popleft()는 O(1)!

시간복잡도 비교

기본 메서드

from collections import deque

dq = deque([1, 2, 3, 4, 5])

# 추가
dq.append(6)         # 오른쪽 끝: deque([1, 2, 3, 4, 5, 6])
dq.appendleft(0)     # 왼쪽 끝: deque([0, 1, 2, 3, 4, 5, 6])

# 여러 개 추가
dq.extend([7, 8])    # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])
dq.extendleft([-2, -1])  # deque([-1, -2, 0, 1, ...]) (역순 주의!)

# 제거
dq.pop()             # 8 반환
dq.popleft()         # -1 반환

# 회전
dq = deque([1, 2, 3, 4, 5])
dq.rotate(1)         # deque([5, 1, 2, 3, 4]) (오른쪽으로)
dq.rotate(-1)        # deque([1, 2, 3, 4, 5]) (왼쪽으로)

# 기타
len(dq)              # 길이
dq[0]                # 첫 번째 요소 (O(1))
dq[-1]               # 마지막 요소 (O(1))
# dq[2]              # 중간 요소 (O(n) - 느림!)

dq.clear()           # 전체 삭제

🎯 3. 스택 구현 및 활용 ⭐⭐⭐

deque로 스택 구현