栈：后进先出（LIFO）

---

元数据卡

属性	值
章节编号	Vol 2 · 第3章 · 栈
难度等级	（入门加固）
前置知识	数组、链表（第2章）
核心技能	LIFO 操作、数组栈与链表栈、括号匹配
关键字	Stack LIFO push pop peek

---

你的进度

你跳进一条死胡同。唯一的活路是一扇从外面推开的门——最后放进去的东西，恰恰是打开门的钥匙。

栈 = 后进先出（LIFO — Last In First Out）

手边只有树枝和泥巴：

Python

class ArrayStack:
    """数组实现的栈 —— 底层就是 Python list"""

    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)          # 尾部添加 O(1)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()          # 尾部弹出 O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

st = ArrayStack()
st.push("🔑 钥匙"); st.push("🧱 砖头"); st.push("🐗 野猪")
print(st.pop())   # 🐗 野猪 —— 后进先出
print(st.pop())   # 🧱 砖头
print(st.pop())   # 🔑 钥匙

Java 差异： Java 官方推荐用 ArrayDeque 代替 Stack：Deque<String> s = new ArrayDeque<>(); s.push(x); s.pop();

C++ 差异： std::stack 默认底层是 std::deque，没有 peek()，需先 top() 再 pop()。

---

链表实现 —— 反向思考

野猪追得太紧，得换个思路——用节点串起来：

Python

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class LinkedStack:
    """链表栈 —— push/pop 全部在头部 O(1)"""

    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, item):
        self._head = Node(item, self._head)
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self._head.value
        self._head = self._head.next
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._head.value

    def is_empty(self):
        return self._head is None

    def __len__(self):
        return self._size

# 对比
ast = ArrayStack()
lst = LinkedStack()
for i in range(5):
    ast.push(i); lst.push(i)
for _ in range(5):
    print(f"数组栈: {ast.pop()} | 链表栈: {lst.pop()}")

区别在哪？ 数组栈偶尔扩容痛一下（均摊 O(1)），链表栈每次分配节点（常数开销大但时间稳定）。

---

常见陷阱

括号匹配 —— 栈的绝配

[{()}] 是对的，[(]) 是错的。编译器就这么判断——用栈。

Python

def is_valid_brackets(s: str) -> bool:
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '({[':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pair[ch]:
                return False
    return not stack

for t in ["()", "({[]})", "({[}])", "(", "]"]:
    print(f"{'✅' if is_valid_brackets(t) else '❌'} {t}")

为什么是栈？ 最近出现的左括号必须最先被匹配——这就是 LIFO。

---

验收标准

• [ ] 手写数组栈和链表栈，说出各自的内存/性能特点
• [ ] 解释括号匹配为什么非栈不可——能用队列做吗？

---

旅人笔记

1. 栈 = 后进先出。核心操作：push / pop / peek。
2. 数组栈：list.append() + list.pop()，天然就是栈。
3. 链表栈：头部操作 O(1)，每个节点独立分配。
4. 括号匹配：左括号压栈，右括号和栈顶比——编译器每天都在做。

---

→ 下一站预告

继续读 第3章：队列——先进先出，看看单行河上怎么顺序通行。

代码仓库位置： vol-02-dsa/examples/ch03/ 下有此章完整示例代码