스택과 큐, LIFO·FIFO 차이와 실무 쓰임새
스택은 나중에 넣은 값부터 꺼내는 후입선출(LIFO), 큐는 먼저 넣은 값부터 꺼내는 선입선출(FIFO) 구조다. 파이썬·자바 공식 문서 기준 표준 구현과 콜 스택·BFS 같은 실무 쓰임, 흔한 성능 함정을 정리했다.
스택(stack)은 나중에 넣은 데이터가 먼저 나오는 후입선출(LIFO, Last In First Out) 구조다. 큐(queue)는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO, First In First Out) 구조다. 스택은 함수 호출 관리와 실행 취소(undo), 괄호 짝 검사에 쓰고 큐는 작업 대기열과 너비 우선 탐색, 데이터 버퍼에 쓴다. 이 글은 두 구조의 동작 원리와 파이썬·자바 공식 문서가 권장하는 표준 구현, 현업에서 둘 중 어느 쪽을 언제 고르는지를 다룬다. 코딩 테스트 풀이 요령이나 멀티스레드 환경의 동시성 큐(concurrent queue)는 범위 밖이다.
스택과 큐는 무엇이 다른가
차이는 데이터를 꺼내는 순서 하나로 갈린다. 스택은 가장 최근에 넣은 값부터, 큐는 가장 오래전에 넣은 값부터 꺼낸다. 접시를 쌓았다 위에서부터 집는 모습이 스택이고, 매표소 줄처럼 뒤로 서서 앞에서 빠져나가는 모습이 큐다.
둘 다 데이터를 한 줄로 세워 두지만 입구와 출구의 위치가 다르다. 스택은 넣는 곳과 빼는 곳이 맨 위(top) 하나로 같고, 큐는 맨 뒤(rear)로 넣어 맨 앞(front)으로 뺀다.
| 구분 | 스택 | 큐 |
|---|---|---|
| 처리 순서 | 후입선출(LIFO) | 선입선출(FIFO) |
| 넣는 위치 | 맨 위(top) | 맨 뒤(rear) |
| 빼는 위치 | 맨 위(top) | 맨 앞(front) |
| 기본 연산 | push / pop | enqueue / dequeue |
| 대표 용도 | 콜 스택, 실행 취소 | 작업 큐, BFS |
스택은 실무에서 어디에 쓰나
가장 가까운 예는 프로그램이 함수 호출을 관리하는 콜 스택(call stack)이다. 함수 A가 B를 부르면 B의 지역 변수와 돌아갈 위치가 스택에 쌓이고, B가 끝나면 그 정보가 맨 위에서 제거되며 실행이 A로 돌아온다. 재귀 호출이 너무 깊어 이 공간이 넘치면 스택 오버플로(stack overflow) 오류가 난다.
편집기의 실행 취소도 스택이다. 방금 한 동작을 맨 위에 쌓아 두었다가 되돌리기를 누르면 가장 최근 동작부터 꺼내 되돌린다. 여는 괄호를 만나면 push하고 닫는 괄호를 만나면 pop해서 짝을 맞추는 괄호 검사, 후위 표기 수식 계산, 브라우저 뒤로 가기도 같은 원리다. push와 pop이 맨 위에서만 일어나므로 두 연산 모두 O(1)에 끝난다.
큐는 실무에서 어디에 쓰나
큐는 들어온 순서를 지켜 하나씩 처리해야 할 때 쓴다. 대표적인 곳이 작업 큐(work queue)와 메시지 큐다. 요청을 받은 순서대로 큐에 쌓아 두고 워커가 앞에서부터 꺼내 처리하면 먼저 온 요청이 먼저 끝난다.
그래프를 너비 우선으로 훑는 탐색(BFS)도 큐가 핵심이다. 방문할 노드를 큐에 넣고 앞에서 꺼내며 이웃을 다시 큐에 넣으면 가까운 노드부터 차례로 방문한다. 노드와 엣지로 실행 흐름을 짜는 그래프 오케스트레이션에서도 방문 대기 노드를 큐에 담아 같은 방식으로 훑는다. 프린터 대기열, 입출력 버퍼, 순서를 보장해야 하는 이벤트 처리도 모두 큐다.
파이썬과 자바에서는 어떻게 구현하나
파이썬에서 스택은 리스트로 충분하다. append()로 넣고 pop()으로 맨 뒤를 꺼내면 그대로 LIFO가 된다. 문제는 큐다. 리스트로 큐를 만들어 맨 앞을 빼는 list.pop(0)을 쓰면 뒤 원소를 전부 한 칸씩 당겨야 해서 O(n)이 걸린다. 파이썬 공식 문서의 collections 모듈 설명은 양쪽 끝 삽입·삭제가 모두 O(1)인 deque를 큐로 쓰라고 안내한다.
from collections import deque
# 스택: 리스트로 충분하다
stack = []
stack.append(1) # push
stack.append(2)
print(stack.pop()) # 2 (마지막에 넣은 값)
# 큐: deque로 앞에서 빼면 O(1)
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft()) # 1 (먼저 넣은 값)자바는 스택도 큐도 ArrayDeque 하나로 해결된다. 오라클 자바 공식 문서의 Deque 인터페이스 설명은 레거시 Stack 클래스보다 Deque를 우선 쓰라고 명시한다. Stack은 JDK 1.0 시절 Vector를 상속해 모든 연산에 동기화 락이 걸리는데, 단일 스레드에서는 불필요한 비용이다. 같은 문서는 ArrayDeque가 스택으로 쓰면 Stack보다, 큐로 쓰면 LinkedList보다 빠르다고 설명한다.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll()); // 1고를 때 흔히 놓치는 것
먼저 큐가 필요한 자리에 배열이나 리스트의 맨 앞을 반복해서 빼는 코드를 쓰지 않는다. 데이터가 많아질수록 앞에서 빼는 비용이 O(n)으로 쌓여 느려진다. 파이썬은 deque.popleft(), 자바는 ArrayDeque.poll()로 이 비용을 O(1)로 줄인다.
자바 새 코드에서는 java.util.Stack을 쓰지 않는다. 앞서 인용한 오라클 문서 권고대로 ArrayDeque를 스택으로 쓴다. 스택을 쓰는 재귀에 깊이 한계가 있다는 점도 기억한다. CPython의 기본 재귀 한도는 1000이며 sys.setrecursionlimit()로 조정하는데, 무작정 늘리기보다 깊은 재귀는 명시적 스택이나 반복문으로 바꾸는 편이 안전하다.
마지막으로 순서와 우선순위를 헷갈리지 않는다. 들어온 순서가 아니라 중요도 순으로 꺼내야 한다면 순수 큐가 아니라 우선순위 큐(힙)를 써야 한다. 스택과 큐는 순서를 다루는 가장 기본 도구이고, 그 위에 우선순위 큐나 덱(deque) 같은 변형이 얹힌다.
