Python 알고리즘

Python의 스택(stack) 자료 구조

이 레슨에서는 Python 리스트로 스택의 기본 연산인 push, pop, peek를 구현합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

실행 취소 버튼, 브라우저의 뒤로 가기, 괄호의 짝 맞추기에는 공통점이 있습니다. 항목을 기억해 두었다가 가장 최근 것부터 꺼내야 한다는 점입니다. 스택은 바로 그런 일을 하려고 만든 자료 구조입니다.

일상 속 비유

스택은 구내식당에 쌓아 둔 접시와 같습니다. 새 접시는 맨 위에 올리고, 가져갈 때도 맨 위에서 가져갑니다. 마지막에 올린 접시를 가장 먼저 쓰게 되고, 중간에 있는 접시는 빼낼 수 없습니다.

쌓아 둔 접시에서 코드로
stack.append("third")🍽️ 맨 위에 접시 올리기
stack.pop()⬆️ 맨 위 접시 꺼내기
stack[-1]👀 맨 위 접시를 꺼내지 않고 보기만 하기
stack📚 아직 쌓여 있는 접시들
나중에 넣은 것이 먼저 나옵니다. 손이 닿는 곳은 맨 위뿐입니다.
한 문장으로

스택은 후입선출(LIFO, 나중에 넣은 것이 먼저 나옴) 방식의 컬렉션입니다. 항목은 맨 위에서만 넣고 꺼냅니다.

핵심 포인트

  1. stack.append(...)는 항목을 맨 위에 올립니다(push). 스택의 맨 위는 리스트의 끝입니다.
  2. stack.pop()은 맨 위 항목을 꺼내서 돌려줍니다. 여기서는 "third"입니다.
  3. stack[-1]은 맨 위 항목을 꺼내지 않고 읽기만 합니다.
  4. append와 pop은 둘 다 리스트의 끝에서 동작하므로 빠릅니다.

언제 사용하나요?

  • 실행 취소와 다시 실행 기록.
  • 괄호의 짝 확인과 수식 파싱.
  • 재귀 없이 구현하는 깊이 우선 탐색과 백트래킹.

필요 없는 경우

  • 항목이 들어온 순서대로 나가야 하는 경우: 그때는 큐를 씁니다.
  • 중간에 있는 항목을 꺼내거나 위치로 접근해야 하는 경우: 일반 리스트나 다른 자료 구조가 더 알맞습니다.

동작 원리 보기

push와 pop을 해 보면 마지막에 넣은 항목이 항상 먼저 나온다는 것을 알 수 있습니다.

예제 코드

코드 실행 →
main.py
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 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

빈 스택에서 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 리뷰를 받을 수 있습니다.

모든 챌린지