📚스택(Stack)

“쌓는다” 라는 개념의 자료구조이다.

위 그림처럼 상자를 1,2,3,4 차례로 넣고 뺄때 4,3,2,1 순으로 나오듯,
가장 나중에 들어간 데이터가 가장 먼저 나온다.

이를 LIFO 구조 (Last In, First Out)라 한다.

---

☑️ 스택의 구조

연산	의미
push()	데이터를 스택에 "넣는다"
pop()	데이터를 스택에서 "꺼낸다"
peek()	스택의 맨 위 데이터를 "확인"
is_empty()	스택이 비었는지 확인

---

☑️ 스택의 동작 예시

스택: [1]
스택: [1, 2]
스택: [1, 2, 3]  ← 3 push
스택: [1, 2]     ← 3 pop
스택: [1]        ← 2 pop

---

☑️ 스택 사용 예시

1) 괄호 짝 맞추기 문제

• 열린 괄호 push
• 닫힌 괄호 pop
  → 스택이 비었는지로 유효성 체크

2) DFS 구현 시 사용

• 재귀 대신 스택을 직접 사용해서 DFS 구현 가능

3) 백트래킹 경로 기록

• 경로를 스택에 쌓았다가 되돌릴 때 pop()

---

☑️ 시간 복잡도

연산	시간복잡도
push()	O(1)
pop()	O(1)
peek()	O(1)

→ 모든 연산이 빠름

---

📚 큐(Queue)

큐는 스택과 정반대 방식으로, "먼저 들어간 데이터가 먼저 나오는 자료구조"이다.
즉, 선입선출(FIFO, First In First Out) 구조

치킨을 주문했을 때, 주문을 “큐” 방식으로 저장해야지 먼저 주문한 사람의 치킨이 빨리 나올 것!

---

☑️ 큐의 기본 연산

연산	설명
enqueue()	데이터를 "뒤"에 추가 (삽입)
dequeue()	데이터를 "앞"에서 제거 (꺼냄)
peek()	맨 앞의 데이터를 확인 (삭제 X)
is_empty()	큐가 비었는지 확인

---

☑️ 동작 예시

예)

enqueue(1) → [1]
enqueue(2) → [1, 2]
enqueue(3) → [1, 2, 3]
dequeue()   → [2, 3] → 1 출력
dequeue()   → [3]   → 2 출력

---

☑️ 파이썬으로 구현

1) 리스트로 구현 (비효율적)

queue = []

# enqueue
queue.append(5)
queue.append(7)

# dequeue (비효율: O(N))
print(queue.pop(0))  # 5
print(queue.pop(0))  # 7

❌ 단점: pop(0)은 리스트의 앞쪽 데이터를 빼면 나머지를 모두 앞으로 당겨야 해서 O(N)

---

2) collections.deque로 구현 (추천)

from collections import deque

queue = deque()

# enqueue
queue.append(5)
queue.append(7)

# dequeue (O(1))
print(queue.popleft())  # 5
print(queue.popleft())  # 7

• *popleft()**를 써야 진짜 "큐"처럼 동작!
• deque는 양쪽에서 O(1)으로 삽입/삭제 가능

---

☑️ 큐 사용 예시

1) BFS (너비 우선 탐색)

• BFS 탐색은 큐를 사용해서 가까운 노드부터 방문

2) 캐시 구현

• 캐시(메모리)는 오래된 데이터를 먼저 내보냄 (FIFO)

3) 작업 스케줄러

• 프로세스나 네트워크 패킷 처리도 큐 구조를 사용

---

☑️ 시간 복잡도

연산	시간 복잡도 (deque 기준)
enqueue()	O(1)
dequeue()	O(1)
peek()	O(1)