스택은 한쪽 끝에서만 데이터의 삽입과 삭제가 가능한 선형 자료구조로, LIFO(Last In First Out) 구조를 따른다. 함수 호출 관리, 괄호 검사, 수식 계산 등 다양한 영역에서 핵심적인 역할을 수행한다.
스택의 핵심 특성
스택은 상단(top)과 하단(bottom)으로 구분되는 단일 접근점을 가진다. 모든 데이터 입출력은 상단에서만 발생하며, 이 특성으로 인해 데이터의 역순 처리가 자연스럽게 이루어진다.
필수 연산
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| push | 상단에 요소 삽입 | O(1) |
| pop | 상단 요소 제거 및 반환 | O(1) |
| peek | 상단 요소 조회 (제거 없음) | O(1) |
| is_empty | 스택 공백 여부 확인 | O(1) |
| get_count | 저장된 요소 개수 반환 | O(1) |
스택의 활용 분야
- 재귀 및 함수 호출: 실행 시스템이 활성화 레코드를 스택 프레임으로 관리
- 괄호 유효성 검증: 중첩 구조의 짝 맞춤 확인
- 후위 표기법 계산: 연산자 우선순위 처리 없는 수식 평가
- DFS 탐색: 깊이 우선 그래프 순회
- 되돌리기 기능: 애플리케이션 상태 이력 관리
구현 방식 비교
동적 배열 기반 구현
연속 메모리 공간 활용, 캐시 효율성 우수. 단, 용량 초과 시 재할당 비용 발생.
class DynamicArrayStack:
INITIAL_CAPACITY = 8
def __init__(self):
self._buffer = [None] * self.INITIAL_CAPACITY
self._head = -1
def insert(self, value):
if self._head + 1 == len(self._buffer):
self._expand()
self._head += 1
self._buffer[self._head] = value
def remove(self):
if self.is_blank():
raise IndexError("스택이 비어있습니다")
value = self._buffer[self._head]
self._buffer[self._head] = None
self._head -= 1
return value
def inspect(self):
if self.is_blank():
return None
return self._buffer[self._head]
def is_blank(self):
return self._head < 0
def length(self):
return self._head + 1
def _expand(self):
new_size = len(self._buffer) * 2
self._buffer = self._buffer + [None] * new_size연결 리스트 기반 구현
노드 단위 메모리 할당으로 크기 제한 없음. 포인터 오버헤드 존재하나 유연성 우수.
class StackNode:
def __init__(self, value):
self.value = value
self.below = None
class LinkedStack:
def __init__(self):
self._peak = None
self._count = 0
def insert(self, value):
node = StackNode(value)
node.below = self._peak
self._peak = node
self._count += 1
def remove(self):
if self.is_blank():
raise IndexError("스택이 비어있습니다")
value = self._peak.value
self._peak = self._peak.below
self._count -= 1
return value
def inspect(self):
return None if self.is_blank() else self._peak.value
def is_blank(self):
return self._peak is None
def length(self):
return self._count실전 적용 예제
다중 괄호 형 검사
소괄호, 중괄호, 대괄호의 짝 맞춤을 검증하는 알고리즘.
def check_bracket_balance(formula):
pair_map = {')': '(', ']': '[', '}': '{'}
container = []
for symbol in formula:
if symbol in pair_map.values():
container.append(symbol)
elif symbol in pair_map.keys():
if not container or container[-1] != pair_map[symbol]:
return False
container.pop()
return len(container) == 0후위 표기식 평가
피연산자 후 연산자가 오는 표기법을 계산하는 방법.
def calculate_postfix(notation):
operands = []
elements = notation.strip().split()
for elem in elements:
if elem.lstrip('-').isdigit():
operands.append(int(elem))
else:
second = operands.pop()
first = operands.pop()
match elem:
case '+': operands.append(first + second)
case '-': operands.append(first - second)
case '*': operands.append(first * second)
case '/': operands.append(first // second)
case '^': operands.append(first ** second)
return operands[0]문서 편집기 실행 취소 시스템
스냅샷 기반 상태 복원 메니즘.
class DocumentHistory:
def __init__(self):
self._current = ""
self._snapshots = []
def append(self, content):
self._snapshots.append(self._current)
self._current += content
def revert(self):
if self._snapshots:
self._current = self._snapshots.pop()
def get_content(self):
return self._current
# 활용 예시
doc = DocumentHistory()
doc.append("알고리즘")
doc.append(" 스터디")
print(doc.get_content()) # "알고리즘 스터디"
doc.revert()
print(doc.get_content()) # "알고리즘"성능 분석
| 구현 방식 | push | pop | peek | 공간 효율성 |
|---|---|---|---|---|
| 동적 배열 | 평균 O(1), 최악 O(n) | O(1) | O(1) | 미사용 공간 존재 |
| 연결 리스트 | O(1) | O(1) | O(1) | 포인터 오버헤드 |
스택은 제한된 접근 방식으로 인해 구현이 단순하며, 예측 가능한 성능 특성을 제공한다. 상황에 맞는 구현체 선택과 함께, 스택을 활용한 알고리즘 설계 능력은 효율적인 코드 작성의 기초가 된다.