企业官网建设流程全解析

很多朋友在学数据结构的时候，一到栈这一章就有点松懈，觉得不就是 push 和 pop 嘛，Python 列表自带的 append 和 pop 已经够用了，何必自己再多写一遍？我最初也是这个想法，直到在项目里排查一个和函数调用相关的诡异问题，又帮别人梳理了几道括号匹配和单调栈的算法题，才彻底改观。栈这门课，最值得做的事就是合上书本，用 Python 从头手写一遍顺序栈和链式栈。

这篇内容不是从理论到理论的复述，我会把两种栈的完整代码、每一行的设计意图、边界条件、性能差异和踩坑点全部掰开揉碎。适合正在学数据结构的学生、准备算法面试的开发者，以及任何想真正理解 LIFO 背后工程含义的人。看完之后，你能独立实现栈，也知道在真实项目中应该怎么选型。

1. 为什么我建议亲手实现一遍栈

1.1 栈的本质：后放进去的先拿出来

栈是一种操作受限的线性表，它只允许在一端做插入和删除，这一端叫栈顶。用生活里最经典的现象来解释，就是自助餐厅叠盘子的弹簧托盘：新洗好的盘子总是放在最上面，取盘子时也总是先取最上面那一个。最先放进去的盘子在最底下，要等所有后放的盘子都被拿完，才轮得到它。

这个规则有一个专门的名字，叫 LIFO（Last In First Out），后进先出。与之对应的是队列的 FIFO（First In First Out），先进先出，就像奶茶店排队，先到的人先买到奶茶。

栈的“操作受限”看起来是缺点，但它恰恰是优点。因为限制住了操作位置，很多问题的处理流程就变得非常清晰：要么在栈顶放入数据，要么在栈顶取出数据，没有中间地带的模糊操作。计算机科学里凡是出现“需要记住现场，最后再恢复现场”的场景，几乎都可以用栈来表达。

1.2 三个高频应用场景，帮你建立直觉

第一个场景是函数调用。Python 解释器每调用一个函数，就会往调用栈里压入一个栈帧，里面保存着局部变量、返回地址这些信息。函数执行完毕，栈帧被弹出，程序回到上一个函数继续执行。递归特别深时会抛出栈溢出，就是因为调用栈本身有容量限制。

第二个场景是浏览器的前进后退。你访问了页面 A，点进页面 B，再点进页面 C，浏览器会把 A、B 依次压入一个栈。当你点后退按钮时，C 被弹出，回到 B；再后退，B 被弹出，回到 A。每一步操作都是栈顶动作，非常标准。

第三个场景是编辑器的撤销功能。每次操作都被压入撤销栈，按 Ctrl+Z 时从栈顶弹出一条操作并执行反向动作。如果你撤销之后再做了新操作，很多编辑器会把原来的撤销栈清空，这本质上就是丢弃栈顶以上内容。

这些场景共同说明一件事：栈不只是一个考试用的数据结构，它是真实软件系统里反复出现的基础设施。理解了栈，你才算真正理解了函数调用、DFS 遍历、表达式求值这些看起来毫不相关的技术背后共同的骨架。

1.3 为什么同时做顺序和链式两种实现

同一个栈的逻辑可以对应完全不同的存储方式。顺序栈使用连续的内存空间，在 Python 里最直接的模拟就是列表；链式栈则使用彼此独立的节点，通过引用把节点串起来。

有朋友问我，既然 Python 列表已经实现了动态数组，顺序栈直接用列表不就行了？这话对了一半。直接用列表确实够用，但如果你不知道列表底层扩容时发生了什么，遇到性能抖动、内存占用异常时就会一头雾水。链式栈同样如此，它解决了顺序栈“扩容要整体拷贝”的问题，代价是每个节点都要额外存一个指针，节点创建和销毁也有开销。

