参考API

数据结构的基本操作：遍历+访问（增删改查），包括线性和非线性两种形式。线性以for/while迭代为代表，非线性就是递归为代表。

栈

栈是后进先出（LIFO）：最后添加到栈中的元素最先被访问和删除。栈的操作只能在栈顶进行，不能直接访问或修改栈底的元素。应用：

  • 函数调用：栈常用于实现函数调用的调用栈。每次函数调用时，会将函数的执行上下文（如局部变量、返回地址等）压入栈中，并在函数返回时逐个弹出。
  • 表达式求值：栈可以用于表达式求值的计算过程。例如，中缀表达式转换为后缀表达式时，需要借助栈来存储运算符。
  • 括号匹配：栈可以用于检查括号是否匹配。当遇到左括号时，将其入栈；当遇到右括号时，检查栈顶元素是否为相应的左括号，如果匹配，则出栈，继续匹配下一个括号。

算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 单调栈：维护一个值为单调不递减（增）的栈
def nextGreaterElement(nums: List[int]) -> List[int]:
    n = len(nums)
    # 存放答案的数组
    res = [0 for _ in range(n)]
    stack = [] 
    # 倒着往栈里放
    for i in range(n - 1, -1, -1):
        # 判定个子高矮
        while stack and stack[-1] <= nums[i]:
            # 矮个起开，反正也被挡着了。。。
            stack.pop()
        # nums[i] 身后的更大元素
        res[i] = stack[-1] if s else -1
        stack.append(nums[i])

    # 正序遍历的
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            # 当当前元素大于栈顶元素时，将栈顶元素弹出并更新结果数组
            result[stack.pop()] = nums[i]
        stack.append(i)  # 将当前索引入栈
    
    return res

力扣指南

栈
题目 技巧 难度
✅316. 去除重复字母 单调栈 🌟🌟
✅341. 扁平化嵌套列表迭代器 dfs；栈 🌟🌟
✅496. 下一个更大元素 I 单调栈 🌟
✅739. 每日温度 单调栈 🌟🌟
✅503. 下一个更大元素 II 环形数组 拼接 🌟🌟
✅239. 滑动窗口最大值 优先队列；单调双端队列 🌟🌟🌟
✅225. 用队列实现栈 两个队列辅助 🌟
✅ 一个输入栈，一个输出栈 🌟
✅20. 有效的括号 🌟
✅921. 使括号有效的最少添加 🌟
✅1541. 平衡括号字符串的最少插入次数 🌟🌟

队列

队列（Queue）遵循先进先出（First-In-First-Out，FIFO）的原则。队列中的元素按照插入的顺序排列，最先插入的元素在队列的前端，最后插入的元素在队列的后端。应用：

  • 广度优先搜索（BFS）：队列常用于实现广度优先搜索算法中的待访问节点的队列。将初始节点入队，并在搜索过程中依次将相邻节点入队，以保证按照层次进行访问。
  • 缓冲区管理：队列常用于管理缓冲区，例如消息队列、任务队列等。新的消息或任务会被放入队列的末尾，然后按照顺序逐个处理。
  • 模拟事件驱动：队列可以用于模拟事件驱动的系统，将待处理的事件按照顺序放入队列中，然后逐个处理。

「单调队列」结构：既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值。「单调队列」这个数据结构主要用来辅助解决滑动窗口相关的问题。单调队列push方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉，最终单调队列中的元素大小就会保持一个单调递减的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 基本队列，可以指定最大容量（默认为无限）
queue.Queue(maxsize)
# 后进先出队列，类似于栈。
queue.LifoQueue(maxsize)
# 带有优先级的队列
queue.PriorityQueue(maxsize)

# 普通队列
import queue
q = queue.Queue()  # 初始化
size = q.qsize() # 队列长度
q.put(item)  # 添加元素
i = q.get()  # 取出左侧队头元素

# 双端队列
q = collections.deque() # 初始化
q.append(item)          # 队尾添加元素
q.appendleft(item)      # 队首添加元素
s = len(q)              # 队列的长度
item = q[index]         # 指定索引的元素
i = q.pop()             # 删除队尾元素
i = q.popleft()         # 删除队首元素
q.insert(index, item)   # 指定位置插入元素
q.remove(item)          # 删除指定元素
q.rotate(n)             # 将双端队列的元素向右旋转n步，n为负数表示向左旋转
q.extend(iterable)      # 将可迭代对象的元素从右端依次添加到双端队列
q.extendleft(iterable)  # 将可迭代对象的元素从左端依次添加到双端队列

堆

二叉堆（Binary Heap）二叉堆是一种完全二叉树，所以适合存储在数组中。

  • 主要操作：sink（下沉）和 swim（上浮），用以维护二叉堆的有序的性质
  • 主要应用：「堆排序」和数据结构「优先级队列」
    • 优先级队列维护堆顶元素为最值（Python为小顶堆），不满足标准队列先进先出的时间顺序。其主要操作是插入和删除。插入是先插到最后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位置。
1
2
3
4
5
6
7
8
import heapq
heap = [1, 2, 3]
heapq.heapify(heap)                 # 将列表转化为堆结构
heapq.heappush(heap, 4)             # 默认按照第一个元素升序排序，即小顶堆
top_element = heapq.heappop(heap)   # 移除并返回堆顶元素的值
top_element = heap[0]               # 获取堆顶元素的值
heapq.nlargest(n, nums)             # 取出nums数组的前n大的数字
heapq.nsmallest(n, nums)            # 取出nums数组的前n小的数字