Python의 스택(stack) 자료 구조
이 레슨에서는 Python 리스트로 스택의 기본 연산인 push, pop, peek를 구현합니다.
소개
어떤 문제를 해결하나요
실행 취소 버튼, 브라우저의 뒤로 가기, 괄호의 짝 맞추기에는 공통점이 있습니다. 항목을 기억해 두었다가 가장 최근 것부터 꺼내야 한다는 점입니다. 스택은 바로 그런 일을 하려고 만든 자료 구조입니다.
일상 속 비유
스택은 구내식당에 쌓아 둔 접시와 같습니다. 새 접시는 맨 위에 올리고, 가져갈 때도 맨 위에서 가져갑니다. 마지막에 올린 접시를 가장 먼저 쓰게 되고, 중간에 있는 접시는 빼낼 수 없습니다.
stack.append("third")🍽️ 맨 위에 접시 올리기stack.pop()⬆️ 맨 위 접시 꺼내기stack[-1]👀 맨 위 접시를 꺼내지 않고 보기만 하기stack📚 아직 쌓여 있는 접시들스택은 후입선출(LIFO, 나중에 넣은 것이 먼저 나옴) 방식의 컬렉션입니다. 항목은 맨 위에서만 넣고 꺼냅니다.
핵심 포인트
stack.append(...)는 항목을 맨 위에 올립니다(push). 스택의 맨 위는 리스트의 끝입니다.stack.pop()은 맨 위 항목을 꺼내서 돌려줍니다. 여기서는"third"입니다.stack[-1]은 맨 위 항목을 꺼내지 않고 읽기만 합니다.append와pop은 둘 다 리스트의 끝에서 동작하므로 빠릅니다.
언제 사용하나요?
- 실행 취소와 다시 실행 기록.
- 괄호의 짝 확인과 수식 파싱.
- 재귀 없이 구현하는 깊이 우선 탐색과 백트래킹.
필요 없는 경우
- 항목이 들어온 순서대로 나가야 하는 경우: 그때는 큐를 씁니다.
- 중간에 있는 항목을 꺼내거나 위치로 접근해야 하는 경우: 일반 리스트나 다른 자료 구조가 더 알맞습니다.
동작 원리 보기
push와 pop을 해 보면 마지막에 넣은 항목이 항상 먼저 나온다는 것을 알 수 있습니다.
예제 코드
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
실행 결과
popped: third
top: second
stack: ['first', 'second']
코드 설명
append() 메서드는 스택의 맨 위에 요소를 올리고, pop()은 맨 위 요소를 꺼내 돌려주므로 "third"가 가장 먼저 나옵니다. stack[-1]로 맨 위 요소를 꺼내지 않고 확인할 수 있습니다. 리스트 끝에서의 append()와 pop()은 평균 O(1)입니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
빈 스택에서 pop하기
빈 리스트에 pop()을 호출하면 IndexError가 발생합니다.
item = stack.pop()
if stack:
item = stack.pop()
리스트의 앞쪽을 스택의 맨 위로 쓰기
insert(0, x)와 pop(0)은 나머지 항목을 전부 옮겨야 해서 느립니다.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. 보통
- Mini Stack-Language Interpreter Evaluate a small stack language. 어려움