数据结构与算法 / 系统课时
栈的后进先出模型
栈的后进先出模型
栈只允许在同一端加入、删除和查看元素,因此最后压入的状态会最先被恢复。本课用动态数组实现一个通用栈,并说明栈顶方向、空栈处理和均摊复杂度。
学习目标
- 理解后进先出与栈顶受限访问
- 掌握
push、pop、peek和is_empty - 能分析动态数组实现栈的复杂度与边界
栈的操作模型
依次压入 A、B、C 后,C 位于栈顶,弹出顺序为 C、B、A。浏览器返回、编辑器撤销和函数调用都依赖这种“最近状态优先恢复”的顺序。

常用接口包括:
push:把元素压入栈顶pop:删除并返回栈顶元素peek:读取栈顶但不删除is_empty:判断是否为空
空栈执行 pop 或 peek 属于下溢。本课选择抛出 IndexError,避免把异常状态伪装成正常返回值。
数组实现
动态数组应把末尾作为栈顶。append 和末尾 pop 通常为均摊 O(1),而从头部删除需要移动后续元素,通常为 O(n)。
python
from typing import Generic, TypeVar
T = TypeVar("T")
class ArrayStack(Generic[T]):
def __init__(self) -> None:
# 数组末尾固定作为栈顶
self._items: list[T] = []
def push(self, item: T) -> None:
self._items.append(item)
def pop(self) -> T:
# 主动检查下溢,向调用方提供明确错误
if self.is_empty():
raise IndexError("不能从空栈弹出元素")
return self._items.pop()
def peek(self) -> T:
if self.is_empty():
raise IndexError("空栈没有栈顶元素")
return self._items[-1]
def is_empty(self) -> bool:
return not self._items
def __len__(self) -> int:
return len(self._items)
def main() -> None:
history = ArrayStack[str]()
for page in ["首页", "课程页", "课时页"]:
history.push(page)
print("当前页面:", history.peek())
print("返回:", history.pop())
print("新的栈顶:", history.peek())
print("数量:", len(history))
if __name__ == "__main__":
main()运行命令:
bash
python array_stack.py预期输出:
text
当前页面: 课时页
返回: 课时页
新的栈顶: 课程页
数量: 2边界与封装
peek 只能读取,不能调用底层 pop。内部数组不应直接暴露,否则调用方可以清空或修改中间元素,破坏栈的接口约束。
动态数组扩容时,单次 push 可能达到 O(n),但多次操作的平均成本仍为均摊 O(1)。peek、判空和获取长度为 O(1),空间复杂度为 O(n)。
函数调用时,每次进入函数都会把调用帧压栈,返回时再从栈顶恢复上一层。深度优先搜索同样把尚未继续处理的路径保存在栈中,因此总是优先深入最近发现的分支。
按自己的节奏,确认真正理解。