栈的实现与应用
使用 push、pop 和 peek 实现栈，然后解决有效括号、最小栈和逆波兰表示法求值问题。
栈的实现与应用 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
Stack 数据结构
栈是一种后进先出（LIFO）的数据结构。最后入栈的元素会最先出栈。您可以把它想象成一摞盘子：只能从顶部添加或移除元素。核心操作包括 push（添加到顶部）、pop（从顶部移除）和 peek（读取顶部元素但不移除）。在实现良好的栈中，这三种操作的复杂度都是 O(1)。
在 Python 中，列表可以完美地充当栈：append 相当于 push，pop() 相当于 pop，而 [-1] 相当于 peek。
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]带有 push、pop、peek、isEmpty 的 Stack 类
将列表封装在类中可以提供更清晰的接口，并防止意外使用 insert 等非栈操作，或访问栈顶之外的其他位置。这正是面试官要求您“从零实现一个栈”时所期待的实现方式。
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2有效的括号（LeetCode 20）
LeetCode 20“有效的括号”：判断一个括号字符串是否平衡。遇到每个左括号时，将它入栈。遇到每个右括号时，检查栈顶是否为与之匹配的左括号；如果不匹配，或栈为空，则返回假值。如果遍历结束时栈为空，则该字符串有效。这是编程面试中栈最经典的首个应用。
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # False最小栈（LeetCode 155）
LeetCode 155“最小栈”：设计一个支持 push、pop、peek 和 getMin，且每种操作都为 O(1) 的栈。诀窍是：维护第二个栈，记录每个时刻的最小值。入栈时，如果新值小于或等于当前最小值（或者最小值栈为空），也将新值压入最小值栈。出栈时，如果弹出的值等于当前最小值，也从最小值栈中弹出一个值。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2计算逆波兰表示法
LeetCode 150“计算逆波兰表示法”（后缀表达式）：将操作数入栈；遇到运算符时，弹出两个操作数，应用该运算符，然后将结果入栈。减法和除法尤其需要注意顺序：第一个弹出的操作数是右操作数，第二个弹出的操作数是左操作数。
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22解码字符串（LeetCode 394）
LeetCode 394“解码字符串”：给定一个编码字符串，例如 3[a2[c]]，将其展开为 accaccacc。使用两个栈：一个用于存储重复次数，另一个用于存储累积字符串。遇到数字时，构建完整的数字。遇到 [ 时，将当前字符串和重复次数入栈。遇到 ] 时，弹出它们并重复当前片段。遇到字母时，将其追加到当前字符串。
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'每日温度（单调栈预览）
LeetCode 739“每日温度”：对于每一天，找出还要经过多少天才能遇到更高的温度。暴力方法的复杂度为 O(n²)。使用栈时，遍历温度列表；对于每一天，弹出栈中所有温度低于当天温度的条目（这些条目存储的是日期索引）。这些被弹出日期的答案就是当天索引减去它们的索引。然后将当天索引入栈。栈中剩余的条目始终找不到更高温度，因此答案为 0。
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]使用 Stack 进行 DFS 遍历
递归 DFS 中的调用栈可以由显式栈替代，从而将算法改为迭代实现。先将根节点入栈；当栈非空时，弹出一个节点，处理它，然后将它的子节点入栈（为了从左到右处理，应先压入右子节点，再压入左子节点）。这种迭代 DFS 的行为与递归 DFS 完全相同，但可以避免深层树触发 Python 的递归深度限制。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]时间和空间复杂度
所有栈操作（push、pop、peek、isEmpty）的摊销复杂度都是 O(1)。构建一个包含 n 个元素的栈需要 O(n) 时间。最坏情况下，当所有元素都被存储时，空间复杂度为 O(n)。对于使用单调栈的问题，每个元素最多入栈和出栈一次，因此所有迭代的总体时间复杂度为 O(n)，而不是仅根据朴素的外层循环观察所推测的 O(n²)。
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000直方图中的最大矩形（预览）
LeetCode 84“直方图中的最大矩形”是经典栈问题中最困难的一类。对于每个柱形，以它为高度的矩形向左延伸，直到遇到更矮的柱形；向右延伸也是如此。单调栈按照柱形高度递增的顺序跟踪柱形索引。遇到更矮的柱形时，弹出栈中元素，并使用被弹出柱形的高度计算矩形面积。对于每次弹出操作，栈都能在 O(1) 时间内提供左边界和右边界。
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4栈问题的面试策略
栈问题经常将自己伪装成“从内向外处理”或“查找下一个更大/更小的元素”。以下信号表明栈可能会有帮助：您需要最近见过的元素，需要匹配成对的内容（括号、标签），或者希望在一个朴素方法需要 O(n²) 层嵌套循环的问题上达到 O(n)。尤其是单调栈，可以将“对每个元素查找最近的更大/更小元素”从 O(n²) 降为 O(n)。
在面试中，请清晰地说明栈的不变量：“我将维护一个按高度递减排列的索引栈。”
快速检查
请测试您对本课“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学习了：Python 列表实现了 O(1) 的 push/pop/peek，因此非常适合作为栈；有效的括号和最小栈是栈面试题中最经典的两类问题；以及单调栈通过对每个元素最多进行一次入栈和出栈，在 O(n) 时间内解决下一个更大元素问题。接下来，我们将使用 Python 的双端队列构建队列，并解决滑动窗口最大值问题。
常见问题解答
「栈的实现与应用」课时是免费的吗？
是的 — 「栈的实现与应用」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「栈的实现与应用」这节课中我会学到什么？
使用 push、pop 和 peek 实现栈，然后解决有效括号、最小栈和逆波兰表示法求值问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「栈的实现与应用」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。