课程作业和面试里经常要求“用 Python 实现栈的基本操作”，考察的正是你能不能把这套存储逻辑讲清楚、写明白。两种实现不是二选一，而是互为镜像，对照着写一遍，你对“数据结构 = 逻辑结构 + 存储结构 + 操作集”这句话的理解会上一个台阶。

2. 顺序栈：拿 Python 列表模拟定长数组

2.1 基础类框架与核心方法

顺序栈的核心思路是：用一段连续的内存存储栈元素，用栈顶指针标记当前栈顶位置。Python 的列表天生就是动态数组，尾部追加和弹出都非常高效，所以顺序栈的代码可以写得很短。

class ArrayStack: """固定容量的顺序栈""" def __init__(self, capacity=10): if capacity <= 0: raise ValueError("capacity must be positive") self._items = [] self._capacity = capacity def is_empty(self): return len(self._items) == 0 def is_full(self): return len(self._items) == self._capacity def push(self, item): if self.is_full(): raise OverflowError("stack is full") self._items.append(item) def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") return self._items.pop() def peek(self): if self.is_empty(): raise IndexError("peek from empty stack") return self._items[-1] def size(self): return len(self._items) def __len__(self): return self.size() def __repr__(self): return f"ArrayStack({self._items!r})"

这个类里，底层存储是self._items，一个 Python 列表；self._capacity表示栈能容纳的最大元素个数。为什么要在列表外面再套一层容量限制？因为经典的顺序栈设计是“定长数组”，一旦数组满了就不能继续入栈，否则会覆盖未分配的内存，这在 C 语言里是严重错误。Python 的列表会自动扩容，平时用不到这个限制，但教学和面试场景里，模拟定长数组能逼你思考“栈满”这种边界情况。

2.2 边界条件才是顺序栈的重点

很多人第一次写顺序栈，光顾着把 push、pop 写完，忽略了两个关键动作：入栈前要判满，出栈前要判空。

判满的意义在于，顺序栈有容量上限。如果忽略is_full()，在真正定长数组的实现里会越界写入，破坏相邻内存数据；在 Python 的模拟版本里，栈会继续扩张，变成一个“没有上限的假顺序栈”。判空的意义则更直接，对空栈做 pop 或 peek 会报错。代码里我选择抛IndexError，这也是 Python 内置列表对越界操作的默认行为，语义上保持一致。

还有一种值得注意的情况：peek和pop都是从栈顶取数据，但peek不删除元素，pop会删除元素。写过一次之后你会发现，它们前半段逻辑几乎一样，都是先判空，再访问self._items[-1]。区别只在最后一行：peek返回self._items[-1]，pop调用self._items.pop()。

把这两个方法分开，是因为真实场景里两种需求都存在。比如括号匹配只需要看栈顶是什么，不需要立刻弹掉；而撤销操作一旦拿到操作记录，就应该立刻弹出。接口清晰，调用方就能各取所需。

2.3 顺序栈的“扩容”原理与摊还复杂度

现在聊聊 Python 列表到底是怎么扩容的。列表底层是一个动态数组，一开始可能只分配了几个元素的空间。每次 append 时，如果当前空间足够，就直接写入，非常快；如果空间不够，解释器会申请一块更大的新内存，把旧元素整体拷贝过去，再释放旧空间。

这就好比一个停车场，停满之后只能去旁边新建一个更大的停车场，把所有车一辆一辆挪过去。单次扩容确实很慢，但扩容发生的频率很低。假设每次扩容把容量扩大到原来的两倍，那么在整个生命周期里，各次 append 的总拷贝次数加起来只有 O(n)，平均到每一次 append 上就是 O(1)。这就是摊还复杂度分析：单个操作可能很贵，但批量操作的平均成本很好看。

Python 3 的列表扩容并不是严格的 2 倍，它的策略更复杂，会根据元素大小调整扩容比例，但总体思路一致：用少量的大开销扩容换取大量的小开销追加，换来平均 O(1) 的尾部插入性能。这也解释了为什么顺序栈的 push 和 pop 在大多数时候都很快，只有在偶尔触发扩容那一刻才会有明显的卡顿。

