Ch.4 스택과 큐
스택 — 접시 쌓기 (LIFO)
접시를 쌓으면 맨 위부터 꺼내잖아요
식당에서 접시를 쌓으면, 마지막에 올린 접시를 가장 먼저 꺼냅니다. 이 단순한 원리가 컴퓨터 과학에서 가장 중요한 자료구조 중 하나입니다.
왜 굳이 마지막에 넣은 것을 먼저 꺼내야 할까?
함수 호출, Undo 기능, 괄호 검증 — 모두 스택 덕분에 작동합니다.
핵심 개념
스택(Stack)
후입선출(LIFO) 방식의 자료구조
LIFO
Last In, First Out — 마지막에 넣은 것이 먼저 나옴
핵심 내용
접시를 쌓아 올리면 맨 위 접시를 먼저 꺼내게 됩니다
LIFO = Last In, First Out 마지막에 들어간 것이 가장 먼저 나옵니다
현실 속 스택 예시 접시 쌓기 — 맨 위부터 꺼냄 브라우저 뒤로가기 — 마지막 방문 페이지 Ctrl+Z (Undo) — 마지막 작업 취소
스택의 핵심 연산은 두 가지뿐입니다 push(넣기)와 pop(빼기)
모든 연산이 O(1) — 이것이 스택의 매력입니다
Python의 list는 그 자체로 스택입니다
stack = []
# push
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) # [10, 20, 30]
# pop
top = stack.pop()
print(top) # 30
print(stack) # [10, 20]
# peek
print(stack[-1]) # 20list를 스택으로 쓸 때 핵심 append() → push (맨 뒤에 추가) pop() → pop (맨 뒤에서 제거) [-1] → peek (맨 뒤 확인)
프로그램이 함수를 호출할 때마다 콜 스택에 쌓입니다
def a():
print("a 시작")
b()
print("a 끝")
def b():
print("b 시작")
c()
print("b 끝")
def c():
print("c 실행")
a()콜 스택 변화 a() 호출 → [a] b() 호출 → [a, b] c() 호출 → [a, b, c] c() 끝 → [a, b] b() 끝 → [a] a() 끝 → []
재귀 호출이 너무 깊으면? RecursionError — 스택 오버플로!
스택에서 원소를 꺼내는 연산은?
Python list의 append()와 pop()은 모두 O(1) 시간복잡도이다
stack = [1,2,3]에서 stack.pop()의 결과는?
stack.pop() → ___
스택 마스터!
핵심 용어
스택(Stack)
후입선출(LIFO) 방식의 자료구조
LIFO
Last In, First Out — 마지막에 넣은 것이 먼저 나옴
push(x)
스택 맨 위에 x를 추가 — O(1)
pop()
스택 맨 위 요소를 제거하고 반환 — O(1)
peek/top
맨 위 요소를 제거하지 않고 확인 — O(1)
is_empty()
스택이 비었는지 확인 — O(1)
정리 노트
스택 — 접시 쌓기 (LIFO)
핵심 개념
- 스택
- LIFO — Last In, First Out
- push(x)
- 맨 위에 x 추가 — O(1)
- pop()
- 맨 위 원소 제거 및 반환 — O(1)
- peek
- 맨 위 원소 확인(제거X) — O(1)
Python 구현
- push
- list.append(x)
- pop
- list.pop()
- peek
- list[-1]
- is_empty
- len(list) == 0
Python list의 pop(0)은 O(n)이므로 스택에는 pop()만 사용하세요!
시각 자료
핵심 정리
- 1스택 = LIFO (후입선출) 자료구조
- 2핵심 연산: push, pop, peek 모두 O(1)
- 3Python list의 append/pop으로 간단히 구현
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작