栈（Stack）完全详解¶
重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐ 学习时间：2-3天 前置知识：数组、链表
📚 目录¶
什么是栈？¶
基本概念¶
栈是一种后进先出（LIFO, Last In First Out）的线性数据结构。
生活中的例子¶
想象一摞盘子：
Text Only
┌───┐
│ 5 │ ← 最上面的盘子（最后放上去的）
├───┤
│ 4 │
├───┤
│ 3 │
├───┤
│ 2 │
├───┤
│ 1 │ ← 最下面的盘子（最先放上去的）
└───┘
图：栈（Stack）的后进先出（LIFO）结构示意图
- 只能从顶部放入盘子（入栈/压栈/push）
- 只能从顶部取出盘子（出栈/弹栈/pop）
- 后放上去的先拿出来（LIFO）
为什么学栈？¶
✅ 应用广泛： - 函数调用栈（所有编程语言的基础） - 撤销操作（Ctrl+Z） - 浏览器的前进/后退 - 括号匹配 - 深度优先搜索（DFS） - 表达式求值
✅ 实现简单： - 操作只有两种：push和pop - 时间复杂度都是O(1)
✅ 面试常考： - 括号匹配 - 逆波兰表达式 - 最小栈 - 有效括号
栈的实现¶
方法1：使用Python列表（最简单）¶
Python
class Stack:
"""使用Python list实现栈"""
def __init__(self):
self.items = []
def push(self, item):
"""入栈：O(1)"""
self.items.append(item)
print(f"入栈: {item}")
def pop(self):
"""出栈：O(1)"""
if not self.is_empty():
item = self.items.pop()
print(f"出栈: {item}")
return item
raise IndexError("栈为空，无法出栈")
def peek(self):
"""查看栈顶元素：O(1)"""
if not self.is_empty():
return self.items[-1]
raise IndexError("栈为空")
def is_empty(self):
"""判断栈是否为空"""
return len(self.items) == 0
def size(self):
"""返回栈的大小"""
return len(self.items)
def __str__(self):
return f"栈底 -> {self.items} <- 栈顶"
# 测试
stack = Stack()
print("初始状态:", stack)
stack.push(1)
stack.push(2)
stack.push(3)
print("当前栈:", stack)
print("栈顶元素:", stack.peek())
print("栈的大小:", stack.size())
stack.pop()
stack.pop()
print("出栈两次后:", stack)
# 输出：
# 初始状态: 栈底 -> [] <- 栈顶
# 入栈: 1
# 入栈: 2
# 入栈: 3
# 当前栈: 栈底 -> [1, 2, 3] <- 栈顶
# 栈顶元素: 3
# 栈的大小: 3
# 出栈: 3
# 出栈: 2
# 出栈两次后: 栈底 -> [1] <- 栈顶
方法2：使用链表（高效）¶
Python
class StackNode:
"""栈的节点"""
def __init__(self, data):
self.data = data
self.next = None
class LinkedListStack:
"""使用链表实现栈"""
def __init__(self):
self.top = None # 栈顶指针
self.size = 0
def push(self, item):
"""入栈：O(1)"""
new_node = StackNode(item)
new_node.next = self.top
self.top = new_node
self.size += 1
print(f"入栈: {item}")
def pop(self):
"""出栈：O(1)"""
if not self.is_empty():
item = self.top.data
self.top = self.top.next
self.size -= 1
print(f"出栈: {item}")
return item
raise IndexError("栈为空，无法出栈")
def peek(self):
"""查看栈顶元素：O(1)"""
if not self.is_empty():
return self.top.data
raise IndexError("栈为空")
def is_empty(self):
"""判断栈是否为空"""
return self.top is None
def get_size(self):
"""返回栈的大小"""
return self.size
def __str__(self):
items = []
current = self.top
while current:
items.append(str(current.data))
current = current.next
return f"栈顶 -> {' -> '.join(items)} <- 栈底"
# 测试
stack = LinkedListStack()
stack.push(1)
stack.push(2)
stack.push(3)
print("当前栈:", stack)
print("栈顶元素:", stack.peek())
print("栈的大小:", stack.get_size())
stack.pop()
print("出栈后:", stack)
# 输出：
# 入栈: 1
# 入栈: 2
# 入栈: 3
# 当前栈: 栈顶 -> 3 -> 2 -> 1 <- 栈底
# 栈顶元素: 3
# 栈的大小: 3
# 出栈: 3
# 出栈后: 栈顶 -> 2 -> 1 <- 栈底
方法3：使用C++ STL stack¶
C++
#include <iostream> // 引入头文件
#include <stack>
using namespace std;
int main() {
// 创建栈
stack<int> s;
// 入栈
s.push(1);
s.push(2);
s.push(3);
// 访问栈顶
cout << "栈顶元素: " << s.top() << endl; // 3
// 栈的大小
cout << "栈的大小: " << s.size() << endl; // 3
// 出栈
s.pop();
cout << "出栈后栈顶: " << s.top() << endl; // 2
// 判断是否为空
cout << "栈是否为空: " << (s.empty() ? "是" : "否") << endl; // 否
return 0;
}
栈的操作详解¶
操作1：入栈（Push）¶
Python
def push_detailed(stack, items):
"""详细演示入栈过程"""
print("=" * 50)
print("入栈操作演示")
print("=" * 50)
for item in items:
print(f"\n步骤: 将 {item} 入栈")
print(f"入栈前: {stack}")
stack.push(item)
print(f"入栈后: {stack}")
print(f"栈顶: {stack.peek()}")
print(f"大小: {stack.size()}")
# 测试
stack = Stack()
push_detailed(stack, [1, 2, 3, 4, 5])
# 输出：
# ==================================================
# 入栈操作演示
# ==================================================
#
# 步骤: 将 1 入栈
# 入栈前: 栈底 -> [] <- 栈顶
# 入栈: 1
# 入栈后: 栈底 -> [1] <- 栈顶
# 栈顶: 1
# 大小: 1
#
# 步骤: 将 2 入栈
# 入栈前: 栈底 -> [1] <- 栈顶
# 入栈: 2
# 入栈后: 栈底 -> [1, 2] <- 栈顶
# 栈顶: 2
# 大小: 2
#
# ...（继续）
入栈过程图解：
Text Only
初始状态：
栈底 栈顶
└─┘
[]
push(1):
栈底 栈顶
└─1┘
[1]
push(2):
栈底 栈顶
└─1─2┘
[1, 2]
push(3):
栈底 栈顶
└─1─2─3┘
[1, 2, 3]
操作2：出栈（Pop）¶
Python
def pop_detailed(stack, n):
"""详细演示出栈过程"""
print("=" * 50)
print("出栈操作演示")
print("=" * 50)
for i in range(n):
if stack.is_empty():
print("\n栈已为空，无法出栈")
break
print(f"\n步骤 {i+1}: 出栈")
print(f"出栈前: {stack}")
print(f"栈顶: {stack.peek()}")
item = stack.pop()
print(f"出栈后: {stack}")
print(f"取出元素: {item}")
# 测试
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("初始栈:", stack)
pop_detailed(stack, 5)
# 输出：
# ==================================================
# 出栈操作演示
# ==================================================
#
# 步骤 1: 出栈
# 出栈前: 栈底 -> [1, 2, 3] <- 栈顶
# 栈顶: 3
# 出栈: 3
# 出栈后: 栈底 -> [1, 2] <- 栈顶
# 取出元素: 3
#
# 步骤 2: 出栈
# 出栈前: 栈底 -> [1, 2] <- 栈顶
# 栈顶: 2
# 出栈: 2
# 出栈后: 栈底 -> [1] <- 栈顶
# 取出元素: 2
#
# 步骤 3: 出栈
# 出栈前: 栈底 -> [1] <- 栈顶
# 栈顶: 1
# 出栈: 1
# 出栈后: 栈底 -> [] <- 栈顶
# 取出元素: 1
#
# 步骤 4: 出栈
#
# 栈已为空，无法出栈
出栈过程图解：
Text Only
初始状态：[1, 2, 3]
栈底 栈顶
└─1─2─3┘
第1次pop():
取出: 3
栈底 栈顶
└─1─2┘
第2次pop():
取出: 2
栈底 栈顶
└─1┘
第3次pop():
取出: 1
栈底 栈顶
└─┘
[]
操作3：查看栈顶（Peek）¶
Python
def peek_operations(stack):
"""演示peek操作"""
print("=" * 50)
print("Peek操作演示")
print("=" * 50)
# 栈为空时peek
print("\n栈为空时peek:")
empty_stack = Stack()
try: # try/except捕获异常
empty_stack.peek()
except IndexError as e:
print(f"错误: {e}")
# 栈不为空时peek
print("\n栈不为空时peek:")
stack.push(10)
stack.push(20)
stack.push(30)
print(f"栈状态: {stack}")
print(f"栈顶元素: {stack.peek()}")
print(f"peek后栈状态: {stack}") # 栈不变
# 测试
stack = Stack()
peek_operations(stack)
# 输出：
# ==================================================
# Peek操作演示
# ==================================================
#
# 栈为空时peek:
# 错误: 栈为空
#
# 栈不为空时peek:
# 入栈: 10
# 入栈: 20
# 入栈: 30
# 栈状态: 栈底 -> [10, 20, 30] <- 栈顶
# 栈顶元素: 30
# peek后栈状态: 栈底 -> [10, 20, 30] <- 栈顶
栈的应用¶
应用1：括号匹配 ⭐⭐⭐⭐⭐¶
问题：给定一个只包含括号的字符串，判断括号是否合法。
示例：
Text Only
输入："()" → 输出：true
输入："()[]{}" → 输出：true
输入："(]" → 输出：false
输入："([)]" → 输出：false
输入："{[]}" → 输出：true
解法：使用栈
Python
def is_valid_parentheses(s):
"""
判断括号是否合法
时间：O(n)
空间：O(n)
思路：
1. 遇到左括号，入栈
2. 遇到右括号，检查栈顶是否匹配
3. 最后栈为空则合法
"""
# 创建括号映射
mapping = {')': '(', ']': '[', '}': '{'}
# 创建栈
stack = []
for char in s:
if char in mapping: # 右括号
# 栈顶元素
top_element = stack.pop() if stack else '#'
# 检查是否匹配
if mapping[char] != top_element:
return False
else: # 左括号
stack.append(char)
# 栈为空则合法
return not stack
def is_valid_parentheses_detailed(s):
"""详细版：展示每一步"""
print("=" * 60)
print(f"判断括号是否合法: {s}")
print("=" * 60)
mapping = {')': '(', ']': '[', '}': '{'}
stack = []
for i, char in enumerate(s):
print(f"\n第{i+1}个字符: '{char}'")
print(f"当前栈: {stack}")
if char in mapping:
# 右括号
top_element = stack.pop() if stack else '#'
print(f" 栈顶: '{top_element}'")
print(f" 期望: '{mapping[char]}'")
if mapping[char] != top_element:
print(f" ❌ 不匹配！返回False")
return False
else:
print(f" ✓ 匹配！继续")
else:
# 左括号
stack.append(char)
print(f" 左括号，入栈")
print(f"\n遍历结束")
print(f"最终栈: {stack}")
print(f"栈为空: {not stack}")
return not stack
# 测试
test_cases = [
"()",
"()[]{}",
"(]",
"([)]",
"{[]}",
"((()))",
"([{}])",
"((())"
]
print("快速版测试：")
for s in test_cases:
result = is_valid_parentheses(s)
print(f"{s:10} → {result}")
print("\n" + "="*60)
print("详细版测试：")
is_valid_parentheses_detailed("{[()]}")
# 输出：
# 快速版测试：
# () → True
# ()[]{} → True
# (] → False
# ([)] → False
# {[]} → True
# ((())) → True
# ([{}]) → True
# ((()) → False
#
# ============================================================
# 判断括号是否合法: {[()]}
# ============================================================
#
# 第1个字符: '{'
# 当前栈: []
# 左括号，入栈
#
# 第2个字符: '['
# 当前栈: ['{']
# 左括号，入栈
#
# 第3个字符: '('
# 当前栈: ['{', '[']
# 左括号，入栈
#
# 第4个字符: ')'
# 当前栈: ['{', '[', '(']
# 栈顶: '('
# 期望: '('
# ✓ 匹配！继续
#
# 第5个字符: ']'
# 当前栈: ['{', '[']
# 栈顶: '['
# 期望: '['
# ✓ 匹配！继续
#
# 第6个字符: '}'
# 当前栈: ['{']
# 栈顶: '{'
# 期望: '{'
# ✓ 匹配！继续
#
# 遍历结束
# 最终栈: []
# 栈为空: True
括号匹配过程图解：
Text Only
输入: "{[()]}"
初始: 栈为空
└─┘
[]
步骤1: '{' 入栈
└─{┘
['{']
步骤2: '[' 入栈
└─{─[┘
['{', '[']
步骤3: '(' 入栈
└─{─[─(┘
['{', '[', '(']
步骤4: ')' 匹配 '('
└─{─[┘
['{', '[']
步骤5: ']' 匹配 '['
└─{┘
['{']
步骤6: '}' 匹配 '{'
└─┘
[]
结果: 栈为空 → 合法 ✓
应用2：逆波兰表达式求值 ⭐⭐⭐⭐¶
问题：根据逆波兰表示法，求表达式的值。
示例：
Text Only
输入：["2", "1", "+", "3", "*"]
输出：9
解释：((2 + 1) * 3) = 9
输入：["4", "13", "5", "/", "+"]
输出：6
解释：(4 + (13 / 5)) = 6
解法：使用栈
Python
def eval_rpn(tokens):
"""
逆波兰表达式求值
时间：O(n)
空间：O(n)
有效的运算符包括+, -, *, /
"""
stack = []
for token in tokens:
if token in "+-*/":
# 运算符：弹出两个元素进行计算
b = stack.pop()
a = stack.pop()
if token == '+':
result = a + b
elif token == '-':
result = a - b
elif token == '*':
result = a * b
else: # '/'
result = int(a / b) # 向下取整
print(f"运算: {a} {token} {b} = {result}")
stack.append(result)
else:
# 数字：入栈
num = int(token)
stack.append(num)
print(f"入栈: {num}")
print(f"当前栈: {stack}")
return stack[0]
def eval_rpn_detailed(tokens):
"""详细版：展示每一步"""
print("=" * 60)
print(f"逆波兰表达式求值: {' '.join(tokens)}")
print("=" * 60)
result = eval_rpn(tokens)
print("\n" + "=" * 60)
print(f"最终结果: {result}")
# 测试
tokens1 = ["2", "1", "+", "3", "*"]
eval_rpn_detailed(tokens1)
# 输出: 9
tokens2 = ["4", "13", "5", "/", "+"]
print("\n" + "="*60)
eval_rpn_detailed(tokens2)
# 输出: 6
# 输出：
# ============================================================
# 逆波兰表达式求值: 2 1 + 3 *
# ============================================================
# 入栈: 2
# 当前栈: [2]
# 入栈: 1
# 当前栈: [2, 1]
# 运算: 2 + 1 = 3
# 当前栈: [3]
# 入栈: 3
# 当前栈: [3, 3]
# 运算: 3 * 3 = 9
# 当前栈: [9]
#
# ============================================================
# 最终结果: 9
逆波兰表达式求值过程图解：
Text Only
表达式: ["2", "1", "+", "3", "*"]
初始: 栈为空
└─┘
[]
步骤1: "2" 入栈
└─2┘
[2]
步骤2: "1" 入栈
└─2─1┘
[2, 1]
步骤3: "+" 运算
弹出 1 和 2
计算 2 + 1 = 3
结果入栈
└─3┘
[3]
步骤4: "3" 入栈
└─3─3┘
[3, 3]
步骤5: "*" 运算
弹出 3 和 3
计算 3 * 3 = 9
结果入栈
└─9┘
[9]
最终结果: 9
应用3：最小栈 ⭐⭐⭐⭐⭐¶
问题：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
示例：
Text Only
输入：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解法1：辅助栈
Python
class MinStack:
"""
最小栈实现
时间：O(1) 所有操作
空间：O(n)
"""
def __init__(self):
# 主栈：存储所有元素
self.stack = []
# 辅助栈：存储当前最小值
self.min_stack = []
def push(self, val: int) -> None:
"""入栈：O(1)"""
self.stack.append(val)
# 维护最小值栈
if not self.min_stack:
self.min_stack.append(val)
else:
# 新值 <= 当前最小值，才入栈
if val <= self.min_stack[-1]:
self.min_stack.append(val)
print(f"push({val}): 主栈={self.stack}, 最小栈={self.min_stack}")
def pop(self) -> None:
"""出栈：O(1)"""
if self.stack:
val = self.stack.pop()
# 如果出栈的值是最小值，最小栈也要出栈
if val == self.min_stack[-1]:
self.min_stack.pop()
print(f"pop(): 出栈{val}, 主栈={self.stack}, 最小栈={self.min_stack}")
def top(self) -> int:
"""获取栈顶：O(1)"""
return self.stack[-1]
def getMin(self) -> int:
"""获取最小值：O(1)"""
return self.min_stack[-1]
# 测试
minStack = MinStack()
print("="*60)
print("最小栈测试")
print("="*60)
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(f"\n当前最小值: {minStack.getMin()}") # -3
minStack.pop()
print(f"\n出栈后栈顶: {minStack.top()}") # 0
print(f"当前最小值: {minStack.getMin()}") # -2
# 输出：
# ============================================================
# 最小栈测试
# ============================================================
# push(-2): 主栈=[-2], 最小栈=[-2]
# push(0): 主栈=[-2, 0], 最小栈=[-2]
# push(-3): 主栈=[-2, 0, -3], 最小栈=[-2, -3]
#
# 当前最小值: -3
# pop(): 出栈-3, 主栈=[-2, 0], 最小栈=[-2]
#
# 出栈后栈顶: 0
# 当前最小值: -2
最小栈图解：
Text Only
操作序列: push(-2), push(0), push(-3), pop()
push(-2):
主栈: [-2]
最小栈: [-2]
当前最小: -2
push(0):
主栈: [-2, 0]
最小栈: [-2] (0 > -2，不入最小栈)
当前最小: -2
push(-3):
主栈: [-2, 0, -3]
最小栈: [-2, -3] (-3 <= -2，入最小栈)
当前最小: -3
pop():
主栈: [-2, 0]
最小栈: [-2] (出栈-3，最小栈也出栈)
当前最小: -2
应用4：有效的括号字符串 ⭐⭐⭐⭐¶
问题：给定一个括号字符串，返回最长的有效（正确闭合）括号子串的长度。
示例：
解法：使用栈
Python
def longest_valid_parentheses(s):
"""
最长有效括号
时间：O(n)
空间：O(n)
"""
stack = [-1] # 存储索引，初始为-1
max_len = 0
for i, char in enumerate(s): # enumerate同时获取索引和值
if char == '(':
# 左括号：入栈索引
stack.append(i)
else:
# 右括号：出栈
stack.pop()
if not stack:
# 栈为空，入栈当前索引作为新的起点
stack.append(i)
else:
# 栈不为空，计算有效长度
current_len = i - stack[-1]
max_len = max(max_len, current_len)
print(f"i={i}, char='{char}', stack={stack}, current_len={i - stack[-1] if stack else 0}, max_len={max_len}")
return max_len
# 测试
print("="*60)
s1 = "(()"
print(f"输入: {s1}")
print(f"输出: {longest_valid_parentheses(s1)}")
print()
s2 = ")()())"
print("="*60)
print(f"输入: {s2}")
print(f"输出: {longest_valid_parentheses(s2)}")
# 输出：
# ============================================================
# 输入: (()
# i=0, char='(', stack=[-1, 0], current_len=0, max_len=0
# i=1, char='(', stack=[-1, 0, 1], current_len=0, max_len=0
# i=2, char=')', stack=[-1, 0], current_len=2, max_len=2
# 输出: 2
#
# ============================================================
# 输入: )()())
# i=0, char=')', stack=[0], current_len=0, max_len=0
# i=1, char='(', stack=[0, 1], current_len=0, max_len=0
# i=2, char=')', stack=[0], current_len=2, max_len=2
# i=3, char='(', stack=[0, 3], current_len=0, max_len=2
# i=4, char=')', stack=[0], current_len=4, max_len=4
# i=5, char=')', stack=[5], current_len=0, max_len=4
# 输出: 4
经典面试题¶
题目1：用栈实现队列 ⭐⭐⭐⭐¶
问题：使用两个栈实现队列。
解法：
Python
class MyQueue:
"""
用两个栈实现队列
时间：
- push: O(1)
- pop: O(n) 最坏，amortized O(1)
- peek: O(n) 最坏，amortized O(1)
空间：O(n)
"""
def __init__(self):
# 入队栈
self.in_stack = []
# 出队栈
self.out_stack = []
def push(self, x: int) -> None:
"""入队：O(1)"""
self.in_stack.append(x)
print(f"入队: {x}, in_stack={self.in_stack}")
def pop(self) -> int:
"""出队：amortized O(1)"""
self._transfer()
val = self.out_stack.pop()
print(f"出队: {val}, out_stack={self.out_stack}")
return val
def peek(self) -> int:
"""查看队首：amortized O(1)"""
self._transfer()
return self.out_stack[-1]
def empty(self) -> bool:
"""判断队列是否为空"""
return not self.in_stack and not self.out_stack
def _transfer(self):
"""
将in_stack的元素转移到out_stack
只有out_stack为空时才转移
"""
if not self.out_stack:
print(f"转移: in_stack={self.in_stack} -> out_stack")
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
print(f"转移后: out_stack={self.out_stack}")
# 测试
queue = MyQueue()
print("="*60)
print("用栈实现队列测试")
print("="*60)
queue.push(1)
queue.push(2)
queue.push(3)
print(f"\n队首: {queue.peek()}") # 1
queue.pop()
print(f"\n出队后队首: {queue.peek()}") # 2
# 输出：
# ============================================================
# 用栈实现队列测试
# ============================================================
# 入队: 1, in_stack=[1]
# 入队: 2, in_stack=[1, 2]
# 入队: 3, in_stack=[1, 2, 3]
#
# 转移: in_stack=[1, 2, 3] -> out_stack
# 转移后: out_stack=[3, 2, 1]
# 队首: 1
# 出队: 1, out_stack=[3, 2]
#
# 出队后队首: 2
用栈实现队列图解：
Text Only
初始状态:
in_stack: []
out_stack: []
push(1):
in_stack: [1]
out_stack: []
push(2):
in_stack: [1, 2]
out_stack: []
push(3):
in_stack: [1, 2, 3]
out_stack: []
peek():
需要转移！
in_stack: []
out_stack: [3, 2, 1] # 注意顺序反转
队首: out_stack[-1] = 1
pop():
out_stack: [3, 2]
出队: 1
题目2：简化路径 ⭐⭐⭐¶
问题：给定一个Unix风格的文件路径，简化它。
示例：
解法：使用栈
Python
def simplify_path(path):
"""
简化Unix路径
时间：O(n)
空间：O(n)
"""
stack = []
# 分割路径
parts = path.split('/')
for part in parts:
print(f"处理: '{part}', 栈: {stack}")
if part == '' or part == '.':
# 空或当前目录，跳过
continue
elif part == '..':
# 上级目录
if stack:
stack.pop()
print(f" 返回上级目录，栈变为: {stack}")
else:
# 目录名，入栈
stack.append(part)
print(f" 入栈，栈变为: {stack}")
# 构建简化路径
result = '/' + '/'.join(stack)
print(f"\n最终路径: {result}")
return result
# 测试
paths = [
"/a/./b/../../c/",
"/home//foo/",
"/../",
"/home/../../.."
]
for p in paths:
print("="*60)
print(f"原路径: {p}")
simplify_path(p)
print()
# 输出：
# ============================================================
# 原路径: /a/./b/../../c/
# 处理: 'a', 栈: []
# 入栈，栈变为: ['a']
# 处理: '.', 栈: ['a']
# 处理: 'b', 栈: ['a']
# 入栈，栈变为: ['a', 'b']
# 处理: '..', 栈: ['a', 'b']
# 返回上级目录，栈变为: ['a']
# 处理: '..', 栈: ['a']
# 返回上级目录，栈变为: []
# 处理: 'c', 栈: []
# 入栈，栈变为: ['c']
#
# 最终路径: /c
题目3：删除字符串中的所有相邻重复项 ⭐⭐⭐¶
问题：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
示例：
解法：使用栈
Python
def remove_duplicates(s):
"""
删除相邻重复项
时间：O(n)
空间：O(n)
"""
stack = []
for char in s:
if stack and stack[-1] == char: # 负索引：从末尾倒数访问元素
# 栈顶元素与当前字符相同，出栈
popped = stack.pop()
print(f"发现重复: '{popped}' 和 '{char}'，删除")
else:
# 入栈
stack.append(char)
print(f"入栈: '{char}', 栈: {stack}")
result = ''.join(stack)
print(f"最终结果: {result}")
return result
# 测试
print("="*60)
s = "abbaca"
print(f"输入: {s}")
remove_duplicates(s)
# 输出：
# ============================================================
# 输入: abbaca
# 入栈: 'a', 栈: ['a']
# 入栈: 'b', 栈: ['a', 'b']
# 发现重复: 'b' 和 'b'，删除
# 入栈: 'a', 栈: ['a', 'a']
# 发现重复: 'a' 和 'a'，删除
# 入栈: 'c', 栈: ['c']
# 入栈: 'a', 栈: ['c', 'a']
# 最终结果: ca
实战练习¶
练习1：基本操作¶
Python
# 练习1：实现一个栈，并完成以下操作
class Stack:
def __init__(self):
pass
def push(self, item):
pass
def pop(self):
pass
def peek(self):
pass
def is_empty(self):
pass
def size(self):
pass
# 测试代码
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 应该输出3
print(stack.peek()) # 应该输出2
print(stack.size()) # 应该输出2
练习2：括号匹配¶
Python
# 练习2：判断括号是否合法
def is_valid(s):
"""
判断括号是否合法
支持三种括号：()、[]、{}
"""
pass
# 测试
print(is_valid("()")) # True
print(is_valid("()[]{}")) # True
print(is_valid("(]")) # False
print(is_valid("([)]")) # False
练习3：逆波兰表达式¶
Python
# 练习3：计算逆波兰表达式
def eval_rpn(tokens):
"""
计算逆波兰表达式的值
支持运算符：+、-、*、/
"""
pass
# 测试
print(eval_rpn(["2", "1", "+", "3", "*"])) # 9
print(eval_rpn(["4", "13", "5", "/", "+"])) # 6
📝 总结¶
核心要点¶
✅ 栈的特点： - 后进先出（LIFO） - 只能在一端操作 - 入栈和出栈都是O(1)
✅ 栈的实现： - Python list：简单高效 - 链表：动态大小 - C++ stack：STL容器
✅ 栈的应用： - 括号匹配 - 逆波兰表达式 - 函数调用栈 - 撤销操作 - DFS
✅ 常见技巧： - 辅助栈 - 延迟删除 - 双栈模拟队列
下一步¶
继续学习： - 队列详解 - 先进先出的数据结构
继续查看队列详解...