스택·큐: LIFO와 FIFO

정의

• 스택 (LIFO): 마지막에 넣은 것이 먼저 나옴. push / pop / top
• 큐 (FIFO): 먼저 넣은 것이 먼저 나옴. enqueue / dequeue

언어별 구현

from collections import deque
q = deque()
q.append(1)      # 뒤
x = q.popleft()  # 앞

// 간단 큐 (입력이 작을 때)
const q = [];
let head = 0;
q.push(x);
const y = q[head++];

패턴 1: 괄호·짝 맞추기

const pair = { ')': '(', ']': '[', '}': '{' };
const st = [];
for (const ch of s) {
  if (ch === '(' || ch === '[' || ch === '{') st.push(ch);
  else {
    if (!st.length || st.pop() !== pair[ch]) return false;
  }
}
return st.length === 0;

열린 것을 쌓고, 닫을 때 꼭대기와 짝인지 봅니다.

패턴 2: 단조 스택 (맛보기)

스택에 증가/감소 순을 유지하며, 현재 값보다 약한 후보를 팝합니다.
다음 큰 원소, 히스토그램 넓이 등에 쓰입니다. 처음엔 “괄호 + 계산기”만 익혀도 충분합니다.

패턴 3: BFS와 큐

레벨·최단 거리(가중치 0/1이 아닌 동일 비용)에 큐를 씁니다.

from collections import deque
q = deque([start])
seen = {start}
while q:
    cur = q.popleft()
    for nxt in neighbors(cur):
        if nxt not in seen:
            seen.add(nxt)
            q.append(nxt)

DFS는 스택(또는 재귀)과 붙습니다.

함정

• JS에서 큐를 shift()만으로 남발하면 O(n²)
• 스택이 비었는데 pop하지 않기
• BFS에서 seen에 넣을 때 표시해야 중복 enqueue를 줄임

복잡도

각 원소가 최대 한 번 push/pop되면 전체 O(n)인 경우가 많습니다.