栈

#栈

• 什么是栈
• 入栈与出栈
• LIFO 特性
• 调用栈
• 应用场景

#什么是栈

栈是一种数据呈线性排列的数据结构，但有个特殊限制：只能在一端（栈顶）进行数据的添加和删除。

把栈想象成一摞盘子：你只能把新盘子放在最上面，也只能从最上面拿走盘子——不可能从中间抽一个出来。

      ┌──────┐
      │ Red  │ ← 栈顶（最后放入的，最先取出）
      ├──────┤
      │Green │
      ├──────┤
      │ Blue │ ← 栈底（最先放入的，最后取出）
      └──────┘

#入栈与出栈

• 入栈（push）：把数据放到栈顶
• 出栈（pop）：把栈顶的数据取出来

入栈过程:

  放入 Blue        放入 Green       放入 Red
  ┌──────┐         ┌──────┐         ┌──────┐
  │ Blue │         │Green │         │ Red  │ ← 栈顶
  └──────┘         ├──────┤         ├──────┤
                   │ Blue │         │Green │
                   └──────┘         ├──────┤
                                    │ Blue │
                                    └──────┘

出栈过程:

  取出 Red         取出 Green       取出 Blue
  ┌──────┐         ┌──────┐         (空)
  │Green │ ← 栈顶   │ Blue │ ← 栈顶
  ├──────┤         └──────┘
  │ Blue │
  └──────┘

Python 实现：

stack = []

# 入栈
stack.append("Blue")
stack.append("Green")
stack.append("Red")
print(stack)  # ['Blue', 'Green', 'Red']

# 出栈
top = stack.pop()
print(top)    # Red（最后入栈的，最先出栈）
print(stack)  # ['Blue', 'Green']

#LIFO 特性

栈的核心特性是 LIFO（Last In First Out，后进先出）：最后放入的数据，最先被取出来。

入栈顺序: Blue → Green → Red
出栈顺序: Red → Green → Blue（完全反过来！）

想访问栈中间的数据？不行，必须先把上面的数据一个个出栈，直到目标数据到达栈顶。

#调用栈

计算机在内部使用被称为调用栈的栈来管理函数调用。当你调用一个函数时，计算机把函数的局部变量和返回地址压入栈；函数返回时，再弹出。

def greet(name):
    print "hello, " + name
    greet2(name)       # ← 调用 greet2，greet 暂停
    print "bye"
    bye()              # ← 调用 bye

调用 greet("maggie") 时的调用栈变化:

  栈顶 → greet2("maggie")    ← greet2 执行中
         greet("maggie")      ← greet 暂停等待

  栈顶 → greet("maggie")      ← greet2 返回后，greet 恢复

递归函数也使用调用栈——每层递归调用都会压入栈中，这也是为什么递归太深会导致栈溢出。

#应用场景

• 函数调用管理：所有编程语言的函数调用都依赖调用栈
• 括号匹配：读到左括号入栈，读到右括号出栈，检查是否匹配

字符串: ( A B ( C ( D E ) F ) ( G ( ( H ) I J ) K ) )

处理过程:
  ( → 入栈    栈: (
  ( → 入栈    栈: ( (
  ( → 入栈    栈: ( ( (
  ) → 出栈    栈: ( (       ← 与最近的 ( 匹配
  ...

• 撤销操作（Undo）：编辑器的撤销功能用栈保存历史操作
• 表达式求值：后缀表达式的计算使用栈
• 深度优先搜索：候补顶点的管理使用栈（LIFO 特性恰好匹配 DFS 的需求）
• 浏览器后退：访问的页面依次入栈，点后退就出栈

#小结

• 栈只能在一端（栈顶）操作，后进先出（LIFO）
• 入栈（push）和出栈（pop）的时间复杂度都是 O(1)
• 调用栈是栈最重要的应用，管理函数调用和递归
• 只要问题涉及「最后处理的先用到」，就考虑用栈