家里叠盘子：洗好的盘子一个压一个往上放，取的时候也只从最上面拿——最先放的反而最后被用。这种「只在一端进出」的存放方式，就是数据结构里的栈。

沿箭头从上往下看：三个元素依次进栈，再依次出栈，注意进出顺序刚好相反。

上一页说栈是「后进先出」。听起来抽象？其实你每天都在用：浏览器后退、Excel 撤销、函数嵌套调用，背后都是同一个栈在悄悄工作。

你已经知道栈是后进先出的容器。但写程序前得先约定：外界只能对它做哪些操作？先把「能做什么」说清楚，再谈「怎么做」，这就是接口与实现的分离。

图中以栈顶为枢纽：所有操作只发生在 top 一端，沿箭头看每次调用如何改变栈顶。

用 Python 抽象基类给出栈接口：五个方法，各自的语义与前置条件。

继承 ABC 强制子类实现全部方法——接口只声明契约；pop 与 peek 的区别在于是否移除元素，空栈是两者共同的边界条件。

pop 一次调用，内部走三步约定，缺一步都不完整。

前面我们把 pop 的约定写得清清楚楚，却从没说过数据放在哪。这正是接口分离的好处：只要行为守约，底层既可以是连续数组，也可以是链式列表。本页先看这两条路线的全貌。

一个数组的两头，左端固定是栈底，右端才是栈顶；size 只是一个计数器，不指向数据本身。

从左往右看：head 永远是栈顶，push 和 pop 都只动头部，不碰后面任何节点。

对照两种实现的 push/pop 源码，看栈顶位置的选择如何决定代码形态。

两边都选 O(1) 端作栈顶：数组选尾部，链表选头部。若数组用头部、链表用尾部，操作都退化为 O(n)。

数组栈和链表栈都能实现栈，但性能与适用场景不同，容易混淆，逐维度对比。

一道选择题检验对栈顶操作与实现取舍的理解

• ✓栈是行为约束：只看栈顶、LIFO，与底层结构无关
• ✓接口与实现分离：使用者只依赖 ADT 操作集
• ✓数组实现：栈顶下标即插入位置，O(1) 增删
• ✓链表实现：头结点即栈顶，天然动态扩容
• ✓边界要约定清楚：空栈 pop、满栈 push 各有定义

先自己想，想不动了再看参考答案——思路比结论重要。