如果你希望顺序栈完全可控，也可以自己实现扩容，在push里检测到栈满后，创建新列表并拷贝self._items。不过在 Python 里这么做通常没有意义，因为内置列表已经帮你做了这件事，重复造轮子反而更慢。

3. 链式栈：用节点和引用串起一条链

3.1 节点类与栈类的完整实现

链式栈的思路是，每个元素都放在一个独立的节点里，节点之间通过引用连接。栈顶就是链表的头节点，入栈、出栈都发生在头部。下面是一份完整的实现。

class Node: """链式栈的节点""" def __init__(self, data): self.data = data self.next = None class LinkedStack: """链式栈，栈顶为链表头""" def __init__(self): self._head = None self._size = 0 def is_empty(self): return self._head is None def push(self, item): node = Node(item) node.next = self._head self._head = node self._size += 1 def pop(self): if self.is_empty(): raise IndexError("pop from empty LinkedStack") data = self._head.data self._head = self._head.next self._size -= 1 return data def peek(self): if self.is_empty(): raise IndexError("peek from empty LinkedStack") return self._head.data def size(self): return self._size

内层类Node只有两个属性：data存数据，next存下一个节点的引用。外层类LinkedStack维护一个_head指向链表的第一个节点，并维护_size记录节点数量。

这里有两个设计细节值得注意。第一，栈顶对应链表头，而不是链表尾。第二，用_head是否为空来判断栈是否为空，比用_size == 0更直接，而且不会因为忘记维护_size而出错。

3.2 关键代码逐行解释：为什么入栈要头插、出栈要头删

链式栈最核心的两行代码在push里：

node.next = self._head self._head = node

这就是头插法。新节点的next先指向当前的头节点，也就是现在的栈顶；然后更新_head，让新节点成为新的头节点，新节点变成新的栈顶。两步顺序不能反。如果先写self._head = node，原来的链表就丢失了，node.next也指不到任何有效节点。

为什么不用尾插？因为单向链表只有一个方向，从_head出发可以快速找到第一个节点，但要想找到最后一个节点，必须从头开始一个节点一个节点地走完整个链表，这是 O(n) 操作。如果入栈和出栈都在尾部进行，每次都要遍历链表，栈就失去了 O(1) 操作的优势。

出栈时执行的是一对相反操作：

data = self._head.data self._head = self._head.next

先把栈顶节点的数据取出来，再把_head向后移一个节点，相当于从链表中摘除原栈顶。这一步不能先移动_head再取数据，不然原来的节点引用就丢了，数据也拿不到了。

3.3 操作演练与边界检查

我们来实际运行一下这个链式栈，感受 LIFO 顺序。

s = LinkedStack() s.push("第一层") s.push("第二层") s.push("第三层") print(s.size()) # 3 print(s.peek()) # 第三层 print(s.pop()) # 第三层 print(s.pop()) # 第二层 print(s.is_empty()) # False print(s.pop()) # 第一层 print(s.is_empty()) # True

压入三个字符串之后，栈顶是最后一次压入的“第三层”。连续两次 pop 弹出的是“第三层”和“第二层”，这说明后进先出原则生效了。等三个元素全部弹出后，栈为空。

链式栈没有“满”的概念。天然条件下，只要系统还能分配内存，就可以继续 push 新节点。所以LinkedStack里我只实现了is_empty，没有实现is_full。这是链式栈和固定容量顺序栈最明显的差异之一：顺序栈说“满了”，链式栈只会说“内存不够了”。

从空间占用上看，链式栈每个节点存了两样东西：数据和引用。Python 里每个对象都有额外开销，节点还涉及对象创建、引用计数更新等操作，所以链式栈的实际内存占用通常比列表高不少。但它也有一个好处：不会预留多余容量，用多少分配多少，不存在“扩容时整体拷贝”的瞬间。

