스택과 큐란? LIFO와 FIFO를 파이썬 예제로 이해하기

스택과 큐가 해결하는 문제

많은 프로그램은 항목을 기억해 두었다가 정해진 순서로 나중에 처리해야 합니다. 스택은 가장 최근 항목을 먼저 꺼내 주므로 함수 호출, 실행 취소 기록, 괄호 짝 맞추기, 깊이 우선 탐색 같은 중첩된 작업에 맞습니다. 큐는 가장 오래된 항목을 먼저 꺼내 주므로 인쇄 작업, 작업 스케줄러, 메시지 큐, 너비 우선 탐색처럼 공정한 대기에 맞습니다.

둘 다 추상 자료형(ADT)입니다. 어떻게 저장하느냐가 아니라 어떤 연산을 제공하느냐로 정의되며, 배열이나 연결 리스트 위에 어느 쪽이든 만들 수 있습니다.

연산과 이름

예제: push와 pop을 단계별로 보기

두 자료구조에 1, 2, 3을 넣은 다음 항목 두 개를 제거합니다.

파이썬 구현

파이썬의 list는 이미 훌륭한 스택입니다. append와 pop()은 리스트의 끝에서 분할 상환 O(1)로 동작합니다. 큐에는 list.pop(0)을 쓰지 마세요. 남은 요소를 모두 이동시키므로 O(n)이 듭니다. 양쪽 끝에서 O(1)인 collections.deque를 사용하세요.

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

메서드 이름을 명확히 하고 오류 메시지도 분명하게 하고 싶다면 내장 타입을 작은 클래스로 감싸세요.

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

대표적인 스택 문제: 올바른 괄호

모든 괄호가 올바른 순서로 닫혔는지 확인하려면 여는 괄호를 만날 때마다 push합니다. 닫는 괄호를 만나면 스택의 맨 위가 그에 맞는 여는 괄호여야 합니다.

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

같은 아이디어로 후위 표기법(역폴란드 표기법) 수식을 계산하고, 재귀를 반복문으로 바꾸고, 깊이 우선 탐색을 구현할 수 있습니다. 호출 스택 대신 직접 만든 리스트를 쓰면 됩니다.

대표적인 큐 문제: 너비 우선 탐색

너비 우선 탐색은 그래프를 레벨 단위로 방문합니다. 큐를 쓰면 먼저 발견한 노드가 먼저 처리되므로 이 순서가 자연스럽게 만들어집니다.

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

시간 복잡도와 공간 복잡도

분할 상환이란, 가끔 append가 내부 배열의 크기를 조정하느라 O(n)이 들지만 많은 연산에 걸쳐 평균을 내면 연산 하나당 O(1)이라는 뜻입니다.

변형과 흔한 실수

• 덱(양방향 큐): 양쪽 끝에서 추가하고 제거합니다. collections.deque가 덱이며 스택과 큐 역할을 모두 할 수 있습니다.
• 우선순위 큐: 가장 오래된 항목이 아니라 가장 작은(또는 가장 큰) 항목을 먼저 꺼냅니다. heapq를 사용하세요. 이진 힙 페이지를 참고하세요.
• 원형 버퍼: 인덱스가 순환하는 배열에 저장하는 고정 크기 큐입니다. deque(maxlen=n)은 가득 차면 가장 오래된 항목을 버립니다.
• 스레드 안전 큐: 스레드에는 queue.Queue, 코루틴에는 asyncio.Queue가 있으며 항목을 기다리는 동안 블록됩니다.
• 스택 두 개로 만든 큐: in 스택에 push하고, out 스택이 비면 모든 항목을 옮깁니다. 각 항목은 한 번만 옮겨지므로 연산은 분할 상환 O(1)입니다.