스택은 마지막에 넣은 값을 먼저 꺼내는 LIFO 자료형이다. 기본 구현과 경계 오류에서 출발해 괄호 검사, 수식 변환·평가, DFS 프레임, 실행 취소, 최솟값·단조 스택을 예제와 완전 열거 검사로 설명한다.
개요: 가장 최근의 미완료 작업부터 처리한다
스택(stack)은 마지막에 넣은 원소를 먼저 꺼내는 후입선출, 즉 LIFO 규칙을 가진 추상 자료형이다. 원소를 넣는 push, 맨 위 원소를 제거하며 반환하는 pop, 제거하지 않고 보는 peek 또는 top이 핵심 연산이다. 스택의 핵심은 저장 공간의 모양보다 접근 순서를 제한하는 규칙에 있다.
중첩된 괄호에서 가장 안쪽 괄호를 먼저 닫거나, 함수가 호출한 하위 함수의 작업을 끝낸 뒤 돌아오는 상황에서 이 순서가 자연스럽게 나타난다. 최근에 시작했지만 아직 끝나지 않은 일을 보관하고 먼저 마무리하는 방식이다. 단순한 역순 출력뿐 아니라 파싱, 탐색과 상태 복원에도 쓰인다.
이 문서는 고정 용량 스택 구현에서 출발하여 괄호 검사, 후위·중위 수식 계산, 명시적 깊이 우선 탐색, 실행 취소와 단조 스택을 연결한다. 각 응용에서 무엇을 원소로 저장하는지, 언제 넣고 빼는지, 종료 시 어떤 상태여야 하는지를 구체적으로 설명한다.
실행 예제는 Python 3.9.6에서 검증했다. 별도로 표시한 검증 코드는 앞 절에서 정의한 함수를 재사용한다. 여기서 구현하는 자료구조 스택과 운영체제·런타임의 호출 스택은 관련이 있지만 같은 객체는 아니다. 스택이라는 이름만으로 저장 위치나 메모리 관리 방식을 결정하지 않는다.
push·pop·peek를 작은 연산열로 이해하기
빈 스택에 A를 넣고 B를 넣으면 맨 위는 B다. pop하면 B를 반환하고 스택에는 A가 남는다. 여기에 C를 넣고 두 번 pop하면 C,A 순서로 나온다. 먼저 넣은 A가 가장 오래 기다리게 되는 것이 FIFO 큐와의 차이다.
peek는 현재 맨 위를 읽기만 하고 길이를 바꾸지 않는다. 반면 pop은 원소를 실제로 제거한다. 같은 이름의 top 함수가 값을 반환하는지 참조를 반환하는지는 언어별 계약에 따라 다를 수 있으므로 부수 효과를 확인한다.
아래 Python list의 오른쪽 끝을 스택의 맨 위로 사용한다. append가 push에 해당하고 인수 없는 pop이 끝 원소를 제거한다. 출력 B,2에서 2는 peek 이후에도 길이가 유지됐음을 보여준다. 마지막 빈 목록은 넣은 원소를 모두 꺼냈다는 뜻이다.
예제 코드
pending = []
pending.append('A')
pending.append('B')
print(pending[-1], len(pending))
print(pending.pop())
pending.append('C')
print(pending.pop(), pending.pop())
print(pending)실행 결과
B 2
B
C A
[]추상 자료형과 실제 저장 구조를 구분하기
스택 인터페이스는 어떤 원소를 다음에 꺼낼지 정의한다. 이를 동적 배열로 구현할 수도 있고 연결 리스트의 머리에 넣고 빼는 방식으로 구현할 수도 있다. 서로 다른 구현이 같은 push·pop 계약을 만족하면 호출자는 내부 표현을 몰라도 사용할 수 있다.
배열 기반 구현은 슬롯이 연속적이고 관리 정보가 적을 수 있으며, 동적 확장을 하면 한 번씩 큰 복사가 발생할 수 있다. 연결 기반 구현은 각 추가에 노드 공간과 연결 정보가 필요하고 할당 비용이 생길 수 있다. 연결 리스트라고 메모리를 무한히 쓸 수 있거나 모든 지연이 일정한 것은 아니다.
일반 목록을 스택으로 사용할 때 중간 인덱스 삽입이나 삭제도 기술적으로 가능하지만 그것은 스택 추상화 밖의 연산이다. 여러 코드가 같은 저장소를 직접 조작하면 마지막 입력을 먼저 꺼낸다는 불변식이 깨질 수 있다. 별도 클래스로 필요한 연산만 공개하면 이런 오용을 줄인다.
큐는 먼저 넣은 원소부터 처리하고, 덱은 양 끝의 삽입·삭제를 제공하며, 우선순위 큐는 우선순위가 높은 원소를 고른다. 이름이 비슷하거나 같은 배열을 내부에 사용한다고 동작 의미가 같아지지 않는다. 작업 순서의 요구사항을 먼저 정한 뒤 구현을 선택한다.
빈 스택과 용량 초과의 계약
빈 스택에서 pop이나 peek를 호출하면 꺼낼 원소가 없다. 예외를 던질지, 성공 여부와 값을 함께 반환할지, 특별한 반환값을 사용할지 API가 정해야 한다. 어떤 선택이든 정상 데이터와 실패 표시가 구별되어야 한다.
None을 정상 값으로 저장할 수 있는데 빈 스택에서도 None을 반환하면 호출자가 두 경우를 구분하기 어렵다. 예외나 Optional·Result 형태를 사용하거나 별도 상태를 반환하면 모호함을 줄일 수 있다. 사용 언어와 호출 빈도에 맞춰 계약을 정하되 실패를 정상 값으로 숨기지 않는다.
고정 용량 스택이 가득 찼을 때도 정책이 필요하다. 추가를 거절하거나 대기하거나 확장할 수 있지만, 조용히 가장 오래된 값을 버리는 정책은 일반적인 스택과 다른 의미다. 제한된 deque의 자동 버림 동작을 그대로 사용하면서 데이터 손실 없는 스택이라고 설명해서는 안 된다.
아래는 Python list가 빈 pop에서 IndexError를 발생시키는 것을 확인한다. 이런 예외는 지원한 계약의 일부이며 테스트에서 의도적으로 재현할 수 있다. 외부 입력 때문에 자주 생기는 상황이라면 호출부의 입력 검증과 오류 메시지도 함께 설계한다.
예제 코드
pending = []
try:
pending.pop()
except IndexError:
print('empty stack')
pending.append(None)
print(len(pending), pending.pop() is None)실행 결과
empty stack
1 True고정 용량 구현과 불변식
다음 BoundedStack은 capacity개의 슬롯을 미리 확보한다. _size는 현재 원소 수이며 유효 원소는 0부터 _size-1까지다. 0≤_size≤capacity를 유지하고 맨 위는 _size-1이다. 빈 스택의 -1을 읽지 않도록 peek에서 먼저 검사한다.
push는 가득 찼는지 확인한 뒤 빈 슬롯에 값을 쓰고 길이를 늘린다. pop은 값을 확보한 뒤 길이를 줄이고 사용하지 않는 슬롯을 None으로 비워 참조를 놓는다. 제거된 객체를 내부 저장소가 불필요하게 붙잡지 않도록 하는 부분이다.
원소는 None을 포함한 임의 Python 객체로 둘 수 있고 용량은 음이 아닌 정수라는 전제를 사용한다. 생성 시 슬롯 초기화는 O(capacity), 생성 이후 push·pop·peek의 컨테이너 조작은 상수 개의 작업이다. 객체 소멸이나 사용자 정의 동작까지 포함한 절대 지연을 보장하는 실시간 구현은 아니다.
아래 용량 2의 스택에서 peek는 20을 반환하면서 길이 2를 유지하고, pop은 20,10을 순서대로 반환한다. 완성된 라이브러리에는 입력 타입, 반복 인터페이스와 스레드 안전성 같은 추가 계약이 필요하지만 기본 불변식은 이 예제로 확인할 수 있다.
예제 코드
class BoundedStack:
def __init__(self, capacity):
if capacity < 0:
raise ValueError('negative capacity')
self._data = [None] * capacity
self._size = 0
def __len__(self):
return self._size
def push(self, value):
if self._size == len(self._data):
raise OverflowError('stack full')
self._data[self._size] = value
self._size += 1
def peek(self):
if self._size == 0:
raise IndexError('stack empty')
return self._data[self._size - 1]
def pop(self):
value = self.peek()
self._size -= 1
self._data[self._size] = None
return value
s = BoundedStack(2)
s.push(10)
s.push(20)
print(s.peek(), len(s))
print(s.pop(), s.pop(), len(s))실행 결과
20 2
20 10 0시간·공간 복잡도를 정확히 말하기
고정 용량 배열이나 머리 노드를 사용하는 연결 구현에서는 기본 연산의 구조적 작업 수를 O(1)로 분석할 수 있다. 동적 배열 기반 스택의 push는 확장 순간 O(n) 복사를 할 수 있지만 적절한 성장 정책에서 연속된 추가의 분할 상환 비용은 O(1)이다. 개별 호출의 최악 시간과 연산열 전체의 비용을 구분한다.
스택에 동시에 남는 원소 수의 최댓값이 공간 요구를 결정한다. 입력 길이가 n이어도 늘 일정한 개수만 저장하면 보조 공간은 O(1)일 수 있고, 괄호가 n개 중첩되면 O(n)개의 상태가 필요할 수 있다. 전체 push 횟수와 최대 동시 깊이는 다른 수치다.
pop 후 저장소를 자동으로 줄이는 구현은 축소 시 복사가 발생할 수 있다. 한 번 크게 사용한 스택이 용량을 계속 보유하는 구현도 있다. 길이가 0이라는 사실만으로 내부 메모리나 프로세스 사용량이 0에 가까워졌다고 결론 내리지 않는다.
시간 분석에서는 저장한 값의 복사 비용과 비교 비용을 어떤 모델로 보는지도 명시한다. Python 객체 참조를 넣는 것과 큰 값 타입 전체를 복사하는 것은 같지 않다. 실제 성능 측정에는 할당과 입력 생성, 결과 출력 비용을 분리해 포함 범위를 기록한다.
괄호 검사는 개수보다 중첩 순서가 중요하다
괄호 종류가 하나일 때도 여는 개수와 닫는 개수가 같다는 조건만으로 충분하지 않다. )(는 개수는 같지만 첫 글자부터 닫을 대상이 없다. 여러 종류라면 ([)]처럼 개수와 각 종류의 수가 맞아도 중첩 순서가 잘못될 수 있다.
여는 괄호는 스택에 넣고 닫는 괄호가 나오면 맨 위 여는 괄호와 짝인지 검사한다. 가장 최근에 연 괄호부터 닫혀야 하므로 LIFO가 정확히 맞는다. 닫는 괄호를 처리할 때 스택이 비었거나 종류가 다르면 즉시 실패하고, 입력이 끝난 뒤 남은 여는 괄호가 있어도 실패다.
아래 balanced는 괄호 이외의 문자를 무시하는 간단한 규칙이다. 빈 입력은 올바른 것으로 처리한다. 문자열 리터럴 안의 괄호나 주석을 구분하지 않으므로 실제 프로그래밍 언어의 문법 검증기를 대신할 수 없다. 실제 코드를 검사하려면 토큰화 단계에서 문맥을 구분해야 한다.
예제 코드
def balanced(text):
expected = {')': '(', ']': '[', '}': '{'}
pending = []
for char in text:
if char in '([{':
pending.append(char)
elif char in expected:
if not pending or pending.pop() != expected[char]:
return False
return not pending
for text in ['', '(a+[b*c])', '([)]', ')(', '((x)']:
print(repr(text), balanced(text))실행 결과
'' True
'(a+[b*c])' True
'([)]' False
')(' False
'((x)' False괄호 검사 정확성과 오류 위치 추적
괄호 검사 중 스택은 지금까지 읽은 접두 구간에서 아직 닫히지 않은 여는 괄호를 바깥쪽부터 안쪽 순서로 담는다. 새 여는 괄호를 만나면 미완료 층이 하나 늘고, 올바른 닫는 괄호를 만나면 마지막 층이 하나 끝난다. 이 불변식으로 알고리즘의 정확성을 설명할 수 있다.
입력을 한 번 읽고 각 괄호가 최대 한 번 들어가고 한 번 나오므로 시간 O(n), 공간 O(d)다. d는 최대 괄호 중첩 깊이이며 최악에는 n에 비례한다. 한 줄 코드에 중첩 깊이 제한을 둘 필요가 있는 환경에서는 입력 길이와 깊이를 따로 제한한다.
오류 설명을 개선하려면 괄호 문자와 함께 입력 위치를 저장한다. 아래 함수는 첫 불일치 위치를 반환하고, 끝까지 읽었는데 여는 괄호가 남으면 마지막 미완료 괄호의 위치를 반환한다. 성공은 None이다. 여러 오류를 복구하며 계속 찾는 파서는 더 복잡한 정책이 필요하다.
([)]는 인덱스 2의 닫는 소괄호가 가장 최근의 여는 대괄호와 맞지 않는다. (()는 인덱스 0의 여는 괄호가 남는다. 단순 True·False뿐 아니라 어떤 상태 때문에 실패했는지 알려주면 사용자 입력 검증에 더 실용적이다.
예제 코드
def bracket_error(text):
pending = []
expected = {')': '(', ']': '[', '}': '{'}
for index, char in enumerate(text):
if char in '([{':
pending.append((char, index))
elif char in expected:
if not pending or pending[-1][0] != expected[char]:
return index
pending.pop()
return pending[-1][1] if pending else None
print(bracket_error('([)]'))
print(bracket_error('(()'))
print(bracket_error('([])'))실행 결과
2
0
None후위 표기식: 연산자를 만날 때 계산한다
보통 쓰는 8-3은 피연산자 사이에 연산자가 있는 중위 표기다. 후위 표기는 8 3 -처럼 피연산자 뒤에 연산자를 둔다. 토큰 순서에 계산 구조가 드러나므로 괄호나 우선순위를 다시 해석하지 않고 스택으로 평가할 수 있다.
숫자를 만나면 값 스택에 넣고 이항 연산자를 만나면 두 값을 꺼내 계산한 뒤 결과를 다시 넣는다. 8 3 - 2 *에서는 8과 3으로 5를 만들고, 5와 2로 10을 만든다. 마지막에는 전체 식의 결과 하나만 남아야 한다.
아래 evaluate_postfix는 공백으로 분리한 정수 토큰과 +,-,*만 지원한다. 나눗셈, 변수, 함수 호출과 부동소수점은 지원하지 않는다. Python eval로 입력을 실행하지 않고 허용한 연산을 명시적으로 선택한다. 잘못된 토큰이나 피연산자 부족, 결과가 여러 개 남는 입력은 ValueError다.
정수 자릿수가 매우 커지면 덧셈과 곱셈도 상수 시간이 아니다. 토큰 수에 대한 선형 평가라는 설명은 토큰 변환과 산술 비용을 별도로 보거나 제한된 크기의 값을 전제한 것이다. 입력 길이와 숫자 범위를 제한하는 문제와 자료구조의 연산 수를 구별한다.
예제 코드
def evaluate_postfix(tokens):
values = []
for token in tokens:
if token in {'+', '-', '*'}:
if len(values) < 2:
raise ValueError('missing operand')
right = values.pop()
left = values.pop()
if token == '+':
result = left + right
elif token == '-':
result = left - right
else:
result = left * right
values.append(result)
else:
try:
values.append(int(token))
except ValueError:
raise ValueError('invalid integer token') from None
if len(values) != 1:
raise ValueError('expression must produce one value')
return values[0]
print(evaluate_postfix('8 3 - 2 *'.split()))
print(evaluate_postfix('-3 5 +'.split()))실행 결과
10
2피연산자 순서를 바꾸면 답이 달라진다
후위 표기에서 먼저 pop한 값은 오른쪽 피연산자이고 다음 값은 왼쪽 피연산자다. 스택 맨 위가 가장 최근에 읽은 값이기 때문이다. 더하기나 곱하기만 검사하면 순서를 뒤집은 오류를 놓칠 수 있지만 뺄셈에서는 바로 드러난다.
아래 [8,3]에서 right=3, left=8을 얻어 left-right를 계산하면 5다. right-left를 쓰면 -5가 된다. 연산자의 교환법칙 여부를 고려해 테스트를 구성해야 하는 예다. 나눗셈을 지원한다면 같은 순서 문제에 더해 0으로 나누기와 정수 나눗셈 규칙도 정해야 한다.
중간 결과도 하나의 피연산자처럼 스택에 쌓이므로 중첩된 식에서도 같은 규칙이 유지된다. 두 값을 꺼내고 하나를 넣는 이항 연산은 스택 깊이를 1 줄인다. 올바른 완성식에서는 전체 입력을 처리한 뒤 깊이가 정확히 1이어야 하며, 단순히 스택이 비어 있지 않다는 검사로 끝내면 불완전한 검증이다.
예제 코드
values = [8, 3]
right = values.pop()
left = values.pop()
print(left - right)
print(right - left)
for text in ['1 +', '1 2', '']:
try:
evaluate_postfix(text.split())
except ValueError:
print('rejected', repr(text))실행 결과
5
-5
rejected '1 +'
rejected '1 2'
rejected ''중위 표기 변환: 연산자 스택의 역할
중위 표기 2+3*4는 곱셈을 먼저 처리해야 한다. 연산자를 읽는 즉시 계산하면 20이라는 잘못된 답을 만들 수 있다. 연산자 스택은 아직 출력할 시점이 오지 않은 연산자를 보관하고 우선순위와 괄호에 맞춰 후위 표기로 내보내는 역할을 한다.
숫자는 출력에 바로 추가한다. 새 연산자가 들어오면 스택 위에 더 높거나 같은 우선순위의 연산자가 있는 동안 먼저 출력한다. 여기서는 +,-,*가 모두 왼쪽 결합이므로 같은 우선순위도 먼저 내보낸다. 여는 괄호는 경계로 넣고 닫는 괄호가 오면 그 경계까지 연산자를 꺼낸다.
다음 to_postfix는 토큰이 이미 공백으로 분리되어 있다는 전제다. ( 2 + 3 ) * 4처럼 괄호도 별도 토큰이어야 한다. 단항 연산자는 지원하지 않지만 -3이라는 하나의 정수 토큰은 받아들인다. - 3처럼 연산자와 숫자로 나눈 단항 음수는 다른 문법이므로 거절한다.
need_operand는 다음에 피연산자가 필요한지 나타낸다. 이 상태가 없으면 숫자 두 개가 붙거나 연산자가 연속한 잘못된 식을 우연히 처리할 수 있다. 아래 구현은 교육용 문법의 유효성도 함께 검사한다. 완전한 언어 파서는 토큰 위치, 함수 인자, 오류 복구 같은 추가 상태를 관리한다.
예제 코드
def to_postfix(tokens):
precedence = {'+': 1, '-': 1, '*': 2}
output, operators = [], []
need_operand = True
for token in tokens:
if token == '(':
if not need_operand:
raise ValueError('missing operator')
operators.append(token)
elif token == ')':
if need_operand:
raise ValueError('missing operand')
while operators and operators[-1] != '(':
output.append(operators.pop())
if not operators:
raise ValueError('unmatched closing parenthesis')
operators.pop()
need_operand = False
elif token in precedence:
if need_operand:
raise ValueError('missing operand')
while (operators and operators[-1] in precedence
and precedence[operators[-1]] >= precedence[token]):
output.append(operators.pop())
operators.append(token)
need_operand = True
else:
if not need_operand:
raise ValueError('missing operator')
try:
int(token)
except ValueError:
raise ValueError('invalid token') from None
output.append(token)
need_operand = False
if need_operand:
raise ValueError('incomplete expression')
while operators:
token = operators.pop()
if token == '(':
raise ValueError('unmatched opening parenthesis')
output.append(token)
return output
for text in ['2 + 3 * 4', '( 2 + 3 ) * 4', '8 - 3 - 2']:
result = to_postfix(text.split())
print(' '.join(result), evaluate_postfix(result))실행 결과
2 3 4 * + 14
2 3 + 4 * 20
8 3 - 2 - 3결합 방향과 문법 확장의 함정
같은 우선순위의 연산자를 먼저 출력하는 규칙은 왼쪽 결합 연산자에 맞는다. 8-3-2는 (8-3)-2이므로 3이다. 만약 오른쪽 식을 먼저 계산하면 8-(3-2)=7로 결과가 달라진다. 우선순위만 구현하고 결합 방향을 빼면 이런 차이를 놓친다.
거듭제곱처럼 오른쪽 결합을 선택하는 문법을 추가한다면 같은 우선순위의 스택 연산자를 무조건 꺼내는 조건을 수정해야 한다. 음수 부호와 거듭제곱의 관계도 언어마다 문법이 다를 수 있다. 연산자 하나를 사전에 추가하는 것만으로 완성된 지원이 되는 것은 아니다.
빈 괄호, 닫는 괄호 누락, 두 숫자 사이 연산자 누락, 식 끝의 연산자를 별도로 검사한다. 이 예제에서는 ()를 유효한 값으로 보지 않고 2 ( 3 ) 같은 암묵적 곱셈도 지원하지 않는다. 지원 범위를 제한하는 것은 오류가 아니라 명세이며 문서에 분명히 드러나야 한다.
후위 변환과 값 평가를 분리하면 각각 테스트하기 쉽다. 중간 토큰열을 눈으로 확인할 수 있고, 다른 실행 환경에서도 같은 토큰열을 평가할 수 있다. 반면 입력 전체와 출력 전체를 저장하므로 스트리밍 처리나 메모리 제한을 요구하는 시스템에서는 별도 설계가 필요하다.
호출 스택과 재귀: 미완료 상태를 저장한다
함수가 다른 함수를 호출하면 호출자는 하위 작업이 끝난 뒤 어디서 계속할지, 어떤 지역 상태가 필요한지 보존해야 한다. 재귀 함수도 자기 자신을 호출할 때 각 호출의 상태가 별도로 필요하다. 이러한 미완료 호출의 순서가 스택과 자연스럽게 연결된다.
다만 실제 호출 규약과 런타임 구현은 언어·컴파일러·플랫폼에 따라 다르다. 모든 지역 변수가 반드시 기계의 스택 메모리에 저장되거나 모든 함수 호출이 같은 프레임 모양을 갖는다고 일반화하지 않는다. 인라이닝과 최적화, 코루틴 등은 실행 상태의 표현을 바꿀 수 있다.
재귀를 반복문으로 바꾸는 핵심은 호출이 암묵적으로 보관하던 상태를 명시적인 자료구조로 옮기는 것이다. 방문할 정점 하나만 저장해도 되는 탐색이 있고, 다음 자식 위치나 반환 후 할 작업까지 저장해야 같은 동작을 재현할 수 있는 탐색도 있다.
명시적 스택을 사용하면 재귀 호출 깊이 제한을 피하는 데 도움이 될 수 있지만 메모리 요구가 사라지는 것은 아니다. 깊이 d의 상태를 보관해야 한다면 여전히 O(d) 공간이 필요하다. 재귀 제한을 무작정 높이는 대신 입력 깊이, 종료 조건과 상태 크기를 먼저 검토한다.
깊이 우선 탐색: 방문할 정점을 스택에 넣기
그래프에서 다음에 방문할 정점을 스택에 넣으면 가장 최근에 발견한 방향으로 더 깊이 들어가는 탐색을 구성할 수 있다. 아래 dfs_order는 꺼낸 정점이 아직 방문되지 않았으면 기록하고 이웃을 스택에 넣는다. 순환이 있는 그래프에서도 seen으로 재처리를 막는다.
이웃 목록의 앞쪽을 먼저 방문하고 싶으므로 reversed로 뒤에서부터 넣는다. [B,C]를 그대로 넣으면 C가 먼저 나오기 때문이다. 탐색 순서는 정답 집합과 별개로 구현의 관찰 가능한 결과일 수 있으므로 필요하다면 이웃 순서를 명시한다.
이 구현은 넣는 시점이 아니라 꺼내는 시점에 방문을 확정하므로 같은 정점이 대기 스택에 여러 번 들어갈 수 있다. 간선이 많은 그래프에서는 대기 항목이 O(E)까지 늘 수 있다. 인접 목록과 기대 상수 시간 집합 연산을 가정하면 도달 가능한 부분의 시간은 O(V+E)이지만 보조 공간을 무조건 재귀 깊이만큼이라고 설명하면 안 된다.
아래 A에서 B,C로 이어지고 D에서 A로 돌아오는 순환이 있어도 A,B,D,C 순서로 한 번씩 처리한다. 도달 불가능한 정점까지 모두 방문하려면 전체 정점에 대해 아직 방문하지 않은 시작점을 추가하는 바깥 반복이 필요하다.
예제 코드
def dfs_order(graph, start):
seen = set()
pending = [start]
order = []
while pending:
vertex = pending.pop()
if vertex in seen:
continue
seen.add(vertex)
order.append(vertex)
pending.extend(reversed(graph.get(vertex, [])))
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['A']}
print(dfs_order(graph, 'A'))실행 결과
['A', 'B', 'D', 'C']재귀의 완료 순서를 재현하는 프레임 스택
자식을 모두 처리한 뒤 부모에서 작업하는 후위 순서는 정점만 쌓는 간단한 스택으로 바로 재현하기 어려울 수 있다. 어디까지 자식을 확인했는지 저장해야 하므로 정점과 이웃 반복자를 한 프레임으로 묶는다. 프레임 맨 위가 현재 실행 중인 호출에 대응한다.
아래 dfs_finish는 맨 위 프레임의 다음 이웃을 하나 확인하고 미방문 자식이면 새 프레임을 넣는다. 더 이상 이웃이 없으면 현재 프레임을 빼고 완료 목록에 정점을 기록한다. 하위 호출에서 돌아온 뒤 다음 자식부터 이어가는 재귀의 흐름을 명시적으로 표현한 것이다.
A의 자식이 B,C이고 B의 자식이 D라면 완료 순서는 D,B,C,A다. 시작 순서와 완료 순서는 다르며, 위상 정렬이나 그래프의 구조를 분석할 때 이 구분이 중요하다. 이 함수의 완료 목록 자체가 모든 그래프의 위상 순서라는 뜻은 아니다. 위상 정렬에는 방향성과 순환 검사라는 추가 조건이 있다.
seen 집합은 방문 정점 수만큼 공간을 사용하고 활성 프레임은 현재 탐색 깊이에 비례한다. 입력 그래프는 탐색 중 변경되지 않는다고 가정한다. 반복자를 저장한 상태에서 이웃 목록을 변경하면 건너뛰기나 중복 같은 문제가 생길 수 있으므로 스냅샷이나 변경 금지 계약을 정한다.
예제 코드
def dfs_finish(graph, start):
seen = {start}
frames = [(start, iter(graph.get(start, [])))]
finished = []
while frames:
vertex, neighbors = frames[-1]
try:
child = next(neighbors)
except StopIteration:
frames.pop()
finished.append(vertex)
continue
if child not in seen:
seen.add(child)
frames.append((child, iter(graph.get(child, []))))
return finished
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}
print(dfs_finish(graph, 'A'))실행 결과
['D', 'B', 'C', 'A']백트래킹은 선택과 복원을 한 쌍으로 관리한다
백트래킹은 한 선택을 적용해 하위 경우를 살펴본 뒤 돌아와 다음 선택을 시도한다. 현재 경로를 스택처럼 관리하면 append로 선택을 기록하고 하위 처리가 끝난 뒤 pop으로 복원할 수 있다. 복원을 빠뜨리면 이전 분기의 상태가 다음 분기에 섞인다.
아래 함수는 길이 2의 0·1 문자열을 모두 만든다. path에 한 비트를 넣고 재귀 호출한 뒤 반드시 하나를 뺀다. 출력은 00,01,10,11이다. 결과에는 현재 path 자체가 아니라 .join(path)로 만든 독립 문자열을 저장한다. 같은 변경 가능한 목록을 반복해서 저장하면 모든 결과가 같은 객체를 가리킬 수 있다.
후보가 2^n개이므로 스택을 사용한다고 문제의 지수적인 출력 수가 줄어들지는 않는다. 현재 경로는 O(n) 공간이지만 모든 길이 n의 문자열을 결과에 보관하면 출력 공간은 O(n·2^n)이다. 작업 공간과 출력 공간을 구별한다.
실제 백트래킹에는 유망하지 않은 경로를 일찍 중단하는 가지치기를 추가할 수 있다. 그 판단이 모든 올바른 답을 보존하는지 증명해야 한다. 경로 스택의 역할은 선택의 수명을 관리하는 것이며, 가지치기의 정확성을 자동으로 보장하지는 않는다.
예제 코드
def binary_words(length):
result, path = [], []
def visit():
if len(path) == length:
result.append(''.join(path))
return
for bit in '01':
path.append(bit)
visit()
path.pop()
visit()
return result
print(binary_words(2))실행 결과
['00', '01', '10', '11']실행 취소와 다시 실행: 스택 두 개의 협력
간단한 편집기는 이전 상태를 undo 스택에 넣고 변경을 적용할 수 있다. 실행 취소 시 현재 상태를 redo 스택에 넣고 undo의 맨 위 상태를 복구한다. 다시 실행은 반대 방향으로 옮긴다. 최근 변경부터 되돌리는 요구가 LIFO와 맞는다.
새 변경을 적용하면 redo 스택을 비우는 것이 일반적인 선형 이력 모델이다. 과거로 돌아간 뒤 다른 내용을 입력하면 이전 미래 경로를 그대로 다시 실행할 수 없기 때문이다. 분기 이력을 보존하는 제품은 트리나 그래프 등 더 풍부한 모델을 사용한다.
아래는 문자열 전체를 상태로 저장하여 A,AB를 만든 뒤 취소하면 A,다시 실행하면 AB가 된다. 다시 취소한 상태에서 AX로 바꾸면 redo 길이는 0이다. 문자열이 불변이라 참조 공유에 따른 사후 변경 문제를 피하기 쉽지만 큰 문서를 매번 복사하면 비용이 커질 수 있다.
실제 편집기에서는 전체 스냅샷 대신 삽입·삭제 명령과 반대 연산을 저장하거나 작은 변경을 묶기도 한다. 외부 파일 저장이나 네트워크 요청처럼 되돌리기 어려운 부수 효과는 단순 상태 스택만으로 복구되지 않는다. 실행 취소 가능한 범위를 API와 UI에서 명확하게 정한다.
예제 코드
state = ''
undo, redo = [], []
for new_state in ['A', 'AB']:
undo.append(state)
state = new_state
redo.clear()
redo.append(state)
state = undo.pop()
print(state)
undo.append(state)
state = redo.pop()
print(state)
redo.append(state)
state = undo.pop()
undo.append(state)
state = 'AX'
redo.clear()
print(state, len(redo))실행 결과
A
AB
AX 0최솟값 스택: 각 층에 보조 정보를 저장하기
현재 스택의 최솟값을 매번 전체 순회로 찾으면 O(n)이 걸린다. 각 원소와 함께 그 원소까지의 최솟값을 저장하면 맨 위의 보조 정보만 읽어 최솟값을 O(1)에 얻을 수 있다. 새 값은 이전 최솟값과 비교해 더 작은 값을 함께 넣는다.
아래 MinStack의 각 층은 (값,누적 최솟값) 쌍이다. 3,1,1,2를 넣으면 최솟값은 1이고, 위에서 2와 1을 빼도 다른 1이 남아 있으므로 최솟값은 계속 1이다. 그 다음 1을 빼면 최솟값은 3으로 돌아간다.
중복 최솟값을 제대로 보존하는 것이 중요하다. 별도 최솟값 스택에서 값이 엄격히 작을 때만 기록하고 같은 값의 개수를 관리하지 않으면 하나를 삭제할 때 최솟값을 너무 일찍 잃을 수 있다. 모든 층에 정보를 저장하는 방식은 공간 O(n)을 더 사용하는 대신 복원이 단순하다.
예제는 일관되게 비교 가능한 일반 숫자를 전제로 한다. NaN이나 사용자 정의 비교처럼 순서가 일반적인 전순서를 따르지 않는 경우에는 최솟값의 의미부터 정해야 한다. push의 배열 확장 비용을 제외한 보조 정보 갱신은 상수 개의 비교다.
예제 코드
class MinStack:
def __init__(self):
self._data = []
def push(self, value):
smallest = value if not self._data else min(value, self._data[-1][1])
self._data.append((value, smallest))
def pop(self):
if not self._data:
raise IndexError('stack empty')
return self._data.pop()[0]
def minimum(self):
if not self._data:
raise IndexError('stack empty')
return self._data[-1][1]
s = MinStack()
for value in [3, 1, 1, 2]:
s.push(value)
print(s.minimum())
print(s.pop(), s.minimum())
print(s.pop(), s.minimum())
print(s.pop(), s.minimum())실행 결과
1
2 1
1 1
1 3단조 스택: 다음으로 큰 원소의 위치
오른쪽에서 처음으로 더 큰 값이 나타나는 위치를 각 원소에 대해 찾는 문제를 생각하자. 매 원소마다 오른쪽을 처음부터 훑으면 최악 O(n²)이다. 아직 더 큰 값을 만나지 못한 원소의 인덱스를 스택에 저장하면 한 번의 순회로 해결할 수 있다.
새 값이 스택 맨 위 원소보다 크면 그 원소의 답은 현재 위치다. 그 원소를 빼고 다음 미해결 원소도 같은 조건으로 확인한다. 더 이상 해결할 원소가 없으면 현재 인덱스를 넣는다. 스택 안의 값은 바닥에서 위로 비증가 순서를 유지한다.
아래 [2,1,2,4,3]의 답은 [3,2,3,-1,-1]이다. 위치 0의 2는 위치 2의 2와 같으므로 해결되지 않고 위치 3의 4에서 해결된다. 조건이 “더 큰 값”이므로 비교는 <이며, “이상”으로 바꾸려면 중복 처리 규칙도 바뀐다.
값이 아니라 인덱스를 저장하는 이유는 각 원소의 답을 정확한 자리에 기록하고 거리도 계산할 수 있기 때문이다. 마지막까지 남은 인덱스는 오른쪽에 더 큰 값이 없으므로 -1을 유지한다. 이 패턴은 온도 상승 대기일이나 경계 찾기 등 여러 문제로 확장된다.
예제 코드
def next_greater(values):
answer = [-1] * len(values)
pending = []
for index, value in enumerate(values):
while pending and values[pending[-1]] < value:
answer[pending.pop()] = index
pending.append(index)
return answer
values = [2, 1, 2, 4, 3]
print(next_greater(values))실행 결과
[3, 2, 3, -1, -1]중첩 while인데 왜 선형 시간인가
단조 스택의 바깥 for와 안쪽 while만 보고 이차 시간이라고 판단하면 안 된다. 각 인덱스는 정확히 한 번 들어가고 최대 한 번 나온다. 어떤 단계에서 많이 꺼내더라도 이미 꺼낸 인덱스를 다음 단계에서 다시 꺼낼 수 없다. 전체 pop 횟수는 n을 넘지 않는다.
정확성의 핵심은 어떤 원소가 아직 스택에 남아 있다는 사실이 지금까지 읽은 오른쪽 값 중 그것보다 큰 값이 없었다는 뜻이라는 점이다. 현재 값이 처음으로 더 크면 현재 위치가 가장 가까운 답이다. 이전 원소를 빼도 답을 이미 확정했으므로 나중의 계산에 다시 필요하지 않다.
내림차순 입력은 마지막까지 많은 인덱스가 쌓여 공간 O(n)을 쓰고, 오름차순 입력은 새 값마다 앞의 후보를 빠르게 해결한다. 두 경우 모두 전체 작업은 선형이다. 평균 입력 분포에 기대는 분석이 아니라 각 원소의 생애를 세는 분할 상환 분석이다.
단조 스택 문제를 풀 때는 증가·감소 방향만 외우기보다 해결을 기다리는 질문이 무엇인지 적는다. 엄격한 대소인지 같은 값도 답인지, 왼쪽인지 오른쪽인지, 답으로 값·인덱스·거리를 원하는지를 먼저 정해야 비교 조건과 반환 형태가 맞아떨어진다.
스택 두 개로 큐를 만드는 원리
입력 스택에 차례로 넣은 원소를 출력 스택으로 모두 옮기면 순서가 뒤집힌다. 출력 스택에서 꺼내면 가장 먼저 들어온 원소가 먼저 나오므로 FIFO 큐를 만들 수 있다. 출력 스택이 비었을 때만 이동하고, 남아 있으면 그대로 사용하는 것이 핵심이다.
아래 1,2를 넣고 꺼내면 1이 나온다. 이어서 3을 입력 스택에 넣더라도 출력 스택에는 먼저 들어온 2가 남아 있으므로 다음 출력은 2,그 다음은 3이다. 매번 새 입력을 기존 출력 스택 위로 옮기면 이 순서가 깨질 수 있다.
한 번의 dequeue가 많은 원소를 옮겨 O(n)이 걸릴 수 있지만 각 원소는 입력 스택에 한 번 들어가고 한 번 옮겨지고 한 번 나간다. 충분히 긴 연산열의 전체 비용은 연산 수에 선형이므로 분할 상환 O(1)이다. 개별 최대 지연은 남아 있으며 메모리도 두 스택에 나뉘어 사용된다.
이 예제는 구현 원리를 보여주기 위한 단일 스레드 큐다. Python 실무에서 양끝 연산이 목적이라면 deque, 스레드 간 전달이라면 해당 동기화 큐를 선택할 수 있다. 동일한 처리 순서만 만족한다고 대기·종료·용량·동시성 계약까지 같아지는 것은 아니다.
예제 코드
incoming, outgoing = [], []
def enqueue(value):
incoming.append(value)
def dequeue():
if not outgoing:
while incoming:
outgoing.append(incoming.pop())
if not outgoing:
raise IndexError('queue empty')
return outgoing.pop()
enqueue(1)
enqueue(2)
print(dequeue())
enqueue(3)
print(dequeue(), dequeue())실행 결과
1
2 3언어별 API와 동시성 규칙
Python list는 오른쪽 끝의 append와 pop으로 스택을 구현하기 쉽다. collections.deque도 양 끝 연산을 제공한다. 다만 고정 maxlen을 지정한 deque는 가득 찼을 때 반대쪽 값을 버리는 동작이 있으므로 데이터 손실 없는 용량 제한 스택과 같은 것으로 취급하지 않는다.
Java에서는 Deque 인터페이스가 스택 사용을 제공하며 공식 문서는 기존 Stack 클래스보다 Deque 사용을 권장한다. push·pop은 앞쪽에 대응하고, 실패 시 예외를 내는 메서드와 특별한 값을 반환하는 메서드가 구분된다. 자료형 이름만 보지 말고 실제 메서드의 빈 상태 계약을 확인한다.
Python queue.LifoQueue는 스레드 간 전달을 위한 잠금과 대기·용량 제어를 제공한다. 비동기 함수에서 사용할 도구나 프로세스 간 전달 도구는 별도다. 스택의 LIFO 순서와 여러 실행 흐름이 안전하게 접근하는 동기화 문제는 독립적인 요구사항이다.
empty를 확인한 직후 다른 소비자가 마지막 원소를 꺼낼 수 있으므로 확인과 pop을 별개로 수행하는 절차에 주의한다. 필요한 원자적 연산을 제공하는 API를 사용하고 빈 상태 예외를 처리한다. 아래는 대기하지 않는 get_nowait로 값을 꺼내고 Empty를 처리하는 계약만 보여주며 실제 스레드 스케줄링을 시험한 예제는 아니다.
예제 코드
from queue import LifoQueue, Empty
jobs = LifoQueue(maxsize=2)
jobs.put_nowait('first')
jobs.put_nowait('second')
print(jobs.get_nowait(), jobs.get_nowait())
try:
jobs.get_nowait()
except Empty:
print('empty')실행 결과
second first
empty스택 오버플로와 입력 깊이 제한
고정 용량 자료구조의 가득 참과 런타임 호출 스택의 깊이 초과는 다른 상황이다. 전자는 이 문서의 BoundedStack이 OverflowError로 표현한 API 정책이고, 후자는 언어와 실행 환경의 호출 자원 제한이다. 같은 stack overflow라는 표현을 쓰더라도 대응 방법은 다를 수 있다.
중첩 입력을 처리하는 서비스는 문서 길이뿐 아니라 중첩 깊이와 생성하는 상태 크기를 제한할 수 있다. 깊게 중첩된 괄호나 트리는 작은 텍스트로도 많은 미완료 상태를 요구할 수 있다. 명시적 스택으로 바꾸어도 전체 메모리 사용량과 처리 시간을 제한해야 한다.
실패가 나면 종료 조건이 잘못된 무한 재귀인지, 정상 입력이 허용 깊이를 넘었는지, 순환을 놓친 그래프 탐색인지 원인을 구분한다. 깊이 제한만 늘리는 것은 무한 진행이나 순환 검출 오류를 해결하지 못한다.
네이티브 코드에서 스택 메모리의 경계를 벗어나는 쓰기와 안전한 컨테이너가 용량 초과를 예외로 알리는 일도 구별한다. 이 문서의 Python 예제는 메모리 경계를 침범하지 않고 명시적으로 오류를 보고한다. 운영 코드에서는 오류 이후 상태가 유지되는지와 자원이 정리되는지를 확인한다.
완전 열거 검사: 괄호와 단조 스택
아래 첫 검사는 (,),[,] 네 글자로 길이 0부터 6까지 만들 수 있는 5,461개 문자열을 검사한다. 기준 판정은 올바른 인접 괄호쌍을 반복 제거해 빈 문자열이 되는지를 보는 별도 방식이다. 효율성보다 작은 입력에서 독립적으로 답을 구하는 용도로 사용한다.
두 번째 검사는 값 0,1,2로 길이 0부터 6까지 만들 수 있는 1,093개 배열에 대해 next_greater를 오른쪽 선형 탐색의 결과와 비교한다. 중복·오름차순·내림차순·빈 입력이 모두 포함된다. 두 알고리즘의 제어 흐름이 다르므로 같은 구현 실수를 반복할 가능성을 낮춘다.
앞의 balanced와 next_greater 정의 뒤에 실행한다. 전수 검사는 이 작은 입력 공간에서의 전수이며 모든 길이의 입력에 대한 증명은 아니다. 불변식과 연산별 분석은 별도로 유지하고, 테스트는 경계 처리와 구현 변경의 회귀를 찾는 용도로 사용한다.
예제 코드
from itertools import product
def reduce_pairs(text):
while True:
reduced = text.replace('()', '').replace('[]', '')
if reduced == text:
return reduced == ''
text = reduced
bracket_cases = 0
for length in range(7):
for chars in product('()[]', repeat=length):
text = ''.join(chars)
assert balanced(text) == reduce_pairs(text)
bracket_cases += 1
array_cases = 0
for length in range(7):
for values in product(range(3), repeat=length):
expected = []
for i, value in enumerate(values):
expected.append(next((j for j in range(i + 1, length)
if values[j] > value), -1))
assert next_greater(values) == expected
array_cases += 1
print(bracket_cases, array_cases)실행 결과
5461 1093수식 계산과 용량 경계 검증
수식 계산기는 연산자 하나의 성공 사례만으로 검증하기 어렵다. 아래는 -2부터 2까지 세 숫자와 +,-,*의 조합을 사용해 괄호로 구조를 명시한 식 1,125개를 후위 표기로 변환한 뒤 기준 연산 결과와 비교한다. 교환법칙이 없는 뺄셈과 음수도 포함한다.
잘못된 중위 입력 여섯 개도 ValueError로 거절되는지 확인한다. 빈 식, 피연산자가 없는 식, 연산자가 빠진 식, 괄호 불일치와 빈 괄호를 포함한다. 지원하지 않는 문법을 우연히 허용하지 않는 것도 파서 계약의 일부다.
마지막으로 용량 1의 스택에 None을 넣고 초과 push가 실패한 뒤 기존 값과 길이가 유지되는지 확인한다. 꺼낸 뒤 다시 pop하면 빈 상태 오류가 나야 한다. 실패한 연산이 기존 데이터를 손상시키지 않는지를 검사하는 것이다. 앞의 BoundedStack, to_postfix와 evaluate_postfix 정의가 필요하다.
예제 코드
from itertools import product
operations = {'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b}
checks = 0
for a, b, c in product(range(-2, 3), repeat=3):
for first, second in product(operations, repeat=2):
tokens = ['(', str(a), first, str(b), ')', second, str(c)]
expected = operations[second](operations[first](a, b), c)
assert evaluate_postfix(to_postfix(tokens)) == expected
checks += 1
invalid = ['', '1 +', '1 2', '( 1', '1 )', '( )']
rejected = 0
for text in invalid:
try:
to_postfix(text.split())
except ValueError:
rejected += 1
assert rejected == len(invalid)
s = BoundedStack(1)
s.push(None)
try:
s.push(9)
except OverflowError:
pass
else:
raise AssertionError('missing full error')
assert len(s) == 1 and s.peek() is None
assert s.pop() is None and len(s) == 0
try:
s.pop()
except IndexError:
pass
else:
raise AssertionError('missing empty error')
print(checks, rejected, 'boundary ok')실행 결과
1125 6 boundary ok실전에서 스택을 선택하는 기준
해결해야 할 작업이 최근의 미완료 상태부터 닫히는 구조인지 먼저 살핀다. 중첩 문법, 되돌리기, 깊이 우선 탐색과 후보 경계 관리라면 스택이 자연스럽다. 도착 순서의 공정성이 필요한 대기열을 LIFO로 만들면 오래된 작업이 계속 밀릴 수 있으므로 큐와의 차이를 고려한다.
각 원소가 무엇을 나타내는지 문장으로 적으면 설계가 명확해진다. 괄호 검사에서는 미완료 여는 괄호, 수식 평가에서는 계산된 부분식 값, DFS에서는 다음 방문이나 재개할 프레임, 단조 스택에서는 답을 기다리는 인덱스다. 같은 push·pop이라도 보존해야 할 의미가 다르다.
빈 상태와 가득 찬 상태, 최대 깊이, 오류 이후 상태, 외부 참조의 수명과 동시성 요구를 정한다. 반복문이 끝났을 때 스택이 비어 있어야 하는지 결과 하나가 남아야 하는지도 알고리즘마다 다르다. 이 종료 조건을 테스트에 직접 표현하면 잘못된 입력을 조기에 발견할 수 있다.
스택을 잘 사용하는 구현은 단순히 목록 끝에서 값을 꺼내는 코드가 아니다. 왜 그 값이 지금 처리할 대상인지, 제거한 상태를 이후에 다시 필요로 하지 않는지, 한 원소가 몇 번 들어가고 나오는지를 설명할 수 있어야 한다. 이 근거가 정확성과 복잡도 분석을 함께 뒷받침한다.