스택과 큐 — LIFO vs FIFO

이 토픽을 마치면

스택과 큐의 원리를 설명할 수 있고, 각각 어디에 쓰이는지 알게 됩니다.

스택 — 접시 쌓기

스택(Stack)은 위에서만 넣고 빼는 구조입니다.

text

┌─────┐
  push → │  30 │ ← pop (가장 마지막에 넣은 것을 먼저 꺼냄)
         ├─────┤
         │  20 │
         ├─────┤
         │  10 │
         └─────┘

식당에서 접시를 쌓는 것과 같습니다. 마지막에 올린 접시를 먼저 꺼냅니다. 이것을 LIFO(Last In, First Out) — 후입선출이라고 합니다.

python

stack = []

# push — 위에 쌓기
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)        # [10, 20, 30]

# pop — 위에서 꺼내기
top = stack.pop()
print(top)          # 30 (마지막에 넣은 것)
print(stack)        # [10, 20]

# peek — 꺼내지 않고 맨 위 확인
print(stack[-1])    # 20

스택이 쓰이는 곳

활용	설명
되돌리기 (Ctrl+Z)	마지막 동작부터 취소
브라우저 뒤로가기	마지막 방문 페이지로
함수 호출 스택	마지막 호출된 함수부터 반환
괄호 검증	`({[]})` 짝 맞추기

큐 — 줄 서기

큐(Queue)는 뒤에서 넣고 앞에서 빼는 구조입니다.

text

enqueue →  ┌────┬────┬────┐  → dequeue
             │ 10 │ 20 │ 30 │
             └────┴────┴────┘
             앞(front)    뒤(rear)

편의점 계산대 줄과 같습니다. 먼저 온 사람이 먼저 계산합니다. 이것을 FIFO(First In, First Out) — 선입선출이라고 합니다.

python

from collections import deque

queue = deque()

# enqueue — 뒤에 넣기
queue.append(10)
queue.append(20)
queue.append(30)
print(queue)         # deque([10, 20, 30])

# dequeue — 앞에서 꺼내기
front = queue.popleft()
print(front)         # 10 (가장 먼저 넣은 것)
print(queue)         # deque([20, 30])

Python의 list로도 큐를 구현할 수 있지만, list.pop(0)은 모든 요소를 앞으로 밀어야 해서 느립니다. deque는 양쪽 끝 연산이 모두 O(1)입니다.

큐가 쓰이는 곳

활용	설명
프린터 대기열	먼저 보낸 문서부터 인쇄
작업 스케줄링	먼저 요청된 작업부터 처리
BFS (너비 우선 탐색)	가까운 노드부터 방문
메시지 큐	서버 간 메시지 순서 보장

스택 vs 큐 비교

특성	스택	큐
원칙	LIFO (후입선출)	FIFO (선입선출)
비유	접시 쌓기	줄 서기
넣기	push (위에)	enqueue (뒤에)
빼기	pop (위에서)	dequeue (앞에서)
Python	`list.append()` + `list.pop()`	`deque.append()` + `deque.popleft()`

실전 예제: 괄호 검증 (스택 활용)

python

def is_valid_brackets(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return len(stack) == 0

print(is_valid_brackets("({[]})"))   # True
print(is_valid_brackets("([)]"))     # False
print(is_valid_brackets("(("))       # False

여는 괄호를 만나면 스택에 push, 닫는 괄호를 만나면 pop해서 짝이 맞는지 확인합니다. 스택의 LIFO 특성이 "가장 최근에 열린 괄호부터 닫아야 한다"는 규칙과 정확히 일치합니다.