스택과 큐의 차이는?

스택은 LIFO(후입선출), 큐는 FIFO(선입선출)입니다. 스택은 접시 쌓기, 큐는 줄 서기.

스택은 언제 쓰나요?

괄호 검사, 함수 호출, 되돌리기(Undo), DFS 등에 사용합니다.

Python에서 스택/큐 구현은?

스택은 list, 큐는 collections.deque를 사용하세요.

[2026] 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리

Q: 큐는 언제 쓰나요?

BFS, 프린터 대기열, 작업 스케줄링 등 순서가 중요한 곳에 사용합니다.

2026년 3월 28일 · 18분 읽기 · 수정 2026년 4월 7일 초급 튜토리얼

이 글의 핵심

스택과 큐: 코딩 테스트 필수 자료구조 스택 (Stack)·큐 (Queue).

🎯 이 글을 읽으면 (읽는 시간: 18분)

TL;DR: 코딩 테스트 필수 자료구조인 스택(LIFO)과 큐(FIFO)를 완벽하게 마스터합니다. 괄호 검사, BFS/DFS, 작업 스케줄링 등 실전 문제를 풀 수 있는 능력을 습득합니다. 이 글을 읽으면:

✅ 스택(LIFO)과 큐(FIFO) 동작 원리 완벽 이해
✅ Python/C++로 스택/큐 구현 및 활용
✅ 괄호 검사, BFS 등 실전 패턴 마스터 실무 활용:
🔥 괄호/태그 유효성 검사
🔥 함수 호출 스택, Undo/Redo
🔥 작업 큐, 프린터 대기열 난이도: 초급 | 실습 문제: 6개 | Python + C++: 모두 포함

들어가며

”스택과 큐는 언제 쓰나요?”

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

스택 (LIFO)
큐 (FIFO)
구현 방법
실전 문제 풀이

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

1. 스택 (Stack)

스택이란?

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

접시 쌓기: 맨 위에 놓은 접시를 먼저 꺼냄
브라우저 뒤로 가기: 최근 방문 페이지부터 이동
함수 호출 스택: 가장 최근 호출된 함수부터 종료 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

스택 동작 과정:
    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에서 스택을 구현하는 방법입니다: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 방법 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 사용 (메모리 효율)
교육/명시적 인터페이스: 클래스 구현

C++ 구현

C++ 표준의 stack·queue·priority_queue는 C++ queue/stack 글에서 API와 활용(BFS/DFS 등)을 함께 정리했습니다. 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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() 호출

스택 연산 시간복잡도

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

스택 사용 예시

최근에 쌓인 것부터 처리해야 할 때(뒤로 가기, 실행 취소, 괄호 짝 맞추기) 스택을 씁니다. 아래는 방문 기록과 함수 호출 순서를 리스트로 시뮬레이션한 예입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예시 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()

2. 큐 (Queue)

큐란?

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

줄 서기: 먼저 온 사람이 먼저 처리됨
프린터 대기열: 먼저 보낸 문서가 먼저 출력
콜센터 대기: 먼저 전화한 사람이 먼저 상담 아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

큐 동작 과정:
    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에서 큐를 구현하는 방법입니다: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 방법 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의 추가 기능: 아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 성능 비교: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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배 느림!)

C++ 구현

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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() == 0`	`empty()`
size()	크기	O(1)	`len()`	`size()`

3. 실전 문제 풀이

문제 1: 괄호 검사

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

동작 과정 추적 (입력: "([{}])"): 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 초기: 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++ 풀이: 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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 풀이: 다음은 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

동작 과정 추적: 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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] 접근 방법:

스택에 인덱스를 저장
현재 값이 스택 top의 값보다 크면, 스택에서 pop하며 정답 갱신
현재 인덱스를 스택에 push Python 풀이: 다음은 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)

동작 과정 추적 (입력: [4, 5, 2, 10]): 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 초기: 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 풀이: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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']

동작 과정: 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 초기: 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']

4. 실전 팁과 활용 패턴

스택 활용 패턴

1. 괄호/태그 매칭

HTML/XML 태그 검증
수식 괄호 검사
컴파일러 구문 분석 2. 계산기 (후위 표기식)
중위 표기식 → 후위 표기식 변환
후위 표기식 계산 3. 함수 호출 스택
재귀 함수 시뮬레이션
콜 스택 추적 4. DFS (깊이 우선 탐색)
그래프 순회
미로 탐색 5. 되돌리기 (Undo)
텍스트 에디터
게임 상태 복원 다음은 python를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예시: 간단한 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. 레벨 순회 (트리)
트리의 각 레벨별 처리 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 예시: 프린터 대기열
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	스택	최근 작업부터 취소

5. 고급 주제

우선순위 큐 (Priority Queue)

우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 큐입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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++ 우선순위 큐: 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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)은 양쪽 끝에서 삽입/삭제가 가능한 자료구조입니다. 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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++ 덱: 다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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;
}

6. 실전 팁과 활용 패턴

스택 활용 패턴 상세

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

큐 활용 패턴 상세

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

7. 트러블슈팅

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

다음은 python를 활용한 상세한 구현 코드입니다. 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

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

아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 비효율적
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() 반환값 없음

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

[2026] 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리

이 글의 핵심

🎯 이 글을 읽으면 (읽는 시간: 18분)

들어가며

”스택과 큐는 언제 쓰나요?”

코딩 테스트 준비하며 깨달은 것

1. 스택 (Stack)

스택이란?

Python 구현 (3가지 방법)

C++ 구현

스택 연산 시간복잡도

스택 사용 예시

2. 큐 (Queue)

큐란?

Python 구현 (2가지 방법)

C++ 구현

큐 연산 시간복잡도

3. 실전 문제 풀이

문제 1: 괄호 검사

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

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

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

4. 실전 팁과 활용 패턴

스택 활용 패턴

큐 활용 패턴

스택 vs 큐 선택 가이드

5. 고급 주제

우선순위 큐 (Priority Queue)

덱 (Deque) - 양방향 큐

6. 실전 팁과 활용 패턴

스택 활용 패턴 상세

큐 활용 패턴 상세

7. 트러블슈팅

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

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

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

정리

핵심 요약

다음 단계

관련 글