4. 栈的经典应用：写一个括号匹配工具

4.1 需求与算法思路

栈最经典的应用之一就是检查字符串里的括号是否合法。编译器、IDE、文本编辑器里到处都能见到这个需求：你写((a + b) * (c - d))没问题，但写(a + b))就会报错，因为多了一个右括号。

处理规则很简单：遇到左括号就入栈，遇到右括号就去栈顶找一个左括号跟它匹配。如果栈顶不是对应的左括号，说明不匹配；如果遇到右括号时栈是空的，说明没有左括号可配；如果字符串遍历完，栈里还有左括号，说明后面缺少右括号。

为什么用栈？因为括号的嵌套结构与 LIFO 天然吻合：最后一个出现的左括号，要匹配第一个出现的右括号。也就是说，后出现的左括号先被消费，这就是标准的栈行为。

4.2 完整代码与运行效果

def is_balanced(s): stack = [] pairs = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in '([{': stack.append(ch) elif ch in ')]}': if not stack or stack[-1] != pairs[ch]: return False stack.pop() return not stack

这里有三个判断点。第一个是stack.append(ch)，左括号入栈。第二个是if not stack，遇到右括号但栈为空，说明右括号没有对应左括号。第三个是stack[-1] != pairs[ch]，栈顶左括号和当前右括号不配对，比如字符串(]这种情况。

测试几个例子：

print(is_balanced("()")) # True print(is_balanced("()[]{}")) # True print(is_balanced("(]")) # False print(is_balanced("([)]")) # False print(is_balanced("{[]}")) # True

