栈结构详解：后进先出的应用场景

在计算机科学中，数据结构是构建高效算法的基石。其中，栈（Stack）作为一种简单但功能强大的线性数据结构，凭借其”后进先出（LIFO, Last In First Out）”的特性，在软件开发中扮演着重要角色。本文将深入解析栈的核心原理、实现方式及典型应用场景，帮助读者掌握这一基础但关键的数据结构。

一、栈的基本概念

1.1 定义与特性

栈是一种遵循LIFO原则的线性数据结构，即最后插入的元素会最先被移除。其操作主要限定在栈顶（Top）进行，类似于一摞盘子：

• 入栈（Push）：将元素添加到栈顶
• 出栈（Pop）：移除并返回栈顶元素
• 窥视（Peek/Top）：查看栈顶元素但不移除
• 判空（IsEmpty）：检查栈是否为空

1.2 抽象数据类型（ADT）

1class Stack:
2    def push(self, item):  # 入栈
3        pass
4    def pop(self):         # 出栈
5        pass
6    def peek(self):        # 查看栈顶
7        pass
8    def is_empty(self):    # 判空
9        pass
10

二、栈的实现方式

2.1 数组实现（静态栈）

1class ArrayStack:
2    def __init__(self, capacity=10):
3        self.items = [None] * capacity
4        self.top = -1  # 栈顶指针
5        self.capacity = capacity
6
7    def push(self, item):
8        if self.top == self.capacity - 1:
9            raise Exception("Stack Overflow")
10        self.top += 1
11        self.items[self.top] = item
12
13    def pop(self):
14        if self.is_empty():
15            raise Exception("Stack Underflow")
16        item = self.items[self.top]
17        self.top -= 1
18        return item
19
20    # 其他方法实现...
21

特点：

• 固定大小，需预先分配内存
• 访问速度快（O(1)）
• 可能发生栈溢出（需动态扩容优化）

2.2 链表实现（动态栈）

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None
5
6class LinkedListStack:
7    def __init__(self):
8        self.top_node = None
9
10    def push(self, item):
11        new_node = Node(item)
12        new_node.next = self.top_node
13        self.top_node = new_node
14
15    def pop(self):
16        if self.is_empty():
17            raise Exception("Stack Underflow")
18        item = self.top_node.data
19        self.top_node = self.top_node.next
20        return item
21
22    # 其他方法实现...
23

特点：

• 动态扩容，无大小限制
• 每个操作需额外指针操作（仍为O(1)）
• 内存开销略大（需存储节点指针）

三、栈的经典应用场景

3.1 函数调用栈

• 机制：系统自动维护调用栈，记录函数调用顺序和局部变量
• 示例：
  c

  1void funcA() {
  2    funcB();  // 调用前压栈
  3}
  4void funcB() {
  5    // 执行中...
  6}  // 返回时弹栈
  7

• 作用：实现递归、保存返回地址、管理局部变量

3.2 表达式求值与括号匹配

• 中缀转后缀（逆波兰表示法）：

  1输入: 3 + 4 * 2 / (1 - 5)
  2输出: 3 4 2 * 1 5 - / +
  3

• 括号匹配算法：
  python

  1def is_valid_parentheses(s):
  2    stack = []
  3    mapping = {')': '(', ']': '[', '}': '{'}
  4    for char in s:
  5        if char in mapping:
  6            top_element = stack.pop() if stack else '#'
  7            if mapping[char] != top_element:
  8                return False
  9        else:
  10            stack.append(char)
  11    return not stack
  12

3.3 浏览器前进/后退功能

• 双栈模型：
  • 前进栈：存储已访问页面
  • 后退栈：存储后退时的页面
• 操作流程：

  1访问A → B → C
  2后退栈: [A, B], 前进栈: []
  3点击后退到B:
  4后退栈: [A], 前进栈: [C]
  5点击前进到C:
  6后退栈: [A, B], 前进栈: []
  7

3.4 撤销操作（Undo/Redo）

• 实现方式：
  • 撤销栈：存储操作历史
  • 重做栈：存储被撤销的操作
• 示例：文本编辑器中Ctrl+Z/Ctrl+Y的实现

3.5 深度优先搜索（DFS）

• 递归实现本质：利用系统调用栈
• 显式栈实现：
  python

  1def dfs_iterative(graph, start):
  2    visited = set()
  3    stack = [start]
  4    while stack:
  5        vertex = stack.pop()
  6        if vertex not in visited:
  7            visited.add(vertex)
  8            # 将邻接节点压栈（注意顺序需反转）
  9            stack.extend(reversed(graph[vertex]))
  10    return visited
  11

四、栈的优化技巧

1. 动态扩容：数组实现时，当容量不足时扩容1.5-2倍
2. 惰性删除：批量删除时仅标记，待栈空时统一回收
3. 双栈技巧：用两个栈实现队列（如LeetCode 232题）
4. 最小栈：辅助栈同步记录最小值（O(1)获取最小元素）