스택(Stack)
2025. 3. 26. 04:34ㆍData Structures/Python
스택(Stack)
개념 소개
스택은 프로그래밍에서 가장 기본적인 자료구조 중 하나로, 후입선출(LIFO: Last-In-First-Out) 원칙에 따라 작동합니다. 이것은 마치 접시를 쌓아놓은 것과 같습니다. 가장 마지막에 쌓은 접시가 가장 먼저 사용됩니다.
스택의 주요 연산:
- push: 스택의 맨 위에 항목을 추가
- pop: 스택의 맨 위에 있는 항목을 제거하고 반환
- peek/top: 스택의 맨 위 항목을 제거하지 않고 확인
- isEmpty: 스택이 비어있는지 확인
시간 복잡도
연산 |
시간 복잡도 |
| Push | O(1) |
| Pop | O(1) |
| Peek/Top | O(1) |
| isEmpty | O(1) |
스택의 모든 기본 연산은 상수 시간(O(1))에 수행됩니다. 이는 스택이 특정 유형의 문제에 매우 효율적인 솔루션을 제공할 수 있음을 의미합니다.
파이썬에서의 구현
파이썬에서는 리스트를 사용하여 스택을 쉽게 구현할 수 있습니다. 또한 collections 모듈의 deque를 사용할 수도 있습니다.
리스트를 이용한 스택 구현
class Stack:
def __init__(self):
"""스택 초기화"""
self.items = []
def is_empty(self):
"""스택이 비어있는지 확인"""
return len(self.items) == 0
def push(self, item):
"""스택에 항목 추가"""
self.items.append(item)
def pop(self):
"""스택의 맨 위 항목 제거 및 반환"""
if self.is_empty():
raise IndexError("Pop from an empty stack")
return self.items.pop()
def peek(self):
"""스택의 맨 위 항목 확인"""
if self.is_empty():
raise IndexError("Peek from an empty stack")
return self.items[-1]
def size(self):
"""스택의 크기 반환"""
return len(self.items)
def __str__(self):
"""스택의 내용을 문자열로 반환 (바닥에서 위로)"""
return str(self.items)
# 사용 예
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack) # [1, 2, 3]
print(stack.pop()) # 3
print(stack.peek()) # 2
print(stack.size()) # 2
collections.deque를 이용한 스택 구현
from collections import deque
class Stack:
def __init__(self):
"""deque를 사용하여 스택 초기화"""
self.items = deque()
def is_empty(self):
"""스택이 비어있는지 확인"""
return len(self.items) == 0
def push(self, item):
"""스택에 항목 추가"""
self.items.append(item)
def pop(self):
"""스택의 맨 위 항목 제거 및 반환"""
if self.is_empty():
raise IndexError("Pop from an empty stack")
return self.items.pop()
def peek(self):
"""스택의 맨 위 항목 확인"""
if self.is_empty():
raise IndexError("Peek from an empty stack")
return self.items[-1]
def size(self):
"""스택의 크기 반환"""
return len(self.items)
def __str__(self):
"""스택의 내용을 문자열로 반환"""
return str(list(self.items))
파이썬 리스트 메서드만 사용하기
간단한 스택 기능은 별도의 클래스 없이 파이썬 리스트만으로도 구현할 수 있습니다:
# 스택 초기화
stack = []
# 항목 추가(push)
stack.append(1)
stack.append(2)
stack.append(3)
# 스택 내용 확인
print(stack) # [1, 2, 3]
# 맨 위 항목 확인(peek)
if stack:
print(stack[-1]) # 3
# 항목 제거(pop)
if stack:
print(stack.pop()) # 3
# 스택이 비어있는지 확인
is_empty = len(stack) == 0
스택의 활용 사례
스택은 다양한 알고리즘과 응용 프로그램에서 널리 사용됩니다:
1. 괄호 매칭 검사
스택은 프로그래밍 언어에서 괄호의 균형을 확인하는 데 사용됩니다.
def is_balanced(expression):
"""괄호가 균형 잡혀 있는지 확인하는 함수"""
stack = []
brackets = {')': '(', '}': '{', ']': '['}
for char in expression:
if char in '({[':
stack.append(char)
elif char in ')}]':
if not stack or stack.pop() != brackets[char]:
return False
return len(stack) == 0
print(is_balanced("({[()]})")) # True
print(is_balanced("({[())]}")) # False
2. 중위 표기법을 후위 표기법으로 변환
계산식을 후위 표기법(Postfix)으로 변환하는 데 스택이 사용됩니다.
def infix_to_postfix(expression):
"""중위 표기법을 후위 표기법으로 변환"""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
postfix = []
for char in expression:
if char.isalnum(): # 피연산자인 경우
postfix.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop() # '(' 제거
else: # 연산자인 경우
while stack and stack[-1] != '(' and precedence.get(char, 0) <= precedence.get(stack[-1], 0):
postfix.append(stack.pop())
stack.append(char)
# 스택에 남아있는 모든 연산자 추가
while stack:
postfix.append(stack.pop())
return ''.join(postfix)
print(infix_to_postfix("a+b*c")) # "abc*+"
print(infix_to_postfix("(a+b)*c")) # "ab+c*"
3. 후위 표기법 계산
후위 표기법으로 된 식을 계산하는 데도 스택이 사용됩니다.
def evaluate_postfix(expression):
"""후위 표기법 계산"""
stack = []
for char in expression:
if char.isdigit():
stack.append(int(char))
else:
if len(stack) < 2:
raise ValueError("Invalid expression")
b = stack.pop() # 두 번째 피연산자
a = stack.pop() # 첫 번째 피연산자
if char == '+':
stack.append(a + b)
elif char == '-':
stack.append(a - b)
elif char == '*':
stack.append(a * b)
elif char == '/':
stack.append(a / b)
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack[0]
print(evaluate_postfix("23+5*")) # (2+3)*5 = 25
print(evaluate_postfix("23*5+")) # 2*3+5 = 11
4. 함수 호출 스택
프로그래밍 언어의 함수 호출은 스택 메모리를 사용하여 관리됩니다. 재귀 함수를 이해하는 데 스택의 개념이 필수적입니다.
def factorial(n):
"""factorial 함수의 호출 스택을 시각화"""
print(f"factorial({n}) 호출됨")
if n == 0 or n == 1:
print(f"factorial({n}) = 1 반환")
return 1
else:
result = n * factorial(n-1)
print(f"factorial({n}) = {result} 반환")
return result
factorial(5)
5. DFS(깊이 우선 탐색)
그래프나 트리의 깊이 우선 탐색에서 방문해야 할 노드를 저장하는 데 스택이 사용됩니다.
def dfs_iterative(graph, start):
"""스택을 사용한 반복적 DFS 구현"""
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
# 인접 노드를 스택에 추가 (역순으로 추가하여 원래 순서대로 방문)
stack.extend(reversed(graph[vertex] - visited))
return visited
# 그래프 예시 (인접 리스트 표현)
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
print("DFS:", end=' ')
dfs_iterative(graph, 'A') # A B E F C D
6. 실행 취소/다시 실행 기능
많은 애플리케이션에서 사용자 작업의 기록을 유지하고 실행 취소(undo) 및 다시 실행(redo) 기능을 구현하는 데 스택을 사용합니다.
class TextEditor:
def __init__(self):
self.text = ""
self.undo_stack = []
self.redo_stack = []
def insert(self, text):
"""텍스트 삽입"""
old_text = self.text
self.text += text
self.undo_stack.append(old_text)
self.redo_stack = [] # 새 작업으로 redo 스택 초기화
def delete(self):
"""마지막 문자 삭제"""
if self.text:
old_text = self.text
self.text = self.text[:-1]
self.undo_stack.append(old_text)
self.redo_stack = [] # 새 작업으로 redo 스택 초기화
def undo(self):
"""실행 취소"""
if self.undo_stack:
self.redo_stack.append(self.text)
self.text = self.undo_stack.pop()
def redo(self):
"""다시 실행"""
if self.redo_stack:
self.undo_stack.append(self.text)
self.text = self.redo_stack.pop()
def __str__(self):
return self.text
# 사용 예
editor = TextEditor()
editor.insert("Hello")
print(editor) # Hello
editor.insert(" World")
print(editor) # Hello World
editor.undo()
print(editor) # Hello
editor.redo()
print(editor) # Hello World
editor.delete()
print(editor) # Hello Worl
스택의 메모리 구조 이해하기
프로그래밍에서는 두 가지 주요 메모리 영역이 있습니다:
- 스택 메모리: 함수 호출과 지역 변수를 저장
- 힙 메모리: 동적으로 할당된 객체를 저장
함수가 호출될 때마다 스택 프레임이라는 새로운 메모리 블록이 스택 메모리에 추가됩니다. 이 프레임에는:
- 함수의 매개변수
- 지역 변수
- 반환 주소(함수 종료 후 돌아갈 위치)
함수가 종료되면 해당 스택 프레임이 제거되고, 프로그램 실행은 반환 주소에서 계속됩니다.
스택 오버플로우
스택 메모리는 제한된 크기를 가지고 있습니다. 스택이 할당된 메모리보다 더 많은 공간을 사용하려고 하면 "스택 오버플로우(Stack Overflow)" 오류가 발생합니다. 이는 주로 무한 재귀나 매우 깊은 재귀 호출에서 발생합니다.
def infinite_recursion():
print("재귀 호출")
infinite_recursion() # 스택 오버플로우 발생
# 실행하면 RecursionError: maximum recursion depth exceeded
# infinite_recursion()
파이썬에서는 기본적으로 재귀 깊이를 1000으로 제한합니다. 이 제한을 변경할 수 있지만, 일반적으로 재귀가 너무 깊어지면 더 효율적인 알고리즘을 찾는 것이 좋습니다.
import sys
print(f"현재 최대 재귀 깊이: {sys.getrecursionlimit()}")
sys.setrecursionlimit(2000) # 최대 재귀 깊이 변경
스택의 응용: 유효한 괄호 검사 문제 (LeetCode 20번)
가장 유명한 스택 문제 중 하나는 다양한 괄호((), [], {})로 구성된 문자열이 유효한지 검사하는 문제입니다.
def isValid(s: str) -> bool:
"""
LeetCode 20번: Valid Parentheses
괄호 문자열이 유효한지 확인하는 함수
- 열린 괄호는 같은 유형의 괄호로 닫혀야 함
- 열린 괄호는 올바른 순서로 닫혀야 함
"""
# 빈 문자열은 유효함
if not s:
return True
# 홀수 길이의 문자열은 항상 불균형함
if len(s) % 2 != 0:
return False
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
# 열린 괄호는 스택에 추가
if char in "({[":
stack.append(char)
# 닫힌 괄호는 스택의 최상위 요소와 비교
elif char in ")}]":
# 스택이 비어있거나 매칭되지 않으면 불균형함
if not stack or stack.pop() != mapping[char]:
return False
# 모든 문자를 처리한 후 스택이 비어있어야 함
return len(stack) == 0
# 테스트
print(isValid("()")) # True
print(isValid("()[]{}")) # True
print(isValid("(]")) # False
print(isValid("([)]")) # False
print(isValid("{[]}")) # True
마무리
스택은 단순하지만 강력한 자료구조로, 많은 알고리즘과 시스템에서 핵심적인 역할을 합니다. LIFO(후입선출) 원칙을 따르며, 주요 연산은 모두 O(1) 시간 복잡도를 가집니다. 스택은 함수 호출, 구문 파싱, 알고리즘 구현 등에 필수적인 자료구조입니다. 스택의 개념을 잘 이해하면 복잡한 문제도 간단하게 해결할 수 있는 경우가 많습니다.
'Data Structures > Python' 카테고리의 다른 글
| 트리(Tree) (0) | 2025.03.27 |
|---|---|
| 해시 테이블(Hash Table) (0) | 2025.03.26 |
| 큐(Queue) (0) | 2025.03.26 |
| 배열(Array)과 리스트(List) (0) | 2025.03.26 |