스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
이 글의 핵심
스택과 큐에 대한 실전 가이드입니다. 코딩 테스트 필수 자료구조 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”스택과 큐는 언제 쓰나요?”
스택과 큐는 특정 순서로 데이터를 처리할 때 사용합니다. 코딩 테스트에서 매우 자주 나옵니다.
이 글에서 다루는 것:
- 스택 (LIFO)
- 큐 (FIFO)
- 구현 방법
- 실전 문제 풀이
1. 스택 (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사용 (메모리 효율) - 교육/명시적 인터페이스: 클래스 구현
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()호출
스택 연산 시간복잡도
| 연산 | 설명 | 시간복잡도 | 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() |
스택 사용 예시
최근에 쌓인 것부터 처리해야 할 때(뒤로 가기, 실행 취소, 괄호 짝 맞추기) 스택을 씁니다. 아래는 방문 기록과 함수 호출 순서를 리스트로 시뮬레이션한 예입니다.
# 예시 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) 자료구조입니다. 먼저 들어간 것이 먼저 나옵니다.
실생활 비유:
- 줄 서기: 먼저 온 사람이 먼저 처리됨
- 프린터 대기열: 먼저 보낸 문서가 먼저 출력
- 콜센터 대기: 먼저 전화한 사람이 먼저 상담
큐 동작 과정:
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 frontPython 구현 (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배 느림!)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() == 0 | empty() |
| size() | 크기 | O(1) | len() | size() |
3. 실전 문제 풀이
문제 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동작 과정 추적 (입력: "([{}])"):
# 초기: stack = []
# char='(': 여는 괄호 → push
# stack = ['(']
# char='[': 여는 괄호 → push
# stack = ['(', '[']
# char='{': 여는 괄호 → push
# stack = ['(', '[', '{']
# char='}': 닫는 괄호
# pop() → '{', pairs['{'] = '}' == '}' ✓
# stack = ['(', '[']
# char=']': 닫는 괄호
# pop() → '[', pairs['['] = ']' == ']' ✓
# stack = ['(']
# char=')': 닫는 괄호
# pop() → '(', pairs['('] = ')' == ')' ✓
# stack = []
# 최종: stack이 비어있음 → TrueC++ 풀이:
#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동작 과정 추적:
# 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 풀이:
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]):
# 초기: 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']4. 실전 팁과 활용 패턴
스택 활용 패턴
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 | 스택 | 최근 작업부터 취소 |
5. 고급 주제
우선순위 큐 (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)) # 1C++ 우선순위 큐:
#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;
}6. 실전 팁과 활용 패턴
스택 활용 패턴 상세
| 패턴 | 설명 | 예시 |
|---|---|---|
| 괄호/태그 매칭 | 여는 것과 닫는 것 짝 맞추기 | HTML, JSON, 수식 |
| 계산기 | 후위 표기식 계산 | 3 4 + 2 * → 14 |
| 함수 호출 스택 | 재귀 시뮬레이션 | DFS, 백트래킹 |
| 되돌리기 | 최근 작업 취소 | Ctrl+Z |
| 경로 추적 | 이전 상태 기억 | 미로 탐색 |
큐 활용 패턴 상세
| 패턴 | 설명 | 예시 |
|---|---|---|
| BFS | 레벨별 순회 | 최단 경로, 트리 레벨 |
| 작업 대기열 | 순서대로 처리 | 프린터, 콜센터 |
| 스케줄링 | 라운드 로빈 | CPU 스케줄러 |
| 슬라이딩 윈도우 | 고정 크기 윈도우 | 최근 N개 항목 |
| 스트림 처리 | 순차 데이터 처리 | 로그 분석 |
7. 트러블슈팅
문제 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(); // 제거정리
핵심 요약
- 스택: LIFO, push/pop O(1), 괄호 검사
- 큐: FIFO, enqueue/dequeue O(1), BFS
- Python: 스택은 list, 큐는 deque
- C++:
<stack>,<queue>헤더
다음 단계
- 해시 테이블
- BFS/DFS
관련 글
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리