栈

栈（Stack） 是一种基于后进先出（Last In, First Out – LIFO）原理的数据结构。栈类似于日常生活中的“子弹夹”：最新插入的元素最先被移除。以下是详细的讲解，涵盖栈的基本概念、实现方式以及应用场景。

1. 栈的基本概念

定义

• 栈是一种线性数据结构，允许在表的一端进行插入和删除操作。
• LIFO原则：后进先出，即最后插入的元素最先被移除。

特点

• 访问限制：

  • 仅能在栈顶（Top）进行插入和删除操作。栈没有提供直接访问中间元素的方法。

• 适用场景：

  • 函数调用：存储函数调用时的返回地址，实现递归调用。
  • 表达式求值：处理数学表达式的计算顺序。
  • 撤销机制：如文本编辑器中的“撤销”功能。

2. 栈的操作

基本操作

栈主要包括以下几种基本操作：

• 初始化（Initialization） ：

  • 创建一个空栈，准备进行插入和删除操作。

• 判空（IsEmpty） ：

  • 检查栈是否为空。如果栈中没有元素，则返回 true；否则返回 false。

• 入栈（Push） ：

  • 向栈顶插入一个新元素。
  • 如果栈已满（溢出），则需要处理溢出情况，如抛出异常或扩展栈的容量。

• 出栈（Pop） ：

  • 从栈顶移除并返回一个元素。
  • 如果栈为空（下溢），则需要处理下溢情况，如抛出异常。

• 取栈顶元素（Peek/Top） ：

  • 返回栈顶元素但不移除它。适用于需要查看栈顶元素而不破坏栈结构的场景。

示意图

       +-------+
   Top |   A   |
       +-------+
       |   B   |
       +-------+
       |   C   | <--- 栈底
       +-------+

在这个示例中，若执行一次 Push(D)，栈将变为：

       +-------+
   Top |   D   |
       +-------+
       |   A   |
       +-------+
       |   B   |
       +-------+
       |   C   |
       +-------+

执行一次 Pop() 将移除栈顶元素 D：

       +-------+
   Top |   A   |
       +-------+
       |   B   |
       +-------+
       |   C   | <--- 栈底
       +-------+

3. 栈的实现方式

1. 数组实现

优点：

• 简单易实现。
• 随机访问效率高。

缺点：

• 固定容量，可能浪费空间或溢出。
• 扩容操作复杂且可能导致数据迁移。

示例代码（Python）：

class Stack:
    def __init__(self, capacity):
        self.stack = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def push(self, item):
        if self.top + 1 >= len(self.stack):
            raise IndexError("Stack overflow")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        popped_item = self.stack[self.top]
        self.stack[self.top] = None
        self.top -= 1
        return popped_item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[self.top]

# 使用示例
stack = Stack(3)
stack.push('A')
stack.push('B')
print(stack.peek())   # 输出: 'B'
print(stack.pop())    # 输出: 'B'
print(stack.is_empty())  # 输出: False

2. 链表实现

优点：

• 动态扩展，容量无限制。
• 灵活管理内存。

缺点：

• 访问效率低于数组（需要从栈底遍历到栈顶）。

示例代码（Python）：

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

class LinkedListStack:
    def __init__(self):
        self.top = None

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

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack underflow")
        popped_item = self.top.data
        self.top = self.top.next
        return popped_item

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.top.data

# 使用示例
stack = LinkedListStack()
stack.push('A')
stack.push('B')
print(stack.peek())   # 输出: 'B'
print(stack.pop())    # 输出: 'B'
print(stack.is_empty())  # 输出: False

4. 栈的应用场景

1. 函数调用管理

在编程语言中，函数调用使用栈来存储返回地址和局部变量。每次调用新函数时，当前的执行状态（如寄存器值和程序计数器）被压入栈中；函数返回后，从栈中弹出最近一次的执行状态。

2. 表达式求值

• 中缀表达式转后缀表达式：使用栈将中缀表达式转换为便于计算的后缀表达式（逆波兰表示法）。

  示例：

  中缀表达式: A + B * C
  后缀表达式: A B C * +

• 后缀表达式求值：使用栈进行计算，遇到操作数时入栈；遇到运算符时弹出相应数量的操作数，执行运算并将结果压回栈中。

