栈、队列与单调栈
High Contrast
Dark Mode
Light Mode
Sepia
Forest
13 min read2,532 words

栈、队列与单调栈

简介

在算法与数据结构的世界里，栈（Stack）和队列（Queue）是两种最基础、最核心的线性数据结构。它们以其简单而强大的操作逻辑，构成了无数复杂算法和系统设计的基石。栈遵循后进先出（LIFO）的原则，如同叠放的盘子，最后放上去的总是最先被取走。队列则遵循先进先出（FIFO）的原则，模拟了现实生活中的排队场景，先到者先得。理解它们的特性和操作，是迈向算法精通的第一步。

然而，基础数据结构的力量远不止于此。当我们将栈与特定的问题解决策略相结合时，便能衍生出威力巨大的高级工具，例如单调栈。单调栈通过在栈的维护过程中强制保持元素的某种单调性（递增或递减），能够以线性时间复杂度高效解决一系列看似复杂的问题，如寻找“下一个更大元素”或计算“柱状图中的最大矩形面积”。这种从基础到进阶的演变，完美体现了算法思维的精髓：用简单的规则解决复杂的问题。

与此同时，队列也有其强大的变体——优先队列。它不再遵循严格的先进先出，而是根据元素的“优先级”来决定出队顺序，优先级最高的元素最先出队。这种特性使其成为实现任务调度、合并K个有序链表等算法的理想选择。在Python中，我们可以通过heapq模块轻松实现一个基于最小堆的优先队列。本章将深入探讨这些核心数据结构的基础操作、进阶应用以及它们在实际算法问题中的实战技巧。

核心概念

栈（Stack）

栈是一种操作受限的线性表，只允许在一端（称为栈顶）进行插入（入栈，push）和删除（出栈，pop）操作。栈的另一个基本操作是查看栈顶元素（peek），而不移除它。栈的特性使其非常适合处理具有嵌套或回溯性质的问题，例如函数调用栈、括号匹配、表达式求值以及深度优先搜索（DFS）。

队列（Queue）

队列是另一种操作受限的线性表，它允许在一端（队尾）进行插入（入队，enqueue），在另一端（队头）进行删除（出队，dequeue）。队列的特性使其天然适用于需要按序处理的场景，如广度优先搜索（BFS）、缓存实现（如FIFO缓存策略）以及各种消息队列系统。

单调栈（Monotonic Stack）

单调栈是栈的一种特殊用法，其核心在于在元素入栈的过程中，动态地维护栈内元素的单调性（单调递增或单调递减）。当需要处理“寻找每个元素右侧第一个更大/更小元素”这类问题时，单调栈能以O(n)的时间复杂度高效解决。基本思路是：遍历数组，当新元素破坏栈的单调性时，则不断弹出栈顶元素，直到单调性恢复。每次弹出时，新元素就是被弹出元素的“下一个更大（或更小）元素”。

优先队列（Priority Queue）与堆（Heap）

优先队列是一种抽象数据类型，其中的每个元素都有一个关联的“优先级”。出队操作总是移除优先级最高（或最低）的元素，而非最先进入队列的元素。堆（通常指二叉堆）是实现优先队列最高效的数据结构之一。它是一个完全二叉树，并满足堆序性质：在最小堆中，任意节点的值都小于或等于其子节点的值；在最大堆中则相反。Python的heapq模块提供了一系列基于最小堆的操作。

