深入理解Python栈函数及其应用207

Python 虽然没有内置专门的“栈”数据结构 (像某些语言那样，例如 C++ 的 `std::stack` )，但我们可以轻松地使用列表 (list) 或 collections 模块中的 deque 来模拟栈的行为。栈是一种后进先出 (LIFO - Last-In, First-Out) 的数据结构，这意味着最后添加的元素将首先被移除。这在许多编程任务中都非常有用，例如函数调用、表达式求值和撤销/重做功能。

使用列表模拟栈

Python 的列表提供了一种简单而直接的方法来实现栈。我们可以使用 `append()` 方法将元素压入栈顶，使用 `pop()` 方法弹出栈顶元素。以下是几个关键操作的示例：```python
stack = [] # 初始化一个空列表作为栈
# 压栈 (push)
(10)
(20)
(30)
print("栈:", stack) # 输出: 栈: [10, 20, 30]
# 弹栈 (pop)
popped_item = ()
print("弹出的元素:", popped_item) # 输出: 弹出的元素: 30
print("栈:", stack) # 输出: 栈: [10, 20]
# 检查栈是否为空
if not stack:
print("栈为空")
else:
print("栈不为空")
# 查看栈顶元素 (不弹出)
if stack:
top_item = stack[-1]
print("栈顶元素:", top_item) # 输出: 栈顶元素: 20
```

这种方法虽然简单，但在处理大量元素时效率可能较低，因为 `append()` 和 `pop()` 操作在列表的末尾进行，而列表在内存中是连续存储的，如果频繁进行插入和删除操作，可能会导致内存频繁的重新分配。

使用模拟栈

`` (双端队列) 提供了比列表更有效的栈实现，尤其是在频繁进行头部和尾部操作时。`append()` 和 `pop()` 操作在 `deque` 的两端都具有 O(1) 的时间复杂度，而列表在头部进行操作的时间复杂度为 O(n)。```python
from collections import deque
stack = deque()
# 压栈
(10)
(20)
(30)
print("栈:", list(stack)) # 使用list()转换方便查看
# 弹栈
popped_item = ()
print("弹出的元素:", popped_item)
# 检查栈是否为空
if not stack:
print("栈为空")
# 查看栈顶元素
if stack:
top_item = stack[-1]
print("栈顶元素:", top_item)
```

`deque` 更适合需要频繁进行压栈和弹栈操作的场景，因为它在性能上优于列表。

栈的应用场景

栈在编程中有着广泛的应用，一些常见的例子包括：
函数调用：程序的函数调用栈。当函数被调用时，其参数、局部变量和返回地址会被压入栈中；当函数返回时，这些信息会被弹出。
表达式求值：后缀表达式 (逆波兰表达式) 的求值。通过栈可以方便地处理运算符优先级和括号匹配。
括号匹配：检查代码或表达式中的括号是否匹配。
深度优先搜索 (DFS)：在图或树的遍历中，栈可以用来存储待访问的节点。
撤销/重做功能：将用户的操作记录到栈中，以便用户可以撤销或重做操作。

一个简单的括号匹配示例```python
from collections import deque
def is_balanced(expression):
stack = deque()
opening_brackets = "({["
closing_brackets = ")}]"
bracket_map = dict(zip(opening_brackets, closing_brackets))
for char in expression:
if char in opening_brackets:
(char)
elif char in closing_brackets:
if not stack or bracket_map[()] != char:
return False
return not stack
expression1 = "((()))"
expression2 = "(()"
expression3 = "([{}])"
expression4 = "((])"
print(f"'{expression1}' is balanced: {is_balanced(expression1)}") # True
print(f"'{expression2}' is balanced: {is_balanced(expression2)}") # False
print(f"'{expression3}' is balanced: {is_balanced(expression3)}") # True
print(f"'{expression4}' is balanced: {is_balanced(expression4)}") # False
```