pkglog
EN

스택과 큐: LIFO·FIFO 구현과 괄호 검사·BFS 같은 코딩 테스트 활용

작성 · · 22분 읽기 · 수정 초급 튜토리얼

이 글의 핵심

스택과 큐는 개념은 쉬운데 막상 구현하면 빈 컨테이너에서 pop하거나 list로 큐를 만들어 시간 초과가 나는 실수가 잦습니다. 언제 스택을, 언제 큐를 떠올려야 하는지 활용 패턴으로 정리하고 우선순위 큐와 덱까지 확장해, 자주 만나는 오류를 트러블슈팅 섹션에서 하나씩 해결합니다.

시리즈 안내

#02 | 📋 전체 목차 | 이전: #01 배열과 리스트 · 다음: #03 해시 테이블

들어가며

스택과 큐는 특정 순서로 데이터를 처리할 때 사용합니다. 코딩 테스트에서 매우 자주 나옵니다.

두 자료구조는 기능이 줄어든 리스트라고 볼 수 있습니다. 아무 위치나 읽고 쓰는 대신 한쪽 끝(스택) 또는 양쪽 끝(큐)만 쓰도록 제한하는 대신, 그 연산을 항상 O(1)로 만들고 “어떤 순서로 처리하는가”를 코드에 드러냅니다. 문제를 보고 “가장 최근 것을 먼저 처리해야 하는가, 먼저 온 것을 먼저 처리해야 하는가”를 물으면 어느 쪽을 쓸지 대부분 정해집니다. 이 글에서는 구현 방법을 본 뒤, 이 질문이 괄호 검사·다음 큰 수·BFS 같은 문제에서 어떻게 풀이로 이어지는지 따라갑니다.

스택 (Stack)

스택이란?

스택(Stack)은 LIFO (Last In First Out) 자료구조입니다. 나중에 들어간 것이 먼저 나옵니다. 실생활 비유:

  • 접시 쌓기: 맨 위에 놓은 접시를 먼저 꺼냄
  • 브라우저 뒤로 가기: 최근 방문 페이지부터 이동
  • 함수 호출 스택: 가장 최근 호출된 함수부터 종료
스택 동작 과정:
    push(3)        push(2)        push(1)
    ↓              ↓              ↓
                            [1]  ← top (가장 위)
                   [2]      [2]
[3]                [3]      [3]  ← bottom
    pop() → 1      pop() → 2      pop() → 3
    ↓              ↓              ↓
[2]  ← top         [3]  ← top     [] (empty)
[3]

Python 구현 (3가지 방법)

list로 스택을 만들고, collections.deque로 양끝 삽입·삭제 O(1)인 큐·스택을 쓰는 패턴이 흔합니다. 리스트·딕셔너리 등 기본 문법은 Python 자료형에서 다룹니다. Python에서 스택을 구현하는 방법입니다:

# 방법 1: list 사용 (가장 간단, 권장)
stack = []
# Python의 list는 동적 배열
# append()와 pop()이 O(1)이므로 스택으로 적합
# push: 요소 추가 (리스트 끝에 추가)
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]
print(stack)  # [1, 2, 3] (3이 top)
# pop: top 제거 및 반환
top = stack.pop()  # 마지막 요소 제거 및 반환
print(top)  # 3
print(stack)  # [1, 2] (2가 새로운 top)
# top 확인 (제거 안 함)
if stack:  # 빈 스택 체크 (len(stack) > 0과 동일)
    print(stack[-1])  # 2 (마지막 요소 = top)
    # -1 인덱스: 리스트의 마지막 요소
