数据结构与算法 / 系统课时

栈的后进先出模型

栈的后进先出模型

栈只允许在同一端加入、删除和查看元素,因此最后压入的状态会最先被恢复。本课用动态数组实现一个通用栈,并说明栈顶方向、空栈处理和均摊复杂度。

学习目标

  • 理解后进先出与栈顶受限访问
  • 掌握 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)。

函数调用时,每次进入函数都会把调用帧压栈,返回时再从栈顶恢复上一层。深度优先搜索同样把尚未继续处理的路径保存在栈中,因此总是优先深入最近发现的分支。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

栈的后进先出模型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通