자료구조 - 스택과 큐

스택과 큐 (LIFO, FIFO, 자료구조)

배열과 연결리스트가 데이터를 메모리에 어떻게 배치할지를 결정하는 가장 원시적인 자료구조라면, 스택과 큐는 그 위에 "어떤 순서로 들어가고 나오느냐"라는 규칙을 얹은 첫 추상 자료형(ADT, Abstract Data Type)이다. 두 구조는 자료구조 시험뿐 아니라 함수 호출 구조, BFS·DFS 같은 그래프 탐색, 메시지 큐 같은 분산 시스템의 핵심에까지 깊숙이 들어와 있어, 이 두 구조를 정확히 이해하면 이후 등장하는 거의 모든 알고리즘의 골격이 손에 잡힌다(출처: 위키백과 — Stack and queue). 본 글은 스택과 큐의 정의·구현·시간복잡도·실전 활용을 세심하게 정리한다. 제가 학교 자료구조 수업에서 처음 함수 호출 스택을 디버거로 직접 들여다본 후로는 "스택은 단순한 자료구조가 아니라 프로그래밍 언어 그 자체의 작동 원리"라는 인상을 손끝으로 받아들였다.

 

스택, 후입선출(LIFO)의 구조

스택(Stack)은 가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO, Last In First Out) 자료구조이다. 가장 좋은 비유는 책상에 쌓아 둔 책 더미인데, 새 책을 올릴 때는 맨 위에 놓고 책을 꺼낼 때도 맨 위 것부터 빼는 흐름이 정확히 스택의 동작이다. 스택이 노출하는 핵심 연산은 두 가지뿐이다. 새 원소를 맨 위에 추가하는 push와 맨 위 원소를 꺼내는 pop이며, 추가로 맨 위 원소를 꺼내지 않고 들여다보는 peek(또는 top)이 보조 연산으로 제공된다. 여기서 ADT란 데이터의 내부 구현 방식과 무관하게 외부에서 사용할 수 있는 연산의 묶음으로 자료구조를 정의하는 추상 모델을 의미한다.

스택은 배열로도 연결리스트로도 구현할 수 있으며, 두 방식 모두 push·pop·peek 세 연산이 모두 O(1)이라는 강력한 시간복잡도를 가진다. 다음은 두 구현 방식을 모두 보여 주는 파이썬 예시이다.

# 1) 배열(list) 기반 스택 — 가장 단순
stack = []
stack.append(10)     # push  → [10]
stack.append(20)     # push  → [10, 20]
stack.append(30)     # push  → [10, 20, 30]
top = stack[-1]      # peek  → 30
print(stack.pop())   # pop   → 30  (stack = [10, 20])

# 2) 연결리스트 기반 스택 — 노드 머리에 push
class Node:
    __slots__ = ("v", "next")
    def __init__(self, v): self.v, self.next = v, None

class Stack:
    def __init__(self): self.head = None
    def push(self, v):
        node = Node(v); node.next = self.head; self.head = node
    def pop(self):
        if self.head is None: raise IndexError("empty")
        v = self.head.v; self.head = self.head.next; return v
    def peek(self):
        return None if self.head is None else self.head.v

스택의 실전 활용은 의외로 광범위하다. 첫째, 모든 프로그래밍 언어의 함수 호출 구조가 정확히 스택이다. 함수가 호출되면 호출 정보(돌아갈 주소·지역 변수·매개변수)가 호출 스택에 push되고, 함수가 끝나면 pop되어 이전 함수로 복귀한다. 재귀 함수가 깊어지면 발생하는 StackOverflowError가 바로 이 호출 스택이 한계에 도달했다는 신호이다. 둘째, 괄호 짝 맞추기·후위 표기식 계산·웹 브라우저의 뒤로 가기·텍스트 에디터의 실행 취소(Undo)가 모두 스택으로 구현된다. 셋째, 그래프 탐색의 양대 산맥 중 하나인 깊이 우선 탐색(DFS)이 스택 기반으로 동작한다.

# 후위 표기식(Postfix) 계산기 — 스택의 가장 고전적인 응용
def eval_postfix(expr):
    stack = []
    for token in expr.split():
        if token in "+-*/":
            b = stack.pop(); a = stack.pop()
            stack.append(eval(f"{a}{token}{b}"))
        else:
            stack.append(int(token))
    return stack[0]

print(eval_postfix("3 4 + 5 *"))   # (3+4)*5 = 35

솔직히 제 경험상 후위 표기식 계산기 한 번 짜 보는 것이 스택을 손끝으로 이해하는 가장 빠른 길이었고, 학교 시험에서 같은 알고리즘이 다른 변형으로 출제되어도 위 8줄짜리 패턴 한 번 외워 두면 거의 자동으로 답을 작성할 수 있었다.

큐, 선입선출(FIFO)의 구조

큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First In First Out) 자료구조이다. 마트의 계산대 줄을 생각하면 정확한 비유이며, 먼저 줄을 선 사람이 먼저 계산을 마치고 떠나는 흐름이 그대로 큐의 동작이다. 큐가 노출하는 핵심 연산도 두 가지로, 맨 뒤에 원소를 추가하는 enqueue와 맨 앞 원소를 꺼내는 dequeue이며, 맨 앞 원소를 들여다보는 front(또는 peek)가 보조 연산으로 제공된다.