# empty 확인
is_empty = len(stack) == 0
print(is_empty)  # False
# 방법 2: collections.deque (더 효율적)
from collections import deque
# deque: 양쪽 끝에서 O(1) 삽입/삭제
# list보다 메모리 효율적 (대량 데이터 시)
stack = deque()
stack.append(1)  # 오른쪽에 추가
stack.append(2)
stack.append(3)
print(stack.pop())  # 3 (오른쪽에서 제거)
# 방법 3: 클래스로 구현 (명시적, 교육용)
class Stack:
    def __init__(self):
        # 내부적으로 list 사용
        self.items = []
    
    def push(self, item):
        # 스택에 요소 추가
        self.items.append(item)
    
    def pop(self):
        # 스택에서 요소 제거 및 반환
        if not self.is_empty():
            return self.items.pop()
        # 빈 스택에서 pop 시도 시 예외 발생
        raise IndexError("pop from empty stack")
    
    def top(self):
        # top 요소 확인 (제거하지 않음)
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("top from empty stack")
    
    def is_empty(self):
        # 스택이 비어있는지 확인
        return len(self.items) == 0
    
    def size(self):
        # 스택의 크기 반환
        return len(self.items)
# 사용 예시
s = Stack()
s.push(10)
s.push(20)
print(s.top())   # 20 (top 확인)
print(s.pop())   # 20 (제거 및 반환)
print(s.size())  # 1 (남은 요소 개수)

방법 선택 가이드:

  • 코딩 테스트: list 사용 (간단, 빠름)
  • 양쪽 끝을 모두 써야 할 때: deque 사용 (스택만 필요하다면 list로 충분)
  • 교육/명시적 인터페이스: 클래스 구현

list가 스택으로 충분한 이유는 끝에서의 append()와 pop()이 분할 상환 O(1)이기 때문입니다. list는 여유 공간을 미리 확보해 두고 가득 차면 더 큰 배열로 옮기는데, 이 복사가 가끔만 일어나서 한 번당 비용은 상수로 수렴합니다. 반대로 list의 앞쪽을 건드리는 insert(0, x)와 pop(0)은 나머지 원소를 모두 밀거나 당겨야 해서 O(n)입니다. 스택에는 문제가 없지만 큐에는 치명적인 이유가 여기에 있습니다.

C++ 구현

C++ 표준의 stack·queue·priority_queue는 C++ queue/stack 글에서 API와 활용(BFS/DFS 등)을 함께 정리했습니다.

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    
    // push: 요소 추가
    s.push(1);
    s.push(2);
    s.push(3);
    
    // top: top 확인 (제거 안 함)
    cout << s.top() << endl;  // 3
    
    // pop: top 제거 (반환 안 함!)
    s.pop();  // 3 제거
    
    cout << s.top() << endl;  // 2
    
    // empty: 비어있는지
    cout << s.empty() << endl;  // 0 (false)
    
    // size: 크기
    cout << s.size() << endl;  // 2
    
    return 0;
}

Python vs C++ 차이:

  • Python: pop()이 값을 반환
  • C++: pop()은 반환 안 함, top()으로 확인 후 pop() 호출

C++이 이렇게 나눈 데는 이유가 있습니다. T pop()처럼 값을 반환하면서 제거하면, 컨테이너에서 원소를 뗀 뒤 반환값을 호출자 쪽으로 복사하는 도중 예외(메모리 부족 등)가 났을 때 원소는 이미 지워졌는데 값은 전달되지 못해 데이터가 사라집니다. 읽기(top)와 제거(pop)를 나누면 복사가 실패해도 원소는 스택에 남아 있습니다. 또 하나의 차이는 빈 컨테이너 처리입니다. Python은 빈 list에서 pop()하면 IndexError: pop from empty list를 던지지만, C++의 빈 stack에서 top()이나 pop()을 호출하면 예외 없이 정의되지 않은 동작이 되어 쓰레기 값이 나오거나 크래시가 납니다. C++에서는 항상 empty()를 먼저 확인해야 합니다.

스택 연산 시간복잡도

연산설명시간복잡도PythonC++
push(x)요소 추가O(1)append(x)push(x)
pop()top 제거O(1)pop()pop()
top()top 확인O(1)[-1]top()
empty()비어있는지O(1)len() == 0empty()
size()크기O(1)len()size()

스택 사용 예시

최근에 쌓인 것부터 처리해야 할 때(뒤로 가기, 실행 취소, 괄호 짝 맞추기) 스택을 씁니다. 아래는 방문 기록과 함수 호출 순서를 리스트로 시뮬레이션한 예입니다.

