6.1 스택의 정의와 특징
스택은 LIFO(Last In, First Out, 마지막에 넣은 것이 먼저 나온다) 원리에 따라 요소들이 정렬된 요소 컬렉션을 나타내는 추상 데이터 구조야. 스택은 책 무더기로 상상할 수 있어: 마지막에 추가된 책이 무더기의 맨 위에 위치하고 가장 먼저 제거/꺼내질 거야.
스택의 특징:
- LIFO (Last In, First Out): 마지막에 추가된 요소가 가장 먼저 추출돼.
- 제한된 연산: 스택에서는 요소 추가(push), 제거(pop), 맨 위 요소 보기(peek)만 지원돼.
- 단방향 접근: 요소는 스택의 맨 위에서만 접근할 수 있어.
- 구현의 용이함: 스택은 배열 또는 연결 리스트로 쉽게 구현할 수 있어.
- 메모리 관리: 임시 데이터나 상태는 추가된 순서의 반대로 저장되고 추출될 수 있어.
LIFO 원리:
- 요소 추가(push): 새로운 요소가 스택의 맨 위에 추가돼.
- 요소 제거(pop): 마지막에 추가된 요소가 스택의 맨 위에서 제거돼.
- 맨 위 보기(peek): 요소를 제거하지 않고 스택의 맨 위에 있는 요소를 볼 수 있어.
스택의 요소는 항상 한쪽, 즉 맨 위(top)에서 추가 및 제거돼. 따라서 마지막에 추가된 요소는 언제나 맨 위에 있게 되고 가장 먼저 제거돼.
6.2 기본 연산
기본 연산: push, pop, peek
연산 push: 새로운 요소를 스택의 맨 위에 추가해.
시간 복잡도: O(1).
Python에서 list 클래스를 사용한 스택 에뮬레이션 예제:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # 출력: [10, 20]
연산 pop: 스택의 맨 위 요소를 제거하고 반환해.
시간 복잡도: O(1).
Python에서 list 클래스를 사용한 스택 에뮬레이션 예제:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # 출력: 20
print(stack) # 출력: [10]
연산 peek: 스택의 맨 위 요소를 제거하지 않고 반환해.
시간 복잡도: O(1).
구현 예제:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # 출력: 10
6.3 스택의 사용 예
스택 사용 예시 몇 가지를 보자:
함수 호출 관리
Python에서는 프로그램 실행 중에 함수의 추적을 위해 스택이 사용돼. 함수가 호출될 때마다 함수의 반환 주소와 로컬 변수들이 스택에 저장돼. 함수 실행이 끝나면 호출한 함수로 제어가 돌아가고 데이터가 스택에서 추출돼.
스택 호출 예제:
이 예제에서 factorial 함수의 재귀 호출은 각 호출의 상태를 스택에 저장하고 n == 1이라는 기본 조건에 도달할 때까지 진행돼.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 출력: 120
작업 취소 (Undo)
텍스트 에디터나 다른 애플리케이션에서 작업 취소 기능을 구현하기 위해 스택이 사용돼. 사용자가 작업을 수행할 때마다, 그 작업은 스택에 저장돼. Undo 작업이 실행되면, 마지막 작업이 스택에서 추출되고 취소돼.
작업 취소를 위한 스택 사용 예제:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# 사용 예제:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # 출력: "Hello World"
editor.undo()
print(editor.text) # 출력: "Hello"
editor.undo()
print(editor.text) # 출력: ""
GO TO FULL VERSION