스택과 큐

스택

한쪽 문만 있는 상자 더미

• LIFO (Last in First out)

✔ 주요 연산

push : 넣기

pop : 꺼내기

peek/top : 맨 위 확인

stack = []
stack.append(1)   # push
stack.pop()       # pop
stack[-1]         # top

👉 되돌리기, 쌓기, 최근 요소

✅ 실제 코테 패턴

• 올바른 괄호

• 괄호 회전 문제

• HTML 태그 짝 검사

• 임시 저장소로 사용 -> 하나씩 넣다가 조건 맞으면 되돌아가서 제거

• (단조 스택) -> 나보다 큰/작은 게 처음으로 나오는 순간

큐

줄 서기

• FIFO (First in First out) : 먼저 들어온 게 먼저 나감

✔ 주요 연산

enqueue : 넣기

dequeue : 빼기

from collections import deque

q = deque()
q.append(1)       # enqueue
q.popleft()       # dequeue (O(1))

-> list로 pop(0) 으로 작성하면 시간 초과 나기가 쉬움

👉 순서, 대기, BFS

✅실제 코테 패턴

• 먼저 들어온 작업부터 처리

• (BFS 최단거리) 방문 처리 + 거리 계산

• 회전/원형 큐 -> 앞으로 빼서 뒤로 다시 넣기

• 우선순위 큐 -> heap