# 예시 1: 브라우저 뒤로 가기
history = []
# 페이지 방문
history.append("google.com")
history.append("youtube.com")
history.append("github.com")
print(f"현재 페이지: {history[-1]}")  # github.com
# 뒤로 가기
history.pop()
print(f"현재 페이지: {history[-1]}")  # youtube.com
# 예시 2: 함수 호출 스택 시뮬레이션
call_stack = []
def func_a():
    call_stack.append("func_a")
    func_b()
    call_stack.pop()
def func_b():
    call_stack.append("func_b")
    func_c()
    call_stack.pop()
def func_c():
    call_stack.append("func_c")
    print(f"호출 스택: {call_stack}")
    # ['func_a', 'func_b', 'func_c']
    call_stack.pop()
func_a()

큐 (Queue)

큐란?

큐(Queue)는 FIFO (First In First Out) 자료구조입니다. 먼저 들어간 것이 먼저 나옵니다. 실생활 비유:

  • 줄 서기: 먼저 온 사람이 먼저 처리됨
  • 프린터 대기열: 먼저 보낸 문서가 먼저 출력
  • 콜센터 대기: 먼저 전화한 사람이 먼저 상담
큐 동작 과정:
    enqueue(1)     enqueue(2)     enqueue(3)
    ↓              ↓              ↓
[1]                [1][2]         [1][2][3]
 ↑                  ↑              ↑     ↑
front              front          front  rear
    dequeue() → 1  dequeue() → 2  dequeue() → 3
    ↓              ↓              ↓
[2][3]             [3]            [] (empty)
 ↑                  ↑
front              front

Python 구현 (2가지 방법)

Python에서 큐를 구현하는 방법입니다:

# 방법 1: collections.deque 사용 (권장)
from collections import deque
# deque: double-ended queue (양방향 큐)
# 양쪽 끝에서 O(1) 삽입/삭제 가능
queue = deque()
# enqueue: 뒤에 추가 (rear에 삽입)
queue.append(1)  # deque([1])
queue.append(2)  # deque([1, 2])
queue.append(3)  # deque([1, 2, 3])
print(queue)  # deque([1, 2, 3])
# 1이 front (앞), 3이 rear (뒤)
# dequeue: 앞에서 제거 및 반환 (front에서 제거)
front = queue.popleft()  # O(1) - 효율적!
# popleft(): 왼쪽(앞)에서 제거
print(front)  # 1
print(queue)  # deque([2, 3])
# front 확인 (제거 안 함)
if queue:  # 빈 큐 체크 (len(queue) > 0과 동일)
    print(queue[0])  # 2 (첫 번째 요소 = front)
# empty 확인
is_empty = len(queue) == 0
print(is_empty)  # False
# ❌ 방법 2: list 사용 (비효율적, 절대 비권장)
queue_list = []
queue_list.append(1)  # [1]
queue_list.append(2)  # [1, 2]
queue_list.append(3)  # [1, 2, 3]
# pop(0)은 O(n)! (매우 느림)
front = queue_list.pop(0)  # 첫 요소 제거
print(front)  # 1
# 왜 느릴까?
# [1, 2, 3] → pop(0) → [2, 3]
# 
# 내부 동작:
# 1. 인덱스 0의 요소(1) 제거
# 2. 나머지 요소들을 한 칸씩 앞으로 이동
#    [2, 3]을 [0], [1] 위치로 복사
# 3. 배열 크기 조정
# 
# 시간 복잡도: O(n) - 요소 개수만큼 이동 필요
# n=100,000이면 100,000번 복사!

deque의 추가 기능:

from collections import deque
q = deque([1, 2, 3])
# 왼쪽에 추가 (스택으로도 사용 가능)
q.appendleft(0)  # deque([0, 1, 2, 3])
# 오른쪽에서 제거 (스택처럼)
q.pop()  # 3
# 양방향 큐로 활용
# appendleft() + pop() = 스택 (왼쪽)
# append() + popleft() = 큐 (일반)

deque vs list 성능 비교:

import time
from collections import deque
# deque (O(1))
q = deque(range(100000))
start = time.time()
for _ in range(10000):
    q.popleft()
