3.1.1 栈：受限操作为什么反而有力量

栈是只允许在一端插入和删除的线性表。允许操作的一端叫栈顶，另一端叫栈底；后进入的元素先退出，即 LIFO。限制的是操作位置，不是存储方式：数组和链表都可实现栈。

基本接口包括初始化、判空、入栈、出栈和读栈顶。出栈会删除栈顶元素，读栈顶只观察不修改。空栈执行二者都必须报告失败，不能返回某个普通整数冒充错误，因为那个整数也可能是合法数据。

手工推演：空栈依次 push A,push B,pop,push C,push D,pop。栈从底到顶依次为 [A]、[A,B]、[A]、[A,C]、[A,C,D]、[A,C]，两次弹出 D? 注意第一次弹出 B，第二次弹出 D。草稿中固定左边为栈底，可防止方向翻转。

判断出栈序列时，模拟唯一可行策略：输入序列的下一个元素不断入栈，若栈顶等于目标输出便弹出；最终无法匹配则不合法。对输入 1,2,3，3,1,2 不可能，因为弹出 3 后栈顶是 2，不可能越过 2 先取 1。

错解反馈：把“先进后出”理解为最先入栈者永远最后离开，忽略中途可弹出；把栈顶固定为数组高地址，也混淆了抽象规则与实现约定。

迁移题：输入 1,2,3,4，判断 2,1,4,3 是否可行。答案可行：入 1、2，出 2、1；再入 3、4，出 4、3。独立验收：能对任意序列逐步画栈，并在失败点说明是哪一个元素阻挡目标。