큐의 구현에서 가장 자주 빠지는 함정이 "배열 앞쪽에서 dequeue 할 때 O(n)이 된다"는 점이다. 파이썬 list로 큐를 만들면서 list.pop(0)을 쓰면 매 dequeue마다 뒤 원소를 한 칸씩 당기느라 O(n)이 발생한다. 이를 피하기 위해 표준 라이브러리가 제공하는 것이 양방향 큐 자료구조인 collections.deque이며, 내부적으로는 이중 연결리스트 기반의 블록 구조를 사용해 양 끝 삽입·삭제가 모두 O(1)로 동작한다(출처: Python collections — deque).

# 1) 잘못된 큐 — list.pop(0)은 O(n)
q = [1, 2, 3]
q.pop(0)            # O(n) — 1만 빠지는 것 같지만 뒤가 다 당겨짐

# 2) 표준 큐 — collections.deque
from collections import deque
q = deque()
q.append(10)        # enqueue → deque([10])
q.append(20)        # enqueue → deque([10, 20])
print(q.popleft())  # dequeue → 10, q = deque([20])
print(q[0])         # front   → 20

# 3) 연결리스트 기반 큐 — head·tail 포인터를 모두 유지
class Queue:
    def __init__(self):
        self.head = self.tail = None
    def enqueue(self, v):
        node = Node(v)
        if self.tail is None: self.head = self.tail = node
        else: self.tail.next = node; self.tail = node
    def dequeue(self):
        if self.head is None: raise IndexError("empty")
        v = self.head.v; self.head = self.head.next
        if self.head is None: self.tail = None
        return v

큐의 실전 활용 역시 폭이 매우 넓다. 첫째, 그래프 탐색의 다른 한 축인 너비 우선 탐색(BFS)이 큐 기반으로 동작한다. 둘째, 운영체제의 프로세스 스케줄링(특히 라운드 로빈)이 준비 큐(Ready Queue)에 의해 관리된다. 셋째, 메시지 큐(Kafka·RabbitMQ)·작업 큐(Celery)·비동기 이벤트 루프 같은 현대 분산 시스템의 핵심이 모두 큐 자료구조 위에서 동작한다. 넷째, 키보드 입력 버퍼·프린터 인쇄 큐·콜센터 상담사 배정 같은 일상의 흐름 제어가 모두 FIFO 규칙을 따른다.

큐에는 두 가지 변형도 자주 등장한다. 원형 큐(Circular Queue)는 고정 크기 배열의 끝과 시작을 이어붙여 사용하는 형태로, 큐가 가득 차도 앞쪽에 빈 공간이 있다면 그쪽을 재활용할 수 있어 메모리 효율이 좋다. 우선순위 큐(Priority Queue)는 FIFO가 아니라 우선순위가 높은 원소가 먼저 나가는 변형으로, 내부적으로 힙(Heap) 자료구조로 구현되며 enqueue·dequeue 모두 O(log n) 시간이 든다. 다익스트라 최단 경로 알고리즘과 작업 스케줄러가 우선순위 큐의 대표 응용이다.

시간복잡도 비교와 시험·실전 선택 가이드

스택과 큐를 함께 비교하면 다음과 같이 정리된다.

구조	규칙	push/enq	pop/deq	peek	대표 응용
스택	LIFO	O(1)	O(1)	O(1)	함수 호출·DFS·실행 취소·후위식
큐 (deque 기반)	FIFO	O(1)	O(1)	O(1)	BFS·CPU 스케줄링·메시지 큐
원형 큐	FIFO	O(1)	O(1)	O(1)	고정 크기 버퍼
우선순위 큐(힙)	우선순위	O(log n)	O(log n)	O(1)	다익스트라·작업 스케줄러

정보처리기사 시험에서 자주 등장하는 정형 답안 표현은 다음 두 문장이다. "스택은 후입선출(LIFO) 구조로 push와 pop이 같은 끝에서 일어나며, 큐는 선입선출(FIFO) 구조로 enqueue는 한 끝, dequeue는 반대 끝에서 일어난다." 시험 서술형 답안의 첫 문장으로 이 표현이 그대로 쓰일 만큼 표준화되어 있다.

실전에서 가장 자주 만나는 사고는 두 가지다. 첫째, 파이썬에서 list로 큐를 만들지 말 것. list.pop(0)의 O(n) 비용 때문에 입력 크기가 커지면 시간 초과가 곧바로 발생한다. 둘째, 재귀 함수의 깊이를 의식할 것. 호출 스택은 운영체제마다 다르지만 일반적으로 수천 단계 정도가 한계이며, 그보다 깊은 재귀가 필요한 알고리즘은 명시적 스택을 만들어 반복문으로 풀어 주는 것이 안전하다. 제가 학교 알고리즘 과제에서 가장 자주 만난 사고가 정확히 이 두 가지였고, 한 번씩 직접 부딪혀 보고 나서야 두 자료구조의 시간복잡도가 단순한 표 한 장이 아니라 운영 환경의 안전망이라는 사실을 받아들였다.

마지막으로 스택과 큐를 깊이 이해하면 그 뒤에 오는 트리·그래프·우선순위 큐·해시·LRU 캐시 같은 고급 자료구조의 학습 곡선이 눈에 띄게 부드러워진다. 이 두 구조가 곧 자료구조 학습의 첫 분기점이며, 여기서 손에 잡힌 감각이 이후 모든 자료구조의 토대가 된다는 사실을 기억해 두면 학습 우선순위를 잡기가 한결 쉬워진다.

---

메타 디스크립션: 스택(LIFO)과 큐(FIFO)의 정의·구현·시간복잡도·실전 활용을 코드 예시와 비교표로 세심하게 정리하고, 파이썬 deque·우선순위 큐 같은 변형까지 자료구조 입문자 관점에서 다룹니다.