print(f"deque: {time.time() - start:.4f}초")  # 약 0.001초
# list (O(n))
q = list(range(100000))
start = time.time()
for _ in range(10000):
    q.pop(0)
print(f"list: {time.time() - start:.4f}초")  # 약 5초 (5000배 느림!)

위 비교 결과가 큰 차이로 나오는 이유는 list.pop(0)이 지운 자리를 메우려고 나머지 원소 전체를 한 칸씩 앞으로 복사하기 때문입니다. 원소가 10만 개면 한 번 꺼낼 때마다 10만 개를 옮기는 셈입니다. deque는 고정 크기 블록을 이중 연결 리스트처럼 이어 붙인 구조라 양쪽 끝의 삽입·삭제가 원소 이동 없이 O(1)입니다. 대신 deque[i]처럼 중간 원소를 인덱스로 접근하면 O(n)이므로, 무작위 접근이 필요하다면 list가 낫습니다. 제가 BFS 문제에서 “로직은 맞는데 시간 초과”인 코드를 받으면 가장 먼저 확인하는 것이 queue.pop(0)입니다.

C++ 구현

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    
    // push: 뒤에 추가
    q.push(1);
    q.push(2);
    q.push(3);
    
    // front: 앞 요소 확인 (제거 안 함)
    cout << q.front() << endl;  // 1
    
    // back: 뒤 요소 확인
    cout << q.back() << endl;  // 3
    
    // pop: 앞에서 제거 (반환 안 함!)
    q.pop();  // 1 제거
    
    cout << q.front() << endl;  // 2
    
    // empty: 비어있는지
    cout << q.empty() << endl;  // 0 (false)
    
    // size: 크기
    cout << q.size() << endl;  // 2
    
    return 0;
}

큐 연산 시간복잡도

연산설명시간복잡도Python (deque)C++
enqueue(x)뒤에 추가O(1)append(x)push(x)
dequeue()앞에서 제거O(1)popleft()pop()
front()앞 요소 확인O(1)[0]front()
back()뒤 요소 확인O(1)[-1]back()
empty()비어있는지O(1)len() == 0empty()
size()크기O(1)len()size()

실전 문제 풀이

문제 1: 괄호 검사

def is_valid_parentheses(s):
    """
    괄호가 올바른지 검사
    "(())" → True
    "(()" → False
    """
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:  # 여는 괄호
            stack.append(char)
        else:  # 닫는 괄호
            if not stack:
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0
# 테스트
print(is_valid_parentheses("()"))        # True
print(is_valid_parentheses("()[]{}"))    # True
print(is_valid_parentheses("(]"))        # False
print(is_valid_parentheses("([)]"))      # False
print(is_valid_parentheses("{[]}"))      # True
print(is_valid_parentheses("((()"))      # False

괄호 검사에서 스택이 자연스러운 이유는 “가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다”는 규칙이 LIFO 그 자체이기 때문입니다. 흔한 실수는 두 가지입니다. 닫는 괄호를 만났는데 스택이 비어 있는 경우(")("처럼 닫는 것이 먼저 오는 입력)를 확인하지 않아 빈 스택에서 꺼내다 에러가 나는 것, 그리고 반복이 끝난 뒤 스택에 남은 여는 괄호가 있는지("(()") 확인하지 않는 것입니다. 둘 다 짝이 맞지 않는 입력인데, 테스트 예제가 짝이 맞는 입력 위주라서 놓치기 쉽습니다.

동작 과정 추적 (입력: "([{}])"):

# 초기: stack = []
# char='(': 여는 괄호 → push
# stack = ['(']
# char='[': 여는 괄호 → push
# stack = ['(', '[']
# char='{': 여는 괄호 → push
# stack = ['(', '[', '{']
# char='}': 닫는 괄호
# pop() → '{', pairs['{'] = '}' == '}' ✓
# stack = ['(', '[']
# char=']': 닫는 괄호
# pop() → '[', pairs['['] = ']' == ']' ✓
# stack = ['(']
# char=')': 닫는 괄호
# pop() → '(', pairs['('] = ')' == ')' ✓
# stack = []
# 최종: stack이 비어있음 → True