graph TD A["基础数据结构"] --> B["栈 Stack
LIFO"] A --> C["队列 Queue
FIFO"] B --> D["单调栈 Monotonic Stack
维护单调性"] C --> E["优先队列 Priority Queue
按优先级出队"] D --> F["典型应用：
下一个更大元素
最大矩形面积"] E --> G["实现方式：
堆（Heap）
Python heapq模块"] F --> H["解决一类特定
线性时间复杂度问题"] G --> I["解决需要动态
获取极值的场景"]

实战示例

示例一：单调栈求解“下一个更大元素 I”

这是LeetCode上的经典问题（496题）。给定两个没有重复元素的数组nums1和nums2，其中nums1是nums2的子集。需要找出nums1中每个元素在nums2中的下一个更大元素。如果不存在，则输出-1。

单调栈的解法思路：先遍历nums2，利用单调栈找出其中每个元素的下一个更大元素，并用哈希表记录。然后遍历nums1，直接从哈希表中取出结果。

def nextGreaterElement(nums1, nums2):
"""
使用单调栈解决“下一个更大元素 I”问题。
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
# 哈希表，用于存储nums2中每个元素的下一个更大元素
next_greater_map = {}
# 单调栈（栈底到栈顶保持递减），存储nums2中的元素
stack = []
# 遍历nums2，构建映射关系
for num in nums2:
# 当栈不为空，且当前元素num大于栈顶元素时
# 说明num是栈顶元素的下一个更大元素
while stack and num > stack[-1]:
# 弹出栈顶元素，并建立映射
smaller = stack.pop()
next_greater_map[smaller] = num
# 当前元素入栈
stack.append(num)
# 遍历结束后，栈中剩余的元素都没有下一个更大元素
while stack:
next_greater_map[stack.pop()] = -1
# 根据nums1中的元素，从映射表中获取结果
result = []
for num in nums1:
result.append(next_greater_map[num])
return result
# 测试代码
if __name__ == "__main__":
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(f"nums1: {nums1}")
print(f"nums2: {nums2}")
ans = nextGreaterElement(nums1, nums2)
print(f"下一个更大元素结果: {ans}")  # 输出: [-1, 3, -1]
# 解释：对于nums1中的4，在nums2中其右侧没有更大元素，返回-1。
# 对于1，下一个更大元素是3。对于2，下一个更大元素不存在，返回-1。

示例二：利用heapq实现优先队列

Python的heapq模块默认提供最小堆操作。以下示例演示如何使用它合并多个已排序的列表（LeetCode 23题“合并K个升序链表”的列表简化版）。

import heapq
def merge_k_sorted_lists(lists):
"""
使用优先队列（最小堆）合并K个已排序的列表。
:type lists: List[List[int]]
:rtype: List[int]
"""
# 初始化一个最小堆
min_heap = []
# 结果列表
merged_result = []
# 将每个非空列表的第一个元素及其列表索引、元素索引推入堆中
for list_idx, sorted_list in enumerate(lists):
if sorted_list:  # 确保列表不为空
# 堆中元素为三元组：(值, 列表索引, 元素在当前列表中的索引)
heapq.heappush(min_heap, (sorted_list[0], list_idx, 0))
# 当堆不为空时，持续取出当前最小的元素
while min_heap:
val, list_idx, element_idx = heapq.heappop(min_heap)
merged_result.append(val)
# 如果被取出的元素所在列表还有下一个元素，则将其推入堆中
next_element_idx = element_idx + 1
if next_element_idx < len(lists[list_idx]):
next_val = lists[list_idx][next_element_idx]
heapq.heappush(min_heap, (next_val, list_idx, next_element_idx))
return merged_result
# 测试代码
if __name__ == "__main__":
lists_to_merge = [
[1, 4, 5],
[1, 3, 4],
[2, 6]
]
print(f"待合并的列表: {lists_to_merge}")
result = merge_k_sorted_lists(lists_to_merge)
print(f"合并后的排序列表: {result}")  # 输出: [1, 1, 2, 3, 4, 4, 5, 6]

对比分析

数据结构 核心特性 优势 劣势 典型应用场景
栈 (Stack) LIFO（后进先出） 实现简单，操作高效（O(1)），天然支持回溯。 只能访问栈顶元素，功能受限。 函数调用栈、括号匹配、表达式求值、DFS、撤销操作。
队列 (Queue) FIFO（先进先出） 公平有序，保证处理顺序。 同样只能访问两端元素。 BFS、任务调度、消息队列、打印队列、缓存（FIFO策略）。
单调栈 (Monotonic Stack) 栈内元素保持单调性 将某些问题的复杂度从O(n²)优化到O(n)，思路巧妙。 应用场景相对特定，理解有门槛。 寻找下一个更大/更小元素、柱状图最大矩形、接雨水问题。
优先队列 (Priority Queue) 按优先级出队 能动态、高效地获取当前极值（最大或最小）。 实现比普通队列复杂，入队出队通常为O(log n)。 任务调度（如CPU调度）、合并K个有序序列、Dijkstra最短路径算法、获取数据流的中位数。
实现工具 (Python)
list (用作栈/队列) 灵活，内置 使用方便，append/pop即栈，但队列操作效率低。 pop(0)操作是O(n)，不适合高频队列操作。 快速原型、简单场景下的栈。
collections.deque 双端队列 两端插入删除都是O(1)，是实现队列和栈的优选。 需要额外导入模块。 高频的队列或栈操作，BFS。
heapq模块 最小堆实现 轻量级，内存效率高，提供优先队列核心操作。 只提供最小堆，如需最大堆需取负数；无法直接删除非堆顶元素。 需要优先队列的大多数场景，特别是内存敏感时。

最佳实践

  1. 根据场景选择底层实现：

    • 在Python中，使用list的append()和pop()来实现栈是高效且符合习惯的。
    • 如果需要实现队列，务必使用collections.deque，避免使用list的pop(0)，因为其时间复杂度为O(n)，在数据量大时性能极差。
    • 对于优先队列，heapq是标准库中的首选。如果需要更丰富的功能（如删除任意元素），可以考虑第三方库如sortedcontainers。

  2. 掌握单调栈的模板化思维：

    • 单调栈的代码结构往往非常固定。核心是while循环，在循环中判断新元素与栈顶元素的关系，并决定是否弹出栈顶。熟练掌握“寻找下一个更大元素”和“寻找下一个更小元素”这两种单调性（递减栈和递增栈）的模板，能解决一大类问题。
    • 在解决“柱状图最大矩形”（LeetCode 84）等问题时，通常需要在数组前后加入“哨兵”元素（如高度0），以简化边界条件处理，这是非常实用的技巧。

  3. 理解heapq的用法与限制：

    • heapq.heapify(list)可以将一个列表原地转换为堆，时间复杂度O(n)。
    • 堆中存储元组时，默认按元组第一个元素比较。利用这一特性，可以实现“带优先级的任务”或“自定义比较”。例如，在Dijkstra算法中，堆中存储(距离, 节点)。
    • 记住heapq默认是最小堆。要实现最大堆，一个通用技巧是将值取负数存入，取出时再取负恢复。
    • 堆不支持高效的“按值删除”操作。如果应用需要此功能，可以考虑使用“惰性删除”策略（标记删除，在弹出堆顶时检查）或选择其他数据结构。

小结

栈和队列作为基础数据结构，其LIFO和FIFO原则是算法设计的核心逻辑之一。单调栈是栈的升华，通过维护单调性，它能以线性时间解决一系列关于元素间顺序关系的难题，是面试和竞赛中的常客。优先队列则突破了FIFO的限制，通过堆实现，让我们能动态地获取当前最优解，在调度和优化问题中不可或缺。在Python中，灵活运用list、collections.deque和heapq模块，可以高效地实现这些数据结构，应对不同的算法挑战。理解它们的原理、差异和适用场景，是构建高效算法解决方案的关键一步。

下一节：堆与优先队列实战