3. 撤销和重做

许多应用程序（如文本编辑器、绘图软件）使用栈来实现撤销和重做功能。每一步操作的结果被推入栈中，用户可以按需从栈中弹出最近的操作以撤销。

4. 迷宫求解

在解决迷宫问题时，栈可以用作深度优先搜索（DFS）的辅助工具。每次探索一条新路径时，当前路径的状态被压入栈中；如果发现死胡同，则回溯到上一步并尝试其他方向。

5. 常见面试问题

1. 栈实现队列

问题描述：如何使用两个栈来实现一个队列？

解答思路：

• 使用两个栈 stack_in 和 stack_out。
• 入队时，将元素压入 stack_in。
• 出队时，如果 stack_out 为空，则将 stack_in 中的所有元素依次弹出并压入 stack_out，此时 stack_out 的栈顶元素即为队列的前端元素。

示例代码（Python）：

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, item):
        self.stack_in.append(item)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if not self.stack_out:
            raise IndexError("Queue is empty")
        return self.stack_out.pop()

    def is_empty(self):
        return not self.stack_in and not self.stack_out

2. 检测括号匹配

问题描述：给定一个字符串，判断其中的括号是否正确匹配。

解答思路：

• 使用栈来存储左括号。
• 遇到右括号时，检查栈顶元素是否为对应的左括号。如果匹配则弹出栈顶元素；如果不匹配或栈为空，则括号不匹配。

示例代码（Python）：

def is_valid_parentheses(s: str) -> bool:
    stack = []
    matching_braces = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in matching_braces.values():
            stack.append(char)
        elif char in matching_braces.keys():
            if not stack or stack.pop() != matching_braces[char]:
                return False
        else:
            # Ignore non-bracket characters
            continue

    return not stack

# 测试用例
print(is_valid_parentheses("()"))  # 输出: True
print(is_valid_parentheses("(]"))  # 输出: False
print(is_valid_parentheses("([])"))  # 输出: True

3. 括号嵌套的最大深度

问题描述：给定一个字符串，其中包含括号 ( 和 )，返回括号嵌套的最大深度。

解答思路：

• 使用栈来跟踪括号的嵌套层次。
• 遇到左括号时，将当前深度加1并压入栈中。
• 遇到右括号时，弹出栈顶元素（即对应左括号的深度）。
• 维护一个变量记录最大深度。

示例代码（Python）：

def max_depth_parentheses(s: str) -> int:
    stack = []
    max_depth = 0

    for char in s:
        if char == '(':
            current_depth = (stack[-1] + 1) if stack else 1
            stack.append(current_depth)
            max_depth = max(max_depth, current_depth)
        elif char == ')':
            if not stack:
                return -1  # Unmatched right parenthesis
            stack.pop()

    return max_depth

# 测试用例
print(max_depth_parentheses("((()))"))  # 输出: 3
print(max_depth_parentheses("(())()"))  # 输出: 2

4. 栈的复杂度分析

• 时间复杂度：

  • 初始化、判空、入栈和出栈操作的时间复杂度均为 (O(1))。

• 空间复杂度：

  • 数组实现的空间复杂度为 (O(n))，其中 (n) 是栈中元素的数量。
  • 链表实现的空间复杂度同样为 (O(n))，但避免了固定容量的限制。

6. 常见误区与注意事项

1. 栈与队列的区别

• 栈：LIFO（后进先出），仅允许在栈顶进行插入和删除。
• 队列：FIFO（先进先出），允许在一端插入，在另一端删除。

两者在操作顺序上截然不同，因此在不同的应用场景下适用的工具也不同。

2. 栈溢出与下溢

• 栈溢出：

  • 当栈满时继续进行 Push 操作会引发“栈溢出”错误。
  • 需要预先设定栈的最大容量，并在操作前检查是否已满。

• 栈下溢：

  • 当栈空时继续进行 Pop 操作会引发“栈下溢”错误。
  • 在执行 Pop 或 Peek 前，应先调用 IsEmpty 进行判断。

3. 栈的实现选择

• 数组：适合固定大小的场景，实现简单但可能浪费空间。
• 链表：适用于动态大小的场景，内存管理灵活但访问效率较低。