C++ 풀이:

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {'(', ')'}, {'{', '}'}, {'[', ']'}
    };
    
    for (char c : s) {
        if (pairs.count(c)) {  // 여는 괄호
            st.push(c);
        } else {  // 닫는 괄호
            if (st.empty()) return false;
            
            char opening = st.top();
            st.pop();
            
            if (pairs[opening] != c) return false;
        }
    }
    
    return st.empty();
}
int main() {
    cout << isValid("()") << endl;        // 1 (true)
    cout << isValid("()[]{}") << endl;    // 1
    cout << isValid("(]") << endl;        // 0 (false)
    cout << isValid("([)]") << endl;      // 0
    return 0;
}

문제 2: 스택으로 큐 구현 (Implement Queue using Stacks)

문제: 두 개의 스택을 사용하여 큐를 구현하세요. 아이디어:

  • stack_in: enqueue 전용
  • stack_out: dequeue 전용
  • dequeue 시 stack_out이 비어있으면 stack_in의 모든 요소를 옮김 Python 풀이:
class QueueUsingStacks:
    """
    두 개의 스택으로 큐 구현
    """
    def __init__(self):
        self.stack_in = []   # enqueue용
        self.stack_out = []  # dequeue용
    
    def enqueue(self, x):
        """
        뒤에 추가 - O(1)
        """
        self.stack_in.append(x)
    
    def dequeue(self):
        """
        앞에서 제거 - 분할 상환(여러 번 연산의 평균 비용으로 보는 방식) O(1)
        """
        # stack_out이 비어있으면 stack_in에서 옮김
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out.pop() if self.stack_out else None
    
    def front(self):
        """
        앞 요소 확인 - 분할 상환 O(1)
        """
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out[-1] if self.stack_out else None
    
    def is_empty(self):
        return not self.stack_in and not self.stack_out
# 테스트
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.front())    # 2
print(q.dequeue())  # 2
print(q.dequeue())  # 3
print(q.is_empty())  # True

이 구현에서 dequeue 한 번은 최악의 경우 stack_in의 원소를 전부 옮기므로 O(n)이지만, 분할 상환하면 O(1)입니다. 원소 하나에 주목하면 stack_in에 한 번 들어가고, stack_out으로 한 번 옮겨지고, 한 번 꺼내질 뿐이라 원소 하나가 겪는 연산은 총 3번으로 정해져 있기 때문입니다. 중요한 조건은 stack_out이 비었을 때만 옮긴다는 것입니다. dequeue할 때마다 무조건 옮겼다가 다시 돌려놓는 식으로 구현하면 매번 O(n)이 되어 이 성질이 깨집니다.

동작 과정 추적:

# enqueue(1), enqueue(2), enqueue(3)
# stack_in = [1, 2, 3]
# stack_out = []
# dequeue() 호출
# stack_out이 비어있음 → stack_in에서 옮김
# stack_in = [] (모두 pop)
# stack_out = [3, 2, 1] (역순으로 push)
# stack_out.pop() → 1 반환
# stack_out = [3, 2]
# front() 호출
# stack_out이 비어있지 않음 → 그대로 사용
# stack_out[-1] → 2 반환
# dequeue() 호출
# stack_out.pop() → 2 반환
# stack_out = [3]

문제 3: 다음 큰 수 (Next Greater Element)

문제: 각 원소의 오른쪽에서 처음 나오는 더 큰 수를 찾으세요. 예시:

  • [4, 5, 2, 10] → [5, 10, 10, -1]
  • [1, 2, 3, 4] → [2, 3, 4, -1] 접근 방법:
  1. 스택에 인덱스를 저장
  2. 현재 값이 스택 top의 값보다 크면, 스택에서 pop하며 정답 갱신
  3. 현재 인덱스를 스택에 push Python 풀이:
