🧮 栈 (Stack)

难度 / Difficulty: 简单 (Easy)
分类 / Category: 数据结构 (Data Structure)
操作复杂度 / Operations: 全部 O(1)
空间复杂度 / Space Complexity: O(n)

📖 算法简介 / Introduction

栈是一种后进先出（Last In First Out, LIFO）的数据结构。就像一叠盘子，只能从最上面放和取。

A stack is a Last In First Out (LIFO) data structure. Like a stack of plates — you can only add or remove from the top.

核心操作：Push（压入） 和 Pop（弹出）

💡 算法原理 / Principle

核心特性

• LIFO：最后进入栈的元素最先出来
• 只允许栈顶操作：不能访问或删除栈中间的元素
• 方向单一：从一端进，从同一端出

基本操作

📝 代码实现 / Implementation

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, x):
        self.stack.append(x)
    
    def pop(self):
        if self.stack:
            return self.stack.pop()
        return None
    
    def top(self):
        if self.stack:
            return self.stack[-1]
        return None
    
    def empty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

✨ 示例 / Example

操作序列：
push(1)  →  [1]
push(2)  →  [1, 2]
push(3)  →  [1, 2, 3]
pop()    →  返回 3，栈变为 [1, 2]
pop()    →  返回 2，栈变为 [1]
top()    →  返回 1，栈仍为 [1]

🎯 适用场景 / Scenarios

• 函数调用栈 — 程序执行时的调用栈（递归调用）
• 括号匹配 — 验证括号是否匹配（{[()]})
• 撤销操作 — 编辑器的 Ctrl+Z 撤销
• 表达式求值 — 中缀转后缀表达式
• 深度优先搜索（DFS） — 用栈实现 DFS

Function call stack (recursion), Bracket matching, Undo operations (Ctrl+Z), Expression evaluation (infix to postfix), DFS implementation.

🔄 与队列对比 / Comparison with Queue