#CS#DataStructure#Stack#Algorithm#Recursion#DFS
스택(Stack): 프링글스 통의 마법 (완전정복)
가장 늦게 들어간 게 가장 먼저 나온다(LIFO). 뒤로 가기 버튼, 계산기의 원리(RPN), 깊이 우선 탐색(DFS), 그리고 컴파일러의 괄호 검사까지.
2025년 4월 11일
Codemapo
가장 늦게 들어간 게 가장 먼저 나온다(LIFO). 뒤로 가기 버튼, 계산기의 원리(RPN), 깊이 우선 탐색(DFS), 그리고 컴파일러의 괄호 검사까지.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?
매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.
나는 스택을 처음 배울 때 교과서의 추상적인 다이어그램 때문에 한참 헤맸다. "LIFO(Last In First Out)"라는 네 글자를 백 번 읽어도 와닿지 않았다. 그러다가 프링글스 감자칩 통을 보는 순간, "아, 결국 이거였다"라는 깨달음이 왔다.
프링글스 공장을 상상해 보자. 공장에서 가장 먼저 만든 감자칩은 통 바닥에 깔린다. 그 위에 두 번째, 세 번째 감자칩이 차곡차곡 쌓인다. 마지막으로 만든 감자칩이 맨 위에 올라간다. 이제 우리가 먹을 차례다. 통 뚜껑을 열고 손을 넣으면? 가장 나중에 들어간(맨 위) 감자칩부터 꺼내 먹게 된다. 바닥에 깔린 첫 번째 감자칩은 통이 거의 다 비워질 때까지 기다려야 한다.
이 단순하지만 강력한 원리가 스택(Stack)이다. 나는 이걸 "나중에 온 놈이 먼저 나간다"는 후입선출 구조로 이해했다. 그리고 이 개념이 내가 작성하는 모든 코드의 근간에 있다는 사실을 나중에야 받아들였다.
스택을 이해하는 데는 딱 세 가지 연산만 알면 된다. 중간 요소를 뒤적거리거나 랜덤 액세스를 하는 것은 스택의 철학에 위배된다. 나는 이 제약이 처음엔 답답했지만, 나중에는 "제약이 곧 힘"이라는 것을 이해했다.
나는 처음에 "왜 중간 요소에 접근할 수 없지?"라고 불만이었다. 하지만 이 제약 덕분에 스택은 예측 가능하고 빠르다. 항상 맨 위에만 접근하니 캐시 친화적이고, 메모리 관리가 단순하다. 결국 단순함이 성능으로 이어진다는 걸 이해했다.
나는 개발을 시작한 지 1년쯤 됐을 때 "스택을 몰라도 코딩할 수 있나요?"라고 물었던 적이 있다. 답은 "아니요"였다. 내가 작성한 모든 코드는 이미 스택 위에서 돌아가고 있었다. 이걸 깨달은 순간, 함수 호출, 재귀, 디버깅이 한 번에 이해됐다.
함수 A가 함수 B를 호출하면 컴퓨터는 다음과 같이 동작한다.
이 과정이 계속 중첩되면서 함수 호출 트리가 만들어진다. 나는 이걸 "러시아 인형(Matryoshka)" 같다고 이해했다. 작은 인형 안에 더 작은 인형이 들어있고, 다시 그 안에 더 작은 인형이 있는 구조. 가장 안쪽 인형부터 꺼내야(Pop) 바깥 인형을 다시 볼 수 있다.
나는 초창기에 "메모리는 그냥 메모리 아닌가?"라고 생각했다. 하지만 프로그램이 사용하는 메모리는 크게 두 영역으로 나뉜다는 걸 이해했다.
malloc, new)하고 해제(free, delete)해야 한다. 크기 제한이 크지만 관리가 복잡하다.def example():
x = 10 # 스택에 저장 (지역변수)
y = [1, 2, 3] # y는 스택에, [1,2,3]은 힙에 저장 (동적 배열)
return x + len(y)
나는 이 차이를 "스택은 자동판매기, 힙은 창고"로 받아들였다. 스택은 빠르지만 용량이 작고, 힙은 느리지만 공간이 넓다.
개발자들이 가장 사랑하는 에러이자, 가장 유명한 개발자 커뮤니티 이름이다. 나는 처음 이 에러를 마주쳤을 때 "대체 뭘 잘못했길래?"라고 당황했다. 원인은 단순했다. 무한 재귀(Infinite Recursion).
def countdown(n):
print(n)
countdown(n - 1) # 종료 조건이 없다!
countdown(5) # RecursionError: maximum recursion depth exceeded
함수가 자기 자신을 무한히 호출하면 스택 프레임이 끝없이 쌓인다. 프링글스 통의 천장이 없다고 상상해 보라. 감자칩을 계속 쌓다 보면 결국 건물 천장을 뚫고 우주까지 가려 할 것이다. 컴퓨터는 그 전에 메모리 한계에 도달해서 프로그램을 강제 종료한다. 그것이 Stack Overflow다.
나는 이 개념을 이해한 뒤로 재귀 함수를 작성할 때 항상 종료 조건(Base Case)을 먼저 작성하는 습관이 생겼다.
나는 재귀(Recursion)를 처음 배울 때 "왜 함수가 자기 자신을 호출할 수 있지?"라고 의아해했다. 답은 Call Stack에 있었다. 재귀는 스택을 암시적으로 사용하는 것이다.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4)) # 24
factorial(4)를 호출하면 다음과 같은 스택 프레임이 쌓인다.
[Stack Top]
factorial(0) -> return 1
factorial(1) -> return 1 * 1 = 1
factorial(2) -> return 2 * 1 = 2
factorial(3) -> return 3 * 2 = 6
factorial(4) -> return 4 * 6 = 24
[Stack Bottom]
가장 안쪽 호출(factorial(0))이 먼저 리턴되고, 그 결과가 바깥쪽 호출로 전파된다. 나는 이걸 "도미노가 안쪽에서부터 쓰러진다"고 이해했다.
재귀를 반복문으로 바꾸면 스택을 명시적으로 사용하게 된다.
def factorial_iterative(n):
stack = []
result = 1
while n > 0:
stack.append(n)
n -= 1
while stack:
result *= stack.pop()
return result
재귀는 우아하지만 스택 메모리를 많이 쓴다. 반복문은 투박하지만 메모리 효율적이다. 나는 이 트레이드오프를 이해한 뒤, "재귀 깊이가 얕으면 재귀, 깊으면 반복문"이라는 원칙을 세웠다.
나는 고등학교 때 계산기가 3 + 4 * 5를 어떻게 계산하는지 궁금했다. 사람은 "곱셈이 먼저니까 4 * 5 = 20, 그다음 3 + 20 = 23"이라고 생각한다. 하지만 컴퓨터는 이 중위 표기법(Infix Notation)을 이해하지 못한다. 연산자 우선순위를 파싱하려면 복잡한 문법 분석이 필요하다.
그래서 컴퓨터는 후위 표기법(Postfix Notation, RPN)으로 바꾼다. 3 + 4 * 5 → 3 4 5 * +. 연산자가 피연산자 뒤에 온다.
def evaluate_rpn(tokens):
stack = []
for token in tokens:
if token in "+-*/":
b = stack.pop() # 오른쪽 피연산자
a = stack.pop() # 왼쪽 피연산자
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(int(a / b)) # 정수 나눗셈
else:
stack.append(int(token))
return stack[0]
print(evaluate_rpn(["3", "4", "+", "5", "*"])) # (3 + 4) * 5 = 35
나는 이 알고리즘을 처음 봤을 때 "스택이 왜 이렇게 강력하지?"라고 감탄했다. 괄호도 우선순위도 신경 쓸 필요 없이, 왼쪽에서 오른쪽으로 읽으면서 기계적으로 계산할 수 있다.
이건 더 복잡하다. Dijkstra가 고안한 Shunting Yard 알고리즘을 사용한다. 연산자 우선순위를 스택으로 관리한다.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
output = []
for char in expression.split():
if char.isdigit():
output.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # '(' 제거
else: # 연산자
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[char]):
output.append(stack.pop())
stack.append(char)
while stack:
output.append(stack.pop())
return ' '.join(output)
print(infix_to_postfix("3 + 4 * 5")) # "3 4 5 * +"
나는 이 알고리즘을 "우선순위가 높은 연산자가 스택 위로 올라간다"고 이해했다.
미로 찾기를 생각해 보자. 두 가지 전략이 있다.
나는 DFS를 "일단 한 길로 쭉 가보자" 전략으로 받아들였다.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # 가장 최근에 발견한 노드부터
if node not in visited:
print(node, end=' ')
visited.add(node)
# 인접 노드를 스택에 추가 (역순으로 추가해야 왼쪽부터 방문)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': [], 'F': []
}
dfs_iterative(graph, 'A') # A B D E C F
DFS는 재귀로도 구현할 수 있다. 재귀는 Call Stack을 암시적으로 사용하는 것이므로, 사실상 같은 원리다.
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs_recursive(graph, neighbor, visited)
나는 "반복문 버전은 스택을 명시적으로, 재귀 버전은 암시적으로 사용한다"고 정리했다.
나는 크롬 브라우저의 뒤로 가기 버튼을 매일 수십 번 누르면서도, 이게 어떻게 구현됐는지 한 번도 생각해 본 적이 없었다. 나중에 알고 보니 스택 2개를 사용하는 단순한 알고리즘이었다.
class BrowserHistory:
def __init__(self, homepage):
self.back_stack = [homepage]
self.forward_stack = []
self.current = homepage
def visit(self, url):
self.back_stack.append(url)
self.forward_stack = [] # 새 페이지 방문 시 앞으로 가기 기록 삭제
self.current = url
print(f"방문: {url}")
def back(self):
if len(self.back_stack) > 1:
popped = self.back_stack.pop()
self.forward_stack.append(popped)
self.current = self.back_stack[-1]
print(f"뒤로: {self.current}")
return self.current
else:
print("뒤로 갈 페이지 없음")
return self.current
def forward(self):
if self.forward_stack:
forward_page = self.forward_stack.pop()
self.back_stack.append(forward_page)
self.current = forward_page
print(f"앞으로: {self.current}")
return self.current
else:
print("앞으로 갈 페이지 없음")
return self.current
# 테스트
browser = BrowserHistory("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.back() # 뒤로: youtube.com
browser.back() # 뒤로: google.com
browser.forward() # 앞으로: youtube.com
browser.visit("stackoverflow.com") # Forward Stack 초기화됨
이 구현을 보고 나는 "왜 새 페이지 방문 시 Forward Stack을 비울까?"라는 의문이 들었다. 답은 간단했다. 뒤로 간 상태에서 새 페이지를 방문하면, 그 이후의 "미래"는 더 이상 의미가 없기 때문이다. 타임라인을 새로 쓰는 것과 같다.
같은 원리로 텍스트 에디터의 Undo/Redo를 구현할 수 있다.
class TextEditor:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
self.text = ""
def write(self, new_text):
self.undo_stack.append(self.text)
self.text = new_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()
나는 이 패턴을 "시간 여행 디버깅(Time Travel Debugging)"이라고 부른다. Redux 같은 상태 관리 라이브러리도 이 원리를 사용한다.
IDE에서 코드를 작성하다가 괄호 짝을 잃어버리면 빨간 밑줄이 뜬다. 나는 이게 "뭔가 AI가 코드를 분석하는 건가?"라고 생각했는데, 실제로는 스택을 이용한 단순한 알고리즘이었다.
def is_valid_parentheses(code):
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
for char in code:
if char in pairs: # 여는 괄호
stack.append(char)
elif char in pairs.values(): # 닫는 괄호
if not stack:
return False # 닫는 괄호가 먼저 나옴
opening = stack.pop()
if pairs[opening] != char:
return False # 짝이 안 맞음
return len(stack) == 0 # 스택이 비어있어야 유효
print(is_valid_parentheses("{ [ ( ) ] }")) # True
print(is_valid_parentheses("{ [ ( ] ) }")) # False ([ 와 ( 의 순서가 엇갈림)
이 알고리즘의 핵심은 "여는 괄호를 만나면 Push, 닫는 괄호를 만나면 Pop해서 짝 확인"이다. 나는 이걸 "러시아 인형 검증기"라고 이해했다. 안쪽 인형부터 차례대로 닫혀야 한다.
대부분의 프로그래밍 언어는 레지스터 기반 또는 힙 기반이다. 하지만 스택 기반 언어도 존재한다. 나는 이런 언어들을 처음 봤을 때 "이게 언어야?"라고 충격받았다.
3 4 + \ 스택에 3, 4를 Push, + 연산자가 Pop해서 더하고 7을 Push
5 * \ 7과 5를 곱해서 35
. \ 스택 최상단 출력: 35
모든 연산이 스택을 통해 이뤄진다. 변수도 함수도 모두 스택 조작이다. 나는 이걸 "계산기를 프로그래밍 언어로 만들면 이렇게 되는구나"라고 받아들였다.
PDF 파일을 열어서 텍스트 에디터로 보면 이런 코드가 보인다.
100 200 moveto
300 200 lineto
stroke
스택에 좌표를 쌓고, 명령어가 스택에서 꺼내서 실행한다. Adobe가 PostScript로 프린터 제어 언어를 만들었고, 이게 PDF의 기반이 됐다.
프로그램이 크래시되면 이런 메시지를 본다.
Traceback (most recent call last):
File "main.py", line 10, in <module>
result = divide(10, 0)
File "main.py", line 5, in divide
return a / b
ZeroDivisionError: division by zero
이게 바로 Stack Trace다. 에러가 발생한 순간의 Call Stack을 역순으로 보여준다. 나는 이걸 "함수 호출의 빵 부스러기(Breadcrumb)"라고 이해했다. 어디서 출발했고, 어떤 경로로 왔고, 어디서 터졌는지 추적할 수 있다.
스택 트레이스를 읽는 법:
return a / b)divide(10, 0))나는 디버깅할 때 항상 스택 트레이스를 아래에서 위로 읽는다. 에러의 근본 원인은 대부분 맨 아래에 있다.
나는 자료구조를 선택할 때 항상 이 표를 참고한다.
| 연산 | 스택 (Stack) | 큐 (Queue) | 덱 (Deque) | 배열 (Array) |
|---|---|---|---|---|
| Push/Enqueue (끝에 추가) | O(1) | O(1) | O(1) | O(1) (동적 배열 amortized) |
| Pop/Dequeue (맨 앞/뒤 제거) | O(1) | O(1) | O(1) | O(n) (맨 앞 제거 시) |
| Peek (확인) | O(1) | O(1) | O(1) | O(1) |
| 중간 접근 | 불가 | 불가 | O(n) | O(1) |
| 공간 복잡도 | O(n) | O(n) | O(n) | O(n) |
나는 이 표를 보고 "스택은 끝에서만 작업할 때 최적화돼 있다"는 걸 이해했다.
나는 초창기에 "스택, 큐, 덱이 다 비슷해 보이는데 언제 뭘 써야 하지?"라고 혼란스러웠다. 나중에 이렇게 정리했다.
나는 "무조건 양끝만 건드린다 = 스택/큐/덱 중 하나, 중간도 접근한다 = 배열/리스트"라는 기준을 세웠다.
6개월간 스택을 공부하고 적용하면서 나는 다음과 같은 결론에 도달했다.
나는 스택을 배우면서 "단순함 속에 강력함이 있다"는 걸 깨달았다. Push와 Pop이라는 두 가지 연산만으로 브라우저 히스토리, 컴파일러, 미로 찾기 알고리즘을 구현할 수 있다. 결국 이거였다. 복잡한 문제를 단순한 원칙으로 푸는 것. 그것이 좋은 자료구조의 본질이다.
When I first learned about stacks, the textbook diagrams felt abstract and distant. I read the words "LIFO (Last In First Out)" a hundred times, but it never clicked. Then one day, staring at a Pringles can, it hit me: "Oh, this is it."
Imagine a Pringles factory. The first chip produced goes to the bottom of the can. The second chip stacks on top. The third, fourth, and so on. The last chip made sits at the very top. Now, when you open the lid and reach inside, you eat the last chip first. The first chip at the bottom? It waits until the can is nearly empty.
This simple, powerful principle is the Stack. I came to understand it as "the last one in is the first one out" (LIFO). And later, I realized this concept underpins every single line of code I write.
Understanding a stack requires knowing just three operations. Accessing middle elements or random indexing violates the philosophy of a stack. Initially, this constraint felt limiting. But later, I understood that constraints create power.
At first, I wondered, "Why can't I access elements in the middle?" But this restriction makes stacks predictable and fast. Always accessing the top means cache-friendly operations and straightforward memory management. Simplicity translates to performance. I came to accept that.
About a year into programming, I asked, "Can I code without knowing stacks?" The answer was no. Every line of code I've written runs on a stack. Once I realized this, function calls, recursion, and debugging all made sense at once.
When Function A calls Function B, the computer does the following:
This nesting process creates a function call tree. I think of it like a Matryoshka doll (Russian nesting doll). A small doll inside a bigger doll, and an even smaller doll inside that. You must retrieve (pop) the innermost doll first before you can see the outer ones again.
Early on, I thought, "Isn't memory just memory?" But I learned that a program's memory is divided into two main regions:
malloc, new) and deallocate (free, delete). Larger capacity but more complex to manage.def example():
x = 10 # Stored on the stack (local variable)
y = [1, 2, 3] # y is on the stack, [1, 2, 3] is on the heap (dynamic array)
return x + len(y)
I came to think of the difference as: the stack is a vending machine, the heap is a warehouse. The stack is fast but small; the heap is slow but spacious.
The most beloved error among developers and the name of the most famous developer community. When I first encountered this error, I panicked: "What did I do wrong?" The cause was simple: Infinite Recursion.
def countdown(n):
print(n)
countdown(n - 1) # No termination condition!
countdown(5) # RecursionError: maximum recursion depth exceeded
If a function calls itself infinitely, stack frames pile up endlessly. Imagine a Pringles can with no ceiling. You keep stacking chips, and eventually, they'd burst through the roof and reach space. Before that happens, the computer hits its memory limit and crashes the program. That's Stack Overflow.
After understanding this, I developed a habit of writing the base case (termination condition) first whenever I write a recursive function.
When I first learned about recursion, I wondered, "How can a function call itself?" The answer lies in the Call Stack. Recursion is the implicit use of a stack.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4)) # 24
Calling factorial(4) builds the following stack frames:
[Stack Top]
factorial(0) -> return 1
factorial(1) -> return 1 * 1 = 1
factorial(2) -> return 2 * 1 = 2
factorial(3) -> return 3 * 2 = 6
factorial(4) -> return 4 * 6 = 24
[Stack Bottom]
The innermost call (factorial(0)) returns first, and the result propagates outward. I think of this as "dominoes falling from the inside out."
Converting recursion to iteration means using an explicit stack:
def factorial_iterative(n):
stack = []
result = 1
while n > 0:
stack.append(n)
n -= 1
while stack:
result *= stack.pop()
return result
Recursion is elegant but memory-intensive. Iteration is clunky but memory-efficient. Understanding this trade-off, I adopted the rule: "Use recursion when depth is shallow; use iteration when it's deep."
In high school, I wondered how calculators compute 3 + 4 * 5. Humans think, "Multiplication first: 4 * 5 = 20, then 3 + 20 = 23." But computers don't understand Infix Notation. Parsing operator precedence requires complex grammar analysis.
So computers convert it to Postfix Notation (RPN). 3 + 4 * 5 becomes 3 4 5 * +. Operators come after their operands.
def evaluate_rpn(tokens):
stack = []
for token in tokens:
if token in "+-*/":
b = stack.pop() # Right operand
a = stack.pop() # Left operand
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(int(a / b)) # Integer division
else:
stack.append(int(token))
return stack[0]
print(evaluate_rpn(["3", "4", "+", "5", "*"])) # (3 + 4) * 5 = 35
When I first saw this algorithm, I marveled: "Why is the stack so powerful?" No need to worry about parentheses or precedence. Just read left to right and compute mechanically.
This is more complex. It uses Dijkstra's Shunting Yard Algorithm, managing operator precedence with a stack.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
output = []
for char in expression.split():
if char.isdigit():
output.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # Remove '('
else: # Operator
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[char]):
output.append(stack.pop())
stack.append(char)
while stack:
output.append(stack.pop())
return ' '.join(output)
print(infix_to_postfix("3 + 4 * 5")) # "3 4 5 * +"
I understood this algorithm as: "Higher-precedence operators rise to the top of the stack."
Think of solving a maze. There are two strategies:
I think of DFS as the "Let's just go down this path and see where it leads" strategy.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # Most recently discovered node first
if node not in visited:
print(node, end=' ')
visited.add(node)
# Add neighbors in reverse order to visit left to right
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': [], 'F': []
}
dfs_iterative(graph, 'A') # A B D E C F
DFS can also be implemented recursively. Since recursion uses the Call Stack implicitly, it's fundamentally the same principle.
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs_recursive(graph, neighbor, visited)
I summarized it as: "Iterative DFS uses an explicit stack; recursive DFS uses the Call Stack implicitly."
I clicked Chrome's back button dozens of times every day without ever thinking about how it works. Turns out, it's a simple algorithm using two stacks.
class BrowserHistory:
def __init__(self, homepage):
self.back_stack = [homepage]
self.forward_stack = []
self.current = homepage
def visit(self, url):
self.back_stack.append(url)
self.forward_stack = [] # Clear forward history on new visit
self.current = url
print(f"Visited: {url}")
def back(self):
if len(self.back_stack) > 1:
popped = self.back_stack.pop()
self.forward_stack.append(popped)
self.current = self.back_stack[-1]
print(f"Back to: {self.current}")
return self.current
else:
print("No pages to go back to")
return self.current
def forward(self):
if self.forward_stack:
forward_page = self.forward_stack.pop()
self.back_stack.append(forward_page)
self.current = forward_page
print(f"Forward to: {self.current}")
return self.current
else:
print("No pages to go forward to")
return self.current
# Test
browser = BrowserHistory("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.back() # Back to: youtube.com
browser.back() # Back to: google.com
browser.forward() # Forward to: youtube.com
browser.visit("stackoverflow.com") # Forward Stack cleared
After seeing this implementation, I wondered: "Why clear the Forward Stack when visiting a new page?" The answer is simple: when you go back and then visit a new page, the "future" beyond that point no longer makes sense. You're rewriting the timeline.
The same principle implements Undo/Redo in text editors.
class TextEditor:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
self.text = ""
def write(self, new_text):
self.undo_stack.append(self.text)
self.text = new_text
self.redo_stack = [] # Clear redo history on new action
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()
I think of this pattern as "time travel debugging." State management libraries like Redux use this principle.
When you write code in an IDE and lose track of a bracket, a red underline appears. I thought, "Is some AI analyzing my code?" In reality, it's a simple stack-based algorithm.
def is_valid_parentheses(code):
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
for char in code:
if char in pairs: # Opening bracket
stack.append(char)
elif char in pairs.values(): # Closing bracket
if not stack:
return False # Closing bracket comes first
opening = stack.pop()
if pairs[opening] != char:
return False # Mismatch
return len(stack) == 0 # Stack must be empty
print(is_valid_parentheses("{ [ ( ) ] }")) # True
print(is_valid_parentheses("{ [ ( ] ) }")) # False ([ and ( are crossed)
The core of this algorithm: "Push when you see an opening bracket, pop and check when you see a closing bracket." I think of it as a "Matryoshka validator." Inner dolls must close before outer ones.
Most programming languages are register-based or heap-based. But stack-based languages exist too. When I first encountered them, I was shocked: "This is a language?"
3 4 + \ Push 3, 4 onto stack; + pops and adds them, pushes 7
5 * \ Multiply 7 and 5, push 35
. \ Print top of stack: 35
Every operation happens through the stack. Variables, functions—everything is stack manipulation. I thought of it as: "What happens when you turn a calculator into a programming language."
Open a PDF file in a text editor, and you'll see code like this:
100 200 moveto
300 200 lineto
stroke
Coordinates are pushed onto the stack, and commands pop from the stack to execute. Adobe created PostScript as a printer control language, which became the foundation of PDF.
When a program crashes, you see a message like this:
Traceback (most recent call last):
File "main.py", line 10, in <module>
result = divide(10, 0)
File "main.py", line 5, in divide
return a / b
ZeroDivisionError: division by zero
This is a Stack Trace. It shows the Call Stack in reverse order at the moment of the error. I think of it as "breadcrumbs of function calls." You can trace where you started, the path you took, and where it crashed.
How to read a stack trace:
return a / b in the divide function)divide(10, 0) in main.py)When debugging, I always read stack traces bottom-to-top. The root cause is usually at the bottom.
When choosing a data structure, I always refer to this table:
| Operation | Stack | Queue | Deque | Array |
|---|---|---|---|---|
| Push/Enqueue (add to end) | O(1) | O(1) | O(1) | O(1) (amortized for dynamic array) |
| Pop/Dequeue (remove from front/back) | O(1) | O(1) | O(1) | O(n) (removing from front) |
| Peek (view) | O(1) | O(1) | O(1) | O(1) |
| Middle access | N/A | N/A | O(n) | O(1) |
| Space complexity | O(n) | O(n) | O(n) | O(n) |
Looking at this table, I understood that "stacks are optimized for operations at one end only."
Early on, I was confused: "Stacks, queues, deques all look similar. When should I use which?" Later, I organized it like this:
I adopted the rule: "If you only touch the ends = stack/queue/deque; if you access the middle = array/list."