def next_greater_element(arr):
    """
    각 원소의 오른쪽에서 처음 나오는 큰 수
    시간복잡도: O(n)
    공간복잡도: O(n)
    """
    n = len(arr)
    result = [-1] * n  # 기본값 -1 (큰 수 없음)
    stack = []  # 인덱스 저장
    
    for i in range(n):
        # 현재 값이 스택 top의 값보다 크면
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]  # 정답 갱신
        
        stack.append(i)  # 현재 인덱스 push
    
    return result
# 테스트
arr = [4, 5, 2, 10, 8]
print(next_greater_element(arr))
# [5, 10, 10, -1, -1]
# 설명:
# arr[0]=4 → 오른쪽에서 처음 큰 수는 5
# arr[1]=5 → 오른쪽에서 처음 큰 수는 10
# arr[2]=2 → 오른쪽에서 처음 큰 수는 10
# arr[3]=10 → 오른쪽에 큰 수 없음 (-1)
# arr[4]=8 → 오른쪽에 큰 수 없음 (-1)

이 기법을 단조 스택(monotonic stack)이라고 부릅니다. 스택에는 “아직 자기보다 큰 수를 만나지 못한 원소들”만 남고, 그 값들은 아래에서 위로 갈수록 감소하는 순서를 유지합니다. 새 값이 들어오면 그보다 작은 원소들이 차례로 꺼내지며 정답이 확정됩니다. 반복문 안에 while이 있어 O(n²)처럼 보이지만, 각 인덱스는 스택에 한 번 들어가고 한 번 나오므로 전체는 O(n)입니다. 스택에 값 대신 인덱스를 넣는 이유는 정답을 원래 위치에 기록해야 하기 때문이며, 같은 구조가 “주식 가격”, “히스토그램에서 가장 큰 직사각형”, “오큰수”(백준 17298) 같은 문제에 그대로 쓰입니다.

동작 과정 추적 (입력: [4, 5, 2, 10]):

# 초기: stack = [], result = [-1, -1, -1, -1]
# i=0, arr[0]=4
# stack = [] (비어있음)
# stack.append(0) → stack = [0]
# i=1, arr[1]=5
# arr[stack[-1]] = arr[0] = 4 < 5 → pop
# result[0] = 5 → result = [5, -1, -1, -1]
# stack = []
# stack.append(1) → stack = [1]
# i=2, arr[2]=2
# arr[stack[-1]] = arr[1] = 5 > 2 → pop 안 함
# stack.append(2) → stack = [1, 2]
# i=3, arr[3]=10
# arr[stack[-1]] = arr[2] = 2 < 10 → pop
# result[2] = 10 → result = [5, -1, 10, -1]
# arr[stack[-1]] = arr[1] = 5 < 10 → pop
# result[1] = 10 → result = [5, 10, 10, -1]
# stack = []
# stack.append(3) → stack = [3]
# 최종: result = [5, 10, 10, -1]

문제 4: BFS (너비 우선 탐색)

문제: 그래프를 BFS로 순회하세요. Python 풀이:

from collections import deque
def bfs(graph, start):
    """
    BFS로 그래프 순회
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()  # 큐에서 꺼냄
        result.append(node)
        
        # 인접 노드 방문
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result
# 테스트
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs(graph, 'A'))
# ['A', 'B', 'C', 'D', 'E', 'F']

동작 과정:

# 초기: queue = ['A'], visited = {'A'}
# 1. 'A' 방문
# queue = ['B', 'C'], visited = {'A', 'B', 'C'}
# 2. 'B' 방문
# queue = ['C', 'D', 'E'], visited = {'A', 'B', 'C', 'D', 'E'}
# 3. 'C' 방문
# queue = ['D', 'E', 'F'], visited = {'A', 'B', 'C', 'D', 'E', 'F'}
# 4. 'D' 방문 (인접 노드 모두 방문됨)
# queue = ['E', 'F']
# 5. 'E' 방문 (인접 노드 모두 방문됨)
# queue = ['F']
# 6. 'F' 방문 (인접 노드 모두 방문됨)
# queue = []
# 최종: ['A', 'B', 'C', 'D', 'E', 'F']

실전 팁과 활용 패턴

스택 활용 패턴

1. 괄호/태그 매칭

  • HTML/XML 태그 검증
  • 수식 괄호 검사
  • 컴파일러 구문 분석 2. 계산기 (후위 표기식)
  • 중위 표기식 → 후위 표기식 변환
  • 후위 표기식 계산 3. 함수 호출 스택
  • 재귀 함수 시뮬레이션
  • 콜 스택 추적 4. DFS (깊이 우선 탐색)
  • 그래프 순회
  • 미로 탐색 5. 되돌리기 (Undo)
  • 텍스트 에디터
  • 게임 상태 복원
# 예시: 간단한 Undo 시스템
class TextEditor:
    def __init__(self):
        self.text = ""
        self.history = []  # 스택
    
    def write(self, text):
        self.history.append(self.text)  # 현재 상태 저장
        self.text += text
    
    def undo(self):
        if self.history:
            self.text = self.history.pop()  # 이전 상태 복원
editor = TextEditor()
editor.write("Hello")
editor.write(" World")
print(editor.text)  # Hello World
editor.undo()
print(editor.text)  # Hello
editor.undo()
print(editor.text)  # (빈 문자열)

큐 활용 패턴

1. BFS (너비 우선 탐색)

  • 최단 경로 찾기
  • 레벨 순회 2. 프린터 대기열
  • 작업 순서 관리 3. 프로세스 스케줄링
  • 라운드 로빈 스케줄링 4. 캐시 (LRU)
  • 최근 사용 항목 추적 5. 레벨 순회 (트리)
  • 트리의 각 레벨별 처리
# 예시: 프린터 대기열
from collections import deque
class PrinterQueue:
    def __init__(self):
        self.queue = deque()
    
    def add_job(self, job):
        self.queue.append(job)
        print(f"작업 추가: {job}")
    
    def process_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"작업 처리: {job}")
            return job
        else:
            print("대기 중인 작업 없음")
            return None
printer = PrinterQueue()
printer.add_job("문서1.pdf")
printer.add_job("문서2.pdf")
printer.add_job("문서3.pdf")
printer.process_job()  # 문서1.pdf 처리
printer.process_job()  # 문서2.pdf 처리

스택 vs 큐 선택 가이드

상황자료구조이유
최근 항목 먼저 처리스택LIFO
순서대로 처리큐FIFO
괄호 검사스택가장 최근 여는 괄호와 매칭
BFS큐레벨별 순회
DFS스택깊이 우선 탐색
Undo/Redo스택최근 작업부터 취소

고급 주제

우선순위 큐 (Priority Queue)

우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 큐입니다.

import heapq
# 최소 힙 (기본)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
print(heapq.heappop(pq))  # 1 (가장 작은 값)
print(heapq.heappop(pq))  # 2
print(heapq.heappop(pq))  # 3
# 최대 힙 (음수 사용)
pq = []
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
heapq.heappush(pq, -2)
print(-heapq.heappop(pq))  # 3 (가장 큰 값)
print(-heapq.heappop(pq))  # 2
print(-heapq.heappop(pq))  # 1

C++ 우선순위 큐:

#include <queue>
#include <iostream>
using namespace std;
int main() {
    // 최대 힙 (기본)
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    
    cout << pq.top() << endl;  // 3 (가장 큰 값)
    pq.pop();
    cout << pq.top() << endl;  // 2
    
    // 최소 힙
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(3);
    min_pq.push(1);
    min_pq.push(2);
    
    cout << min_pq.top() << endl;  // 1 (가장 작은 값)
    
    return 0;
}

덱 (Deque) - 양방향 큐

덱(Deque)은 양쪽 끝에서 삽입/삭제가 가능한 자료구조입니다.

from collections import deque
dq = deque([1, 2, 3])
# 뒤에 추가/제거
dq.append(4)        # [1, 2, 3, 4]
dq.pop()            # 4 제거 → [1, 2, 3]
# 앞에 추가/제거
dq.appendleft(0)    # [0, 1, 2, 3]
dq.popleft()        # 0 제거 → [1, 2, 3]
# 양쪽 확인
print(dq[0])   # 1 (front)
print(dq[-1])  # 3 (back)
# 회전
dq.rotate(1)   # 오른쪽으로 1칸 → [3, 1, 2]
dq.rotate(-1)  # 왼쪽으로 1칸 → [1, 2, 3]

C++ 덱:

#include <deque>
#include <iostream>
using namespace std;
int main() {
    deque<int> dq = {1, 2, 3};
    
    // 뒤에 추가/제거
    dq.push_back(4);   // [1, 2, 3, 4]
    dq.pop_back();     // [1, 2, 3]
    
    // 앞에 추가/제거
    dq.push_front(0);  // [0, 1, 2, 3]
    dq.pop_front();    // [1, 2, 3]
    
    // 양쪽 확인
    cout << dq.front() << endl;  // 1
    cout << dq.back() << endl;   // 3
    
    // 인덱싱
    cout << dq[1] << endl;  // 2
    
    return 0;
}

활용 패턴 한눈에 보기

스택 활용 패턴 상세

패턴설명예시
괄호/태그 매칭여는 것과 닫는 것 짝 맞추기HTML, JSON, 수식
계산기후위 표기식 계산3 4 + 2 * → 14
함수 호출 스택재귀 시뮬레이션DFS, 백트래킹
되돌리기최근 작업 취소Ctrl+Z
경로 추적이전 상태 기억미로 탐색

큐 활용 패턴 상세

패턴설명예시
BFS레벨별 순회최단 경로, 트리 레벨
작업 대기열순서대로 처리프린터, 콜센터
스케줄링라운드 로빈CPU 스케줄러
슬라이딩 윈도우고정 크기 윈도우최근 N개 항목
스트림 처리순차 데이터 처리로그 분석

트러블슈팅

문제 1: 빈 스택/큐에서 pop

# ❌ 에러 발생
stack = []
# stack.pop()  # IndexError: pop from empty list
# ✅ 해결: 빈 상태 체크
if stack:
    value = stack.pop()
else:
    print("스택이 비어있습니다")
# ✅ 또는 예외 처리
try:
    value = stack.pop()
except IndexError:
    print("스택이 비어있습니다")

문제 2: list로 큐 구현 (성능 문제)

# ❌ 비효율적
queue = []
queue.append(1)
queue.pop(0)  # O(n)!
# ✅ 효율적
from collections import deque
queue = deque()
queue.append(1)
queue.popleft()  # O(1)

문제 3: C++ stack/queue의 pop() 반환값 없음

// ❌ 에러: pop()은 void
// int value = stack.pop();  // 컴파일 에러
// ✅ 올바른 방법
int value = stack.top();  // 값 확인
stack.pop();              // 제거

스택과 큐를 가르는 기준

문제에서 “가장 최근 것부터 되돌린다”는 구조(괄호 짝 맞추기, 실행 취소, 되돌아가며 탐색하는 DFS)가 보이면 스택이고, “먼저 들어온 것부터 처리한다”는 구조(BFS, 작업 대기열, 순서대로 도는 시뮬레이션)가 보이면 큐입니다.

Python에서 가장 흔한 실수는 큐를 list로 만들고 pop(0)으로 꺼내는 것입니다. 매번 나머지 원소를 앞으로 당기느라 O(n)이 걸려서, 작은 예제에서는 멀쩡하던 BFS가 큰 입력에서 시간 초과가 납니다. 큐는 처음부터 collections.deque와 popleft()로 작성하는 것이 안전합니다. 다음 글인 해시 테이블에 이어, 큐는 BFS/DFS에서 다시 핵심 도구로 쓰입니다.

자주 묻는 질문 (FAQ)

Q. C++에서 int v = st.pop();이 컴파일 에러가 나는 이유는 무엇인가요?

A. C++의 std::stack과 std::queue의 pop()은 반환형이 void라서 값을 돌려주지 않습니다. 값이 필요하면 stack은 top(), queue는 front()로 먼저 꺼내 본 다음 pop()으로 제거해야 합니다. Python의 list.pop()이나 deque.popleft()는 값을 반환하므로, 두 언어를 오가며 풀 때 자주 헷갈리는 부분입니다.

같이 보면 좋은 글