([)]是个特别能说明问题的例子。每个左右括号单独看都存在，但嵌套关系不对：中间的[应该先和后面的]匹配，结果却先把(和)配在了一起。用栈来模拟时，遍历完(和[后栈里是['(', '[']，遇到]时栈顶是[，匹配成功，弹出栈顶；遇到)时栈顶是(，也匹配成功。按这个流程走完，栈是空的。如果你觉得这个结果不对，需要再想想，这里的嵌套关系其实是([)]，并不是合法的交叉嵌套。用栈判定时，流程完全取决于遍历顺序，交叉嵌套会被正确判为合法？不会，因为栈只允许后入先出，遇到]时它只能看到当前栈顶[，看不到更底下的(，它会把[弹掉。之后遇到)时栈顶是(，正好匹配。最终栈空，返回 True 吗？不对，我把这个例子的流程重新想一遍。遍历(：入栈。遍历[：入栈。栈现在是["(", "["]。遍历]：栈顶是[，匹配，弹出。栈现在是["("]。遍历)：栈顶是(，匹配，弹出。栈现在空。返回 True。可实际上([)]是不合法的括号序列，但上面的算法居然返回 True？我再想想。哦，不对，遍历顺序里，([)]的字符顺序是(、[、)、]。栈顶匹配时，遇到)时栈里只有["("]，匹配成功；遇到]时栈是空的，return False。所以结果是 False。是我刚才遍历顺序搞错了，正确的是按字符串顺序(→[→)→]。所以这个算法正确返回 False。好，那我写代码没问题，这个例子确实能验证算法能识别交叉嵌套不合法。测试里我写的是([)]，结果是 False，没毛病。

运行效果就是上面注释里的结果，最后一个{[]}是多层嵌套，返回 True。

4.3 从括号匹配延展出的同类问题

括号匹配这个模型可以扩展出很多高频问题。比如 HTML/XML 标签匹配，<div>入栈，遇到</div>时检查栈顶，原理完全一样。再比如计算器的中缀表达式转后缀表达式，数字直接输出，运算符要根据优先级决定是否压栈和弹栈，核心依旧是对栈的运用。

还有一个常见变体是“最长有效括号长度”：给定一串括号，找到最长连续合法括号子串的长度。这类问题不只要判断是否合法，还要在遍历过程中记录位置信息，需要结合栈和下标计算。做题时如果发现某个问题的解法和“最近配对”有关，第一反应就应该是栈。

5. 顺序栈 vs 链式栈：选型对比与实操心得

5.1 一张表看透两种栈的差异

这个表最值得注意的其实是“摊还 O(1)”和“严格 O(1)”的区别。列表的 append 在单次扩容瞬间会比较慢，但整体均摊下来很快；链式栈每次 push 都要创建新节点，单次操作都是 O(1)，但常数项比列表 append 大，速度也不见得更快。

5.2 什么时候选顺序栈，什么时候选链式栈

先给结论：绝大多数场景下，直接用 Python 内置列表当栈就够了。Python 的列表经过重度优化，尾部插入弹出非常稳定，而且内存布局连续，遍历和访问缓存都很友好。如果你只是写算法题、处理临时数据，顺序栈是默认选择。

什么时候选链式栈？第一，栈的元素个数在创建时完全无法估计，又特别关注“不浪费内存”；第二，需要频繁实现栈的拷贝或拆分，链表结构在拆分时只改几个引用，而顺序栈可能要把整个数组复制一遍；第三，你在学习链表，想通过链式栈巩固对指针和引用的理解。

如果是嵌入式、底层 C 语言环境，顺序栈固定容量能避免频繁 malloc 和 free，性能更稳定，所以语言不同、结论也不同。Python 里开发效率和可读性优先，纠结顺序和链式的时间通常不如直接写一版跑起来看效果。

6. 常见问题与排查技巧实录

6.1 空栈操作：不入栈就弹栈的崩溃现场

新手最常见的错误就是对空栈执行 pop 或 peek。很多教程为了简洁，会在示例里直接写stack.pop()，但没有任何一个正常业务的流程能保证栈在每次弹出前一定有元素。

我建议你在自己的栈实现里显式判空并抛出异常，而不是静默处理。有人为了省事写成if not self._items: return None，这看起来安全，实际上会把“程序逻辑错误”隐藏成“数据为空”，后续排查时反而更痛苦。让异常尽早暴露，才能尽早发现调用方的问题。

6.2 头插顺序写反，节点直接丢了一半

链式栈里最经典的崩溃现场是push方法写错顺序，比如写成：

self._head = node node.next = self._head

第二行执行时，self._head已经被替换成新节点了，node.next指向自己，原来的整个链表全部丢失。这种 bug 不会立刻报错，只是栈里元素神秘消失，或者遍历时死循环，排查起来非常费劲。

我的习惯是写代码时把指针操作的顺序念出来：先让新节点右手抓住旧栈顶，再让_head指向新节点。先抓后换，顺序不会错。另外，一定要维护好_size，push 加一、pop 减一，漏一步就会导致 size 和实际元素数量不一致。

6.3 命名与方法签名，方便自己也方便别人

实现栈时尽量统一方法名：push、pop、peek、is_empty、size。Python 内置 queue 模块里的LifoQueue用的是put和get，很多新手混用之后痛苦不堪。统一命名后，以后你在不同项目之间切换栈实现时，几乎不用看文档就能直接上手。

私有属性加下划线，比如_head、_size、_items、_capacity，提醒自己和调用方不要直接访问内部状态。类名用名词，比如ArrayStack、LinkedStack，一眼就能看出底层结构。这些都是很小的习惯，但代码一复杂，这些细节会明显减少返工次数。

我在实际写代码的过程中，最大的体会是你自己亲手写过一遍顺序栈和链式栈之后，再看递归函数、深度优先搜索、表达式求值这些内容，视角会完全不一样。以前只觉得这些话题各自独立，现在你一眼就能认出“这里其实是在用栈”，因为你自己实现过栈顶指向怎么变、空栈怎么保护、满栈怎么处理。建议你拿到这份代码后不要只是读一遍，把关键几行遮住重新默写，写错几次印象更深。这个基本功看似简单，后面能帮你省下不少查资料的功夫。