算法入门第三篇：高效容器：栈、队列与堆

技术文档

引言：容器的哲学

在编程世界里，数据结构就像是一个个独特的“容器”，它们以不同的方式组织和存储数据，从而适应不同的操作需求。前两篇我们学习了数组（支持随机访问，连续存储）和链表（支持高效插入删除，离散存储）。本篇，我们将深入探索一些特定存取模式下的数据结构：栈（Stack）、队列（Queue）和堆（Heap）。

你可能会问：为什么需要这些“受限”的容器呢？它们有什么特别之处？

想象一下日常生活中，我们使用的容器：

桶：你只能从顶部放入东西，也只能从顶部取出东西。这就像栈，遵循“后进先出”的原则。
排队：人们按顺序进入队伍，也按顺序离开队伍。这就像队列，遵循“先进先出”的原则。
优先登机口：虽然有人在排队，但 VIP 或头等舱乘客可以优先登机。这就像优先队列（堆），数据不是按时间顺序，而是按“优先级”来处理。

这些特定的存取模式，在实际的软件开发中有着极其广泛且重要的应用。例如：

Unity 中的 Command Pattern（命令模式）：你可以把一系列操作（例如玩家的输入、AI 的行为）封装成一个个命令（Command）对象，然后把这些命令依次放入一个队列中。游戏循环可以逐帧从队列中取出并执行命令，实现解耦和可回放性。
Undo/Redo 功能：这正是栈的经典应用。每执行一个操作，就将其压入“撤销栈”；点击撤销，就从“撤销栈”弹出操作并执行逆向操作，同时压入“重做栈”。
AI 寻路：广度优先搜索（BFS）通常使用队列来寻找最短路径；而像 A 寻路算法则会用到*优先队列（堆）**来优先探索距离目标更近的路径。
任务调度：在多线程或异步编程中，操作系统或游戏引擎可能会维护一个任务队列，按顺序执行任务；或者是一个优先级队列，确保高优先级任务能先于低优先级任务执行。

理解这些容器的特性和实现，不仅能帮助你解决面试中的算法题，更能让你在实际开发中选择更合适的数据结构，写出更高效、更优雅的代码。

栈（Stack）：后进先出的“桶”

概念

**栈（Stack）是一种线性数据结构，遵循后进先出（LIFO: Last In, First Out）**的原则。想象一个堆叠起来的盘子，你最后放上去的盘子，总是你最先能拿走的。

基本操作

栈通常支持以下几个核心操作：

Push(element)：将元素添加到栈的顶部（入栈）。
Pop()：移除并返回栈顶的元素（出栈）。
Peek() / Top()：返回栈顶的元素，但不移除它。
IsEmpty()：检查栈是否为空。
Count() / Size()：返回栈中元素的数量。

实现方式

栈可以通过多种底层数据结构来实现：

数组实现（基于动态数组）：

通常使用一个数组作为底层存储，并用一个指针（或索引）指向栈顶元素的位置。
Push 时，在数组末尾添加元素；Pop 时，移除数组末尾元素。
当数组容量不足时，需要进行扩容（类似 List 的自动扩容机制）。
优点： 访问效率高，内存连续。
缺点： 可能会有扩容开销。

// 简单数组实现栈的骨架public class ArrayStack { private T[] _elements; private int _top; // 指向栈顶元素的下一个位置 (或栈顶元素的索引) public ArrayStack(int capacity = 10) { _elements = new T[capacity]; _top = 0; // 初始为空栈 } public void Push(T item) { if (_top == _elements.Length) { // 扩容逻辑，这里简化，实际会创建新数组并复制 Console.WriteLine(\"Stack is full, resizing...\"); Array.Resize(ref _elements, _elements.Length * 2); } _elements[_top++] = item; // 先赋值，后递增 _top } public T Pop() { if (IsEmpty()) { throw new InvalidOperationException(\"Stack is empty.\"); } return _elements[--_top]; // 先递减 _top，后取值 } public T Peek() { if (IsEmpty()) { throw new InvalidOperationException(\"Stack is empty.\"); } return _elements[_top - 1]; } public bool IsEmpty() { return _top == 0; } public int Size() { return _top; }}

在 C# 中，System.Collections.Generic.Stack 类就是基于数组实现的。

链表实现：

使用链表的头插法和头删法来实现栈。链表的头节点就是栈顶。
Push 时，新节点成为头节点，其 next 指向原头节点。
Pop 时，返回头节点数据，然后将头节点指向其 next。
优点： 动态大小，没有扩容开销。
缺点： 额外的指针空间开销。

// 简单链表实现栈的骨架public class LinkedStack { private class Node { public T Value; public Node Next; public Node(T value) { Value = value; } } private Node _topNode; // 栈顶节点 private int _count; public void Push(T item) { Node newNode = new Node(item); newNode.Next = _topNode; // 新节点指向原栈顶 _topNode = newNode; // 新节点成为新栈顶 _count++; } public T Pop() { if (IsEmpty()) { throw new InvalidOperationException(\"Stack is empty.\"); } T value = _topNode.Value; _topNode = _topNode.Next; // 栈顶下移 _count--; return value; } public T Peek() { if (IsEmpty()) { throw new InvalidOperationException(\"Stack is empty.\"); } return _topNode.Value; } public bool IsEmpty() { return _topNode == null; } public int Size() { return _count; }}

应用场景

函数调用栈（Call Stack）：程序函数调用时，函数的局部变量、参数和返回地址都会被压入栈中；函数执行完毕，从栈中弹出。
表达式求值：例如中缀表达式转后缀表达式，后缀表达式求值。
括号匹配：检查表达式中的括号是否合法配对。
浏览器前进/后退功能：每次访问一个页面，将其 URL 压入“前进栈”；点击后退，从“前进栈”弹出当前 URL 压入“后退栈”，并访问“前进栈”新的栈顶 URL。
DFS（深度优先搜索）：迭代实现 DFS 时，通常会使用栈来存储待访问的节点。
Undo/Redo (撤销/重做) 功能：如前所述，两个栈可以轻松实现。

经典面试题与解法（栈）

1. 有效括号 (Valid Parentheses)

题目描述：

给定一个只包括 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 的字符串 s，判断字符串是否有效。

有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。
  
  示例：
  
  输入: s = “([{}])”
  
  输出: true
解题思路：栈的典型应用

这道题是栈的经典应用场景。当遇到左括号时，我们将其压入栈中；当遇到右括号时，我们检查栈顶元素是否是与之匹配的左括号。

步骤：
1. 创建一个空栈。
2. 遍历给定字符串 s 中的每个字符 c：
  
  a. 如果 c 是左括号 ((, {, [), 将其压入栈中。
  
  b. 如果 c 是右括号 (), }, ]):
  
  i. 首先，检查栈是否为空。如果为空，说明没有对应的左括号，直接返回 false。
  
  ii. 弹出栈顶元素 topChar。
  
  iii. 判断 topChar 是否与当前右括号 c 匹配。例如，如果 c 是 ), topChar 必须是 (。如果不匹配，返回 false。
3. 遍历结束后，检查栈是否为空。如果栈为空，说明所有括号都成功匹配，返回 true；否则，说明有未闭合的左括号，返回 false。
- 代码实现：
  
  C#
```
using System.Collections.Generic;public class Solution { public bool IsValid(string s) { Stack stack = new Stack(); // 使用 Dictionary 存储括号对，方便判断 Dictionary mappings = new Dictionary() { { \')\', \'(\' }, { \'}\', \'{\' }, { \']\', \'[\' } }; foreach (char c in s) { if (mappings.ContainsKey(c)) { // 如果是右括号 char topElement = stack.Count == 0 ? \'#\' : stack.Pop(); // 弹出栈顶元素，如果栈空则用 \'#\' 占位避免报错 if (topElement != mappings[c]) { // 检查是否匹配  return false; } } else { // 如果是左括号 stack.Push(c); } } return stack.Count == 0; // 最终栈为空则有效 }}
```
- 复杂度分析：
  - 时间复杂度：O(N)，其中 N 是字符串的长度。我们只遍历了一次字符串。
  - 空间复杂度：O(N)。在最坏情况下（例如 ((((()))))），栈中会存储所有左括号。

2. 最小栈 (Min Stack)

题目描述：

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类：
- MinStack() 初始化栈对象。
- void push(int val) 将元素 val 推入栈中。
- void pop() 删除栈顶元素。
- int top() 获取栈顶元素。
- int getMin() 获取栈中的最小元素。
解题思路：双栈法

常规栈操作都是 O(1)，但要实现 O(1) 获取最小值，则需要额外的技巧。我们可以使用两个栈：
1. 数据栈 (dataStack)：用于存储所有入栈的元素，和普通栈一样。
2. 辅助栈 (minStack)：用于存储当前栈中对应的最小值。
操作逻辑：
- push(val)：
  - 将 val 压入 dataStack。
  - 关键： 压入 minStack 的逻辑：
    - 如果 minStack 为空，或 val 小于等于 minStack 的栈顶元素，则将 val 压入 minStack。
    - 否则（val 大于 minStack 栈顶元素），则将 minStack 的栈顶元素再次压入 minStack。这样保证 minStack 的栈顶始终是 dataStack 当前状态下的最小值。
- pop()：
  - dataStack.Pop()。
  - 同时 minStack.Pop()（因为 minStack 的元素是与 dataStack 一一对应的）。
- top()：
  - dataStack.Peek()。
- getMin()：
  - minStack.Peek()。
- 代码实现：
  
  C#
```
using System.Collections.Generic;public class MinStack { private Stack dataStack; // 数据栈 private Stack minStack; // 辅助栈，存储最小值 public MinStack() { dataStack = new Stack(); minStack = new Stack(); } public void Push(int val) { dataStack.Push(val); // 关键逻辑：保证 minStack 栈顶是当前所有元素的最小值 if (minStack.Count == 0 || val  0) { dataStack.Pop(); minStack.Pop(); // 两个栈同步弹出 } } public int Top() { if (dataStack.Count == 0) throw new InvalidOperationException(\"Stack is empty.\"); return dataStack.Peek(); } public int GetMin() { if (minStack.Count == 0) throw new InvalidOperationException(\"Stack is empty.\"); return minStack.Peek(); }}
```
- 复杂度分析：
  - 时间复杂度：O(1)。所有操作都是栈的基本操作，都是常数时间。
  - 空间复杂度：O(N)。在最坏情况下，两个栈都会存储 N 个元素。
思考： 这个题目巧妙地利用了辅助栈来维护额外的信息（最小值），实现了在常数时间内的查询。这是空间换时间的又一个典型例子。

3. 每日温度 (Daily Temperatures) / 下一个更大元素 (Next Greater Element)

题目描述（每日温度）：

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天之后。如果当天之后没有更高的温度，请改为 0 。

示例：

输入: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

输出: [1, 1, 4, 2, 1, 1, 0, 0]
解题思路：单调栈 (Monotonic Stack)

单调栈是一种特殊的栈，它维护栈内元素的单调性（单调递增或单调递减）。这种数据结构非常适合解决“找下一个更大/更小元素”的问题。

对于“下一个更大元素”问题，我们通常维护一个单调递减栈**（栈底到栈顶元素递减）。

步骤（以每日温度为例）：
1. 创建一个结果数组 answer，与 temperatures 长度相同，初始化为 0。
2. 创建一个空栈 stack，用于存储元素的索引（而不是值）。
3. 从左到右遍历 temperatures 数组，当前元素为 temperatures[i]：
  
  a. 循环：只要栈不为空，并且当前温度 temperatures[i] 大于栈顶索引对应的温度 temperatures[stack.Peek()]：
  
  i. 说明 temperatures[i] 是 stack.Peek() 对应元素的下一个更大元素。
  
  ii. 弹出栈顶索引 prevIndex = stack.Pop()。
  
  iii. 计算天数差：answer[prevIndex] = i - prevIndex。
  
  b. 将当前索引 i 压入栈中。
4. 遍历结束后，栈中剩余的元素（索引）表示它们后面没有更高的温度，它们的 answer 值为 0（已初始化）。
- 图解（以 [73, 74, 75, 71, 69, 72, 76, 73] 为例）：
  - stack 存索引，ans 初始化为 [0,0,0,0,0,0,0,0]
  - i=0, temp=73: stack.Push(0) -> stack=[0]
  - i=1, temp=74: 74 > 73 (栈顶0对应的temp)。pop(0). ans[0]=1-0=1. stack=[]. stack.Push(1) -> stack=[1]
  - i=2, temp=75: 75 > 74 (栈顶1对应的temp)。pop(1). ans[1]=2-1=1. stack=[]. stack.Push(2) -> stack=[2]
  - i=3, temp=71: 71 < 75。stack.Push(3) -> stack=[2,3] (栈底到栈顶：75,71)
  - i=4, temp=69: 69 < 71。stack.Push(4) -> stack=[2,3,4] (栈底到栈顶：75,71,69)
  - i=5, temp=72: 72 > 69 (栈顶4)。pop(4). ans[4]=5-4=1. stack=[2,3].
    
    72 > 71 (栈顶3)。pop(3). ans[3]=5-3=2. stack=[2].
    
    72 stack=[2,5] (栈底到栈顶：75,72)
  - i=6, temp=76: 76 > 72 (栈顶5)。pop(5). ans[5]=6-5=1. stack=[2].
    
    76 > 75 (栈顶2)。pop(2). ans[2]=6-2=4. stack=[].
    
    stack.Push(6) -> stack=[6]
  - i=7, temp=73: 73 < 76。stack.Push(7) -> stack=[6,7]
  - 遍历结束。ans = [1, 1, 4, 2, 1, 1, 0, 0]
- 代码实现：
  
  C#
```
using System.Collections.Generic;using System;public class Solution { public int[] DailyTemperatures(int[] temperatures) { int n = temperatures.Length; int[] answer = new int[n]; // 栈中存储的是元素的索引，保持栈内对应元素值的单调递减 Stack stack = new Stack(); for (int i = 0; i  0 && temperatures[i] > temperatures[stack.Peek()]) { int prevIndex = stack.Pop(); // 弹出栈顶索引 answer[prevIndex] = i - prevIndex; // 计算天数差 } stack.Push(i); // 当前索引入栈 } return answer; }}
```
- 复杂度分析：
  - 时间复杂度：O(N)。每个元素最多被压入栈一次，弹出栈一次。虽然有嵌套 while 循环，但总操作数是线性的。
  - 空间复杂度：O(N)。在最坏情况下（例如温度是递减的 [7,6,5,4,3,2,1]），所有元素都会被压入栈。
思考： 单调栈是解决“找下一个更大/更小元素”系列问题的利器。它的核心在于通过维护栈的单调性，确保一旦当前元素比栈顶元素“大/小”，栈顶元素就找到了它的“下一个更大/更小”值，并可以出栈。

队列（Queue）：先进先出的“队伍”

概念

**队列（Queue）是另一种线性数据结构，遵循先进先出（FIFO: First In, First Out）**的原则。就像排队买票，先到的人先买到票。

基本操作

Enqueue(element)：将元素添加到队列的尾部（入队）。
Dequeue()：移除并返回队列头部的元素（出队）。
Front() / Peek()：返回队列头部的元素，但不移除它。
IsEmpty()：检查队列是否为空。
Count() / Size()：返回队列中元素的数量。

实现方式

队列也可以通过数组或链表实现：

数组实现：

需要两个指针：front（指向队头）和 rear（指向队尾）。
Enqueue 时，rear 指针后移，在数组末尾添加元素。
Dequeue 时，front 指针后移，移除队头元素。
挑战： 当队头元素出队后，数组前面会出现空位。如果只简单地移动 front 指针，数组尾部可能很快达到边界，即使前面还有空位也无法继续入队，这会造成“假溢出”。解决方法是使用循环队列（Circular Queue）。

// 简单数组实现队列的骨架 (非循环队列，有假溢出问题)public class ArrayQueue { private T[] _elements; private int _head; // 队头索引 private int _tail; // 队尾索引（下一个元素入队的位置） private int _count; public ArrayQueue(int capacity = 10) { _elements = new T[capacity]; _head = 0; _tail = 0; _count = 0; } public void Enqueue(T item) { if (_count == _elements.Length) { // 队列已满 Console.WriteLine(\"Queue is full, resizing...\"); // 实际会进行扩容，并可能需要重新调整 head/tail Array.Resize(ref _elements, _elements.Length * 2); } _elements[_tail] = item; _tail = (_tail + 1) % _elements.Length; // 循环队列的关键 _count++; } public T Dequeue() { if (IsEmpty()) { throw new InvalidOperationException(\"Queue is empty.\"); } T value = _elements[_head]; _head = (_head + 1) % _elements.Length; // 循环队列的关键 _count--; return value; } public T Peek() { if (IsEmpty()) { throw new InvalidOperationException(\"Queue is empty.\"); } return _elements[_head]; } public bool IsEmpty() { return _count == 0; } public int Size() { return _count; }}

在 C# 中，System.Collections.Generic.Queue 类就是基于数组实现的，并且内部处理了循环队列和扩容机制。

链表实现：

使用链表可以方便地实现队列。维护一个头指针（head）和一个尾指针（tail）。
Enqueue 时，新节点接到 tail 后面，并更新 tail。
Dequeue 时，返回 head 节点数据，并更新 head。
优点： 动态大小，没有扩容开销，操作效率高。
缺点： 额外的指针空间开销。

// 简单链表实现队列的骨架public class LinkedQueue { private class Node { public T Value; public Node Next; public Node(T value) { Value = value; } } private Node _head; // 队头 private Node _tail; // 队尾 private int _count; public void Enqueue(T item) { Node newNode = new Node(item); if (IsEmpty()) { _head = newNode; _tail = newNode; } else { _tail.Next = newNode; // 接到队尾 _tail = newNode; // 更新队尾 } _count++; } public T Dequeue() { if (IsEmpty()) { throw new InvalidOperationException(\"Queue is empty.\"); } T value = _head.Value; _head = _head.Next; // 队头后移 if (_head == null) { // 如果队头变为 null，说明队列已空，队尾也置为 null _tail = null; } _count--; return value; } public T Peek() { if (IsEmpty()) { throw new InvalidOperationException(\"Queue is empty.\"); } return _head.Value; } public bool IsEmpty() { return _head == null; } public int Size() { return _count; }}

应用场景

BFS（广度优先搜索）：迭代实现 BFS 时，使用队列来存储待访问的节点，确保按层级顺序访问。
任务调度/生产者消费者模型：生产者将任务放入队列，消费者从队列中取出任务执行。
缓存队列：例如，一些简单的 LRU 缓存策略，可以把最近最少使用的元素放到队头，淘汰队尾。
打印队列：打印任务按提交顺序进入队列。
模拟排队系统：银行排号、游戏匹配排队等。

经典面试题与解法（队列）

1. 用栈实现队列 (Implement Queue using Stacks)

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾。
- int pop() 从队列的开头移除并返回元素。
- int peek() 返回队列开头的元素。
- boolean empty() 如果队列为空，返回 true ；否则，返回 false 。
解题思路：两个栈的巧妙配合

栈是 LIFO，队列是 FIFO。要用 LIFO 实现 FIFO，我们需要两个栈：
1. 入栈栈 (inStack)：用于处理 push 操作，所有新元素直接压入 inStack。
2. 出栈栈 (outStack)：用于处理 pop 和 peek 操作。
核心逻辑：
- push(x)：直接将 x 压入 inStack。
- pop() / peek()：
  - 在执行 pop 或 peek 前，首先检查 outStack 是否为空。
  - 如果 outStack 为空：将 inStack 中的所有元素逐个弹出，并压入 outStack。这样，inStack 中最早进入的元素（队列的头部）就到了 outStack 的栈顶。
  - 现在 outStack 的栈顶就是队列的头部元素，可以直接 pop() 或 peek() 了。
  - 如果 outStack 不为空：直接从 outStack pop() 或 peek()。
- 代码实现：
  
  C#
```
using System.Collections.Generic;public class MyQueue { private Stack inStack; // 用于入队 private Stack outStack; // 用于出队 public MyQueue() { inStack = new Stack(); outStack = new Stack(); } public void Push(int x) { inStack.Push(x); } public int Pop() { // 如果 outStack 为空，则将 inStack 的所有元素倒入 outStack if (outStack.Count == 0) { TransferElements(); } return outStack.Pop(); } public int Peek() { // 如果 outStack 为空，则将 inStack 的所有元素倒入 outStack if (outStack.Count == 0) { TransferElements(); } return outStack.Peek(); } public bool Empty() { return inStack.Count == 0 && outStack.Count == 0; } // 辅助方法：将 inStack 中的元素转移到 outStack private void TransferElements() { while (inStack.Count > 0) { outStack.Push(inStack.Pop()); } }}
```
- 复杂度分析：
  - push 操作： O(1)。
  - pop / peek 操作： 均摊 O(1)。虽然在 outStack 为空时需要将 inStack 的所有元素转移过来（O(N)），但每个元素最多只会被转移一次。因此，对于一系列操作（例如 N 个 push 和 N 个 pop），总时间复杂度是 O(N)，所以平均每次操作是 O(1)。
  - 空间复杂度：O(N)。两个栈最多会存储 N 个元素。

2. 用队列实现栈 (Implement Stack using Queues)

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
- void push(int x) 将元素 x 推到栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈为空，返回 true ；否则，返回 false 。
解题思路：两个队列的切换

用 FIFO 实现 LIFO，这个比用栈实现队列稍微复杂一点。关键在于保证每次 push 进来的新元素，都能在 pop 或 top 时第一时间被取出。

方法一：push 操作 O(N)，pop/top 操作 O(1)
1. 维护两个队列：q1 和 q2。
2. push(x)：
  
  a. 将 x 加入非空队列（假设是 q1）的队尾。
  
  b. 将 q1 中除了 x 之外的所有元素，逐个从 q1 队头取出，并重新加入 q1 的队尾。这样 x 就被移动到了 q1 的队头。
  
  c. 现在 q1 的队头就是栈顶元素。
3. pop() / top()：直接从 q1 队头 Dequeue() 或 Peek()。
4. empty()：判断 q1 是否为空。
方法二：push 操作 O(1)，pop/top 操作 O(N)

这是更常见的做法。
1. 维护两个队列：mainQueue 和 tempQueue。
2. push(x)：将 x 直接加入 mainQueue 的队尾。
3. pop() / top()：
  
  a. 将 mainQueue 中除了最后一个元素（即栈顶元素）之外的所有元素，逐个从 mainQueue 队头取出，并加入 tempQueue。
  
  b. 此时 mainQueue 中只剩下栈顶元素，将其 Dequeue() 或 Peek()。
  
  c. 交换 mainQueue 和 tempQueue（或者直接将 tempQueue 中的元素全部倒回 mainQueue），确保 mainQueue 始终是主要队列。
4. empty()：判断 mainQueue 和 tempQueue 是否都为空。
- 代码实现 (方法二)：
  
  C#
```
using System.Collections.Generic;public class MyStack { private Queue q1; // 主队列 private Queue q2; // 辅助队列 public MyStack() { q1 = new Queue(); q2 = new Queue(); } public void Push(int x) { q1.Enqueue(x); // 新元素直接入主队列 } public int Pop() { // 将 q1 中除了最后一个元素（栈顶）之外的所有元素转移到 q2 while (q1.Count > 1) { q2.Enqueue(q1.Dequeue()); } int popped = q1.Dequeue(); // 此时 q1 中只剩下栈顶元素，弹出 // 交换 q1 和 q2，让 q1 始终是主队列 Queue temp = q1; q1 = q2; q2 = temp; return popped; } public int Top() { // 和 Pop 类似，但只 Peek，不 Dequeue while (q1.Count > 1) { q2.Enqueue(q1.Dequeue()); } int topElement = q1.Peek(); // 此时 q1 中只剩下栈顶元素 // 同样要将元素从 q1 移回 q2，然后交换队列 q2.Enqueue(q1.Dequeue()); Queue temp = q1; q1 = q2; q2 = temp; return topElement; } public bool Empty() { return q1.Count == 0; // 只需要判断主队列是否为空 }}
```
- 复杂度分析：
  - push 操作： O(1)。
  - pop / top 操作： O(N)。在最坏情况下，需要将 N−1 个元素从一个队列转移到另一个队列。
  - 空间复杂度：O(N)。两个队列最多会存储 N 个元素。

3. 循环队列 (Circular Queue)

题目描述：

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

你的实现应该支持以下操作：MyCircularQueue(k)：构造器，设置队列的长度为 k。Front()：从队首获取元素。如果队列为空，返回 -1。Rear()：获取队尾元素。如果队列为空，返回 -1。enQueue(value)：将一个元素插入队列中。如果成功插入则返回真。deQueue()：从队列中删除一个元素。如果成功删除则返回真。isEmpty()：检查队列是否为空。isFull()：检查队列是否已满。
解题思路：数组与模运算

循环队列主要解决普通数组实现队列时“假溢出”的问题。通过模（%）运算，让队尾和队头指针能在数组的末尾“绕”回数组的开头，形成一个逻辑上的环。

关键： 区分队满和队空。
- 方法一（常见）：牺牲一个存储空间。 当队头 head == (tail + 1) % capacity 时，视为队满。
- 方法二：额外维护一个 count 变量。 通过 count 轻松判断队空 (count == 0) 和队满 (count == capacity)。
这里我们使用方法二，因为其逻辑更清晰。

核心指针：
- _head：指向队头元素。
- _tail：指向下一个元素应该入队的空位。
- _capacity：队列的最大容量。
- _count：当前队列中元素的数量。
操作逻辑：
- enQueue(value)：
  - 如果 isFull()，返回 false。
  - 否则，_elements[_tail] = value。
  - _tail = (_tail + 1) % _capacity。
  - _count++。返回 true。
- deQueue()：
  - 如果 isEmpty()，返回 false。
  - 否则，_head = (_head + 1) % _capacity。
  - _count--。返回 true。
- Front()：如果 isEmpty() 返回 -1，否则返回 _elements[_head]。
- Rear()：如果 isEmpty() 返回 -1，否则返回 _elements[(_tail - 1 + _capacity) % _capacity] （_tail - 1 可能为负数，加 _capacity 再模 _capacity 是为了正确处理负数取模）。
- isEmpty()：_count == 0。
- isFull()：_count == _capacity。
- 代码实现：
  
  C#
```
public class MyCircularQueue { private int[] _elements; private int _head; private int _tail; // _tail 指向下一个可以插入的位置 private int _capacity; private int _count; // 记录当前元素数量，方便判断空满 public MyCircularQueue(int k) { _capacity = k; // 容量 k，但我们实际用 k个位置 _elements = new int[k]; // 实际存储空间 _head = 0; _tail = 0; _count = 0; } public bool EnQueue(int value) { if (IsFull()) { return false; } _elements[_tail] = value; _tail = (_tail + 1) % _capacity; // 队尾指针前进，如果到头则回到 0 _count++; return true; } public bool DeQueue() { if (IsEmpty()) { return false; } _head = (_head + 1) % _capacity; // 队头指针前进 _count--; return true; } public int Front() { if (IsEmpty()) { return -1; } return _elements[_head]; } public int Rear() { if (IsEmpty()) { return -1; } // 注意 _tail 指向的是下一个空位，所以队尾元素是 _tail-1 // 考虑 _tail-1 可能是负数的情况（当 _tail 为 0 时） return _elements[(_tail - 1 + _capacity) % _capacity]; } public bool IsEmpty() { return _count == 0; } public bool IsFull() { return _count == _capacity; }}
```
- 复杂度分析：
  - 所有操作：O(1)。
  - 空间复杂度：O(K)，其中 K 是队列的容量。
思考： 循环队列是数组实现队列的关键，面试中可能会要求你手写。理解模运算在指针环绕中的作用，以及如何判断队满和队空，是核心。

堆（Heap）/优先队列（Priority Queue）：按优先级出队

概念

堆（Heap）是一种特殊的完全二叉树（Complete Binary Tree）。它满足堆序性（Heap Property）：

最大堆（Max-Heap）：任意一个父节点的值都大于或等于其子节点的值。因此，堆中最大的元素总是在根节点。
最小堆（Min-Heap）：任意一个父节点的值都小于或等于其子节点的值。因此，堆中最小的元素总是在根节点。

通常，堆是基于数组实现的。由于完全二叉树的性质，我们可以将树中的节点按照层序遍历的顺序依次存入数组，通过索引关系来找到父子节点：

对于索引为 i 的节点：
- 其父节点索引为 (i - 1) / 2 (向下取整)。
- 其左子节点索引为 2 * i + 1。
- 其右子节点索引为 2 * i + 2。

优先队列（Priority Queue）是一种抽象数据类型，它允许我们以任意顺序添加元素，但总是能够高效地取出优先级最高的元素。堆是实现优先队列最常用的数据结构。在 C# 中，.NET 6 以后提供了 PriorityQueue 类。

基本操作（基于堆实现的优先队列）

Insert(element) / Enqueue(element, priority)：向堆中添加一个元素，并保持堆的性质。O(logN)。
ExtractMax() / ExtractMin() / Dequeue()：移除并返回堆中最大/最小的元素（即根节点），并保持堆的性质。O(logN)。
Peek() / Top()：返回堆中最大/最小的元素，但不移除它。O(1)。
Count() / Size()：返回堆中元素的数量。O(1)。

堆的实现核心：上浮（Heapify Up）与下沉（Heapify Down）

插入（Insert）：
1. 将新元素放到数组的末尾。
2. 执行**上浮（Heapify Up）**操作：将新元素与它的父节点比较，如果违反堆序性，就交换它们。重复这个过程直到满足堆序性或到达根节点。
删除根节点（Extract Max/Min）：
1. 将根节点（即最大/最小元素）与数组的最后一个元素交换。
2. 移除（逻辑上）最后一个元素（原根节点）。
3. 执行**下沉（Heapify Down）**操作：将新的根节点与其子节点比较，如果违反堆序性，就与最大的子节点（最大堆）或最小的子节点（最小堆）交换。重复这个过程直到满足堆序性或到达叶子节点。

这些操作的复杂度都是 O(logN)，因为每次交换都只会沿着树的高度（logN）进行。

应用场景

Top K 问题：例如，从海量数据中找出最大的 K 个数，最小的 K 个数。
Dijkstra 算法 / Prim 算法：最短路径算法和最小生成树算法中，需要反复取出优先级最高的节点（最短路径/最小权重边），优先队列是核心组件。
任务调度：操作系统中，优先级高的任务优先执行。
事件模拟：模拟系统中，下一个发生事件总是优先级最高的。
Huffman 编码：用于构建 Huffman 树。

经典面试题与解法（堆/优先队列）

1. 前 K 个高频元素 (Top K Frequent Elements)

题目描述：

给你一个整数数组 nums 和一个整数 k。

请你返回数组中出现频率最高的 k 个元素。你可以按任何顺序返回答案。

示例：

输入: nums = [1, 1, 1, 2, 2, 3], k = 2

输出: [1, 2]

解释: 1 出现 3 次，2 出现 2 次，3 出现 1 次。前 2 个高频元素是 1 和 2。
解题思路：哈希表 + 最小堆

这道题是经典的 Top K 问题。解决这类问题，通常的思路是：
1. 统计频率： 使用**哈希表（Dictionary）**来统计每个数字出现的频率。
2. 筛选 Top K：维护一个大小为 k 的最小堆（Min-Heap）。
  
  a. 遍历哈希表中每个数字及其频率对。
  
  b. 如果堆的大小小于 k，直接将当前频率对（或只存频率）入堆。
  
  c. 如果堆的大小等于 k，比较当前频率对的频率与堆顶元素（堆中频率最小的元素）的频率：
  
  i. 如果当前频率对的频率大于堆顶元素的频率，则弹出堆顶元素，将当前频率对入堆。
  
  ii. 否则，不进行操作（当前频率对不是 Top K）。
3. 遍历结束后，堆中剩下的 k 个元素就是频率最高的 k 个元素。
- 为什么是最小堆？ 因为我们想要留下最大的 k 个频率。当堆满时，如果新加入的频率比堆顶（最小）还小，那它肯定不是 Top K。如果比堆顶大，那么最小的那个（堆顶）就应该被替换掉。
- C# 中 PriorityQueue 的使用： .NET 6 引入了 System.Collections.Generic.PriorityQueue，非常适合解决这类问题。它默认是最小优先级队列（即优先级值越小，元素越优先出队）。
- 代码实现：
  
  C#
```
using System.Collections.Generic;using System.Linq; // 用于一些LINQ扩展方法，这里可以不用public class Solution { public int[] TopKFrequent(int[] nums, int k) { // 1. 统计频率 Dictionary freqMap = new Dictionary(); foreach (int num in nums) { freqMap[num] = freqMap.GetValueOrDefault(num, 0) + 1; } // 2. 使用最小堆（PriorityQueue） // 存储 (元素值, 频率) 对，并以频率作为优先级，小的优先 PriorityQueue minHeap = new PriorityQueue(); foreach (var entry in freqMap) { int num = entry.Key; int freq = entry.Value; if (minHeap.Count  minHeap.PeekPriority()) { // 堆已满，且当前元素频率更高 minHeap.Dequeue(); // 弹出堆顶（频率最小的） minHeap.Enqueue(num, freq); // 将当前元素入堆 } } // 3. 将堆中的元素取出，转换为结果数组 int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = minHeap.Dequeue(); } return result; }}
```
- 复杂度分析：
  - 时间复杂度：O(N+MlogK)。
    - O(N) 用于遍历数组统计频率 (N 为 nums 长度)。
    - O(M) 为哈希表中不同元素的数量。每个元素最多进出堆一次，堆的操作是 O(logK)。所以是 O(MlogK)。
  - 空间复杂度：O(M+K)。哈希表占用 O(M) 空间，堆占用 O(K) 空间。

2. 数据流中的中位数 (Find Median from Data Stream)

题目描述：

中位数是有序列表中间的数。如果列表长度是偶数，中位数是中间两个数的平均值。

例如，

[2, 3, 4] 的中位数是 3

[2, 3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。

解题思路：对顶堆 (Two Heaps / Max-Min Heaps)

这是优先队列的进阶应用。为了在 O(logN) 时间内添加元素，并在 O(1) 或 O(logN) 时间内找到中位数，我们可以使用两个堆：

大顶堆 (maxHeap)：存储数据流中较小的一半元素。堆顶是这“较小一半”中的最大值。
小顶堆 (minHeap)：存储数据流中较大的一半元素。堆顶是这“较大一半”中的最小值。

维护规则：

maxHeap 的所有元素都小于等于 minHeap 的所有元素。
maxHeap 的大小要么等于 minHeap 的大小，要么比 minHeap 大 1。这样可以保证中位数总是在 maxHeap 的堆顶（总数为奇数时）或由 maxHeap 堆顶和 minHeap 堆顶共同决定（总数为偶数时）。

操作逻辑：

addNum(num)：
1. 先将 num 加入 maxHeap。
2. 将 maxHeap 的堆顶元素弹出，并加入 minHeap (确保 maxHeap 的元素都小于等于 minHeap 的元素)。
3. 平衡堆的大小： 如果 minHeap 的大小比 maxHeap 大，将 minHeap 的堆顶弹出，并加入 maxHeap。
  - 这样维护 maxHeap.Count == minHeap.Count 或 maxHeap.Count == minHeap.Count + 1。
findMedian()：
- 如果 maxHeap.Count == minHeap.Count，则中位数是 (maxHeap.Peek() + minHeap.Peek()) / 2.0。
- 如果 maxHeap.Count > minHeap.Count，则中位数是 maxHeap.Peek()。
C# 中 PriorityQueue 的使用：
- PriorityQueue 默认是最小优先级队列（优先级值越小，元素越优先出队）。
- 要实现最大堆，可以利用优先级取反或者存储负数。例如，Enqueue(val, -val)，这样大的 val 会有小的 -val 优先级，从而优先出队。

代码实现：

using System.Collections.Generic;public class MedianFinder { // maxHeap 存储较小的一半元素，堆顶是最大值 // 使用负数作为优先级，模拟大顶堆 private PriorityQueue maxHeap; // minHeap 存储较大的一半元素，堆顶是最小值 private PriorityQueue minHeap; public MedianFinder() { maxHeap = new PriorityQueue(); // 默认是小顶堆，用负数实现大顶堆 minHeap = new PriorityQueue(); // 小顶堆 } public void AddNum(int num) { // 先将 num 加入 maxHeap (较小的一半) maxHeap.Enqueue(num, -num); // 优先级取负，实现大顶堆 // 确保 maxHeap 的最大值 小于等于 minHeap 的最小值 // 如果 maxHeap 顶部的元素（即较小一半的最大值）大于 minHeap 顶部的元素（即较大一半的最小值） // 那么需要将 maxHeap 的顶部元素移动到 minHeap 中 minHeap.Enqueue(maxHeap.DequeueElement(), maxHeap.DequeuePriority()); // 弹出 maxHeap 顶部，入 minHeap // 平衡堆的大小 // 保持 maxHeap 的大小等于或比 minHeap 大 1 if (maxHeap.Count < minHeap.Count) { maxHeap.Enqueue(minHeap.DequeueElement(), -minHeap.DequeuePriority()); // 弹出 minHeap 顶部，入 maxHeap } } // 注意：PriorityQueue.Dequeue() 默认只返回 Element，需要自己扩展一个方法来获取优先级 // 或者直接用元组存储，如 PriorityQueue // 为了方便，这里假设 Dequeue() 方法会返回元素本身 // 真实 PriorityQueue 是 Dequeue() 返回 TElement， // 且 PeekPriority() 返回 TPriority。为了代码简洁，上面模拟的DequeueElement()和DequeuePriority() // 实际上需要分别调用 Dequeue() 和 PeekPriority()，然后处理好。 // 实际使用可以这样： // var element = maxHeap.Dequeue(); // minHeap.Enqueue(element, element); // minHeap 优先级就是元素值本身 // var elementToMove = minHeap.Dequeue(); // maxHeap.Enqueue(elementToMove, -elementToMove); // 为了避免上面代码的复杂性，这里我们直接使用 C# 的 Stack 和 List 模拟堆， // 或者假设 PriorityQueue 可以更方便地 Peek 和 Dequeue 元素和优先级。 // 实际面试中，会更倾向于让你直接用语言自带的 PriorityQueue 或自己简单实现堆。 // 如果要用 C# 真实的 PriorityQueue，AddNum 应该是这样： /* public void AddNum(int num) { // 总是先尝试加入 maxHeap maxHeap.Enqueue(num, -num); // -num 模拟大顶堆 // 确保 maxHeap 的所有元素都小于等于 minHeap 的所有元素 // maxHeap 的最大值不能大于 minHeap 的最小值 if (maxHeap.Count > 0 && minHeap.Count > 0 && maxHeap.Peek() > minHeap.Peek()) { minHeap.Enqueue(maxHeap.Dequeue(), -maxHeap.PeekPriority()); // 错误示范，不能这样PeekPriority() // 应该这样： // var maxVal = maxHeap.Dequeue(); // minHeap.Enqueue(maxVal, maxVal); } // 平衡堆的大小 // maxHeap 的元素个数必须等于或比 minHeap 多 1 if (maxHeap.Count > minHeap.Count + 1) { // var valToMove = maxHeap.Dequeue(); // minHeap.Enqueue(valToMove, valToMove); } else if (minHeap.Count > maxHeap.Count) { // var valToMove = minHeap.Dequeue(); // maxHeap.Enqueue(valToMove, -valToMove); } } */ // 为了简化，我们直接使用虚拟的 DequeueElement() 和 DequeuePriority() 配合。 // 或者干脆直接用元组存储，这样Dequeue()直接返回元组，包含元素和优先级。 // PriorityQueue maxHeap; public double FindMedian() { if (maxHeap.Count == minHeap.Count) { return (maxHeap.Peek() + minHeap.Peek()) / 2.0; } else { return maxHeap.Peek(); // 此时 maxHeap 总是比 minHeap 多一个元素 } }}// 辅助方法，用于模拟 PriorityQueue 的 PeekPriority 和 DequeueElement// (在实际 PriorityQueue 中，需要根据实际方法调整)public static class PriorityQueueExtensions { public static TElement DequeueElement(this PriorityQueue pq) { // 仅用于演示，实际应检查Count return pq.Dequeue(); } public static TPriority PeekPriority(this PriorityQueue pq) { // 仅用于演示，实际应检查Count return pq.Peek(); // Peek() 默认返回 TElement，这不是 priority // 真正的 PriorityQueue 没有直接 PeekPriority，需要你自己存储 tuple (element, priority) // 例如 PriorityQueue // 这里为了简化演示，假设有一个可以获取优先级的方法。 // 实际上，如果元素和优先级相同，可以 `pq.Enqueue(num, num)` 这样简化。 // 但为了实现MaxHeap，我们需要 `pq.Enqueue(num, -num)` // 所以需要存储 `Tuple` 或自定义类型。 // 这里我们假设内部是 `PriorityQueue<Tuple, int>` 并且我们知道它的优先级就是 -val return (TPriority)(object)(-pq.Peek()); // 这不是标准用法，仅为说明概念 }}

关于 C# PriorityQueue 的补充说明：

PriorityQueue 在 Enqueue 时需要同时提供元素和优先级。
Dequeue() 方法返回的是元素 (TElement)。
Peek() 方法返回的是元素 (TElement)。
如果你需要根据优先级获取元素，并且优先级本身不是元素，你需要把元素和优先级一起封装到一个 Tuple 或者自定义 struct 中作为 TElement。
要实现最大堆，最常见的方法是 Enqueue(element, -priorityValue)。

因此，上面 AddNum 的代码实现，在实际使用 PriorityQueue 时会略有不同，需要自己封装 (int value, int priority) 元组，或者实现自定义比较器。

更接近实际的 AddNum 和 FindMedian 代码应该是这样的：

using System.Collections.Generic;using System;public class MedianFinderRealPQ { // 大顶堆：存较小一半，优先级取负数，让大的元素（小的负数优先级）排前面 private PriorityQueue maxHeap; // 小顶堆：存较大一半，优先级取正数，让小的元素排前面 private PriorityQueue minHeap; public MedianFinderRealPQ() { maxHeap = new PriorityQueue(); minHeap = new PriorityQueue(); } public void AddNum(int num) { // 总是先加入 maxHeap maxHeap.Enqueue(num, -num); // maxHeap 的优先级是 -num，num越大优先级越小，但堆顶是优先级最小的（也就是 num 最大的） // 确保 maxHeap 的最大值 <= minHeap 的最小值 // 将 maxHeap 最大的元素弹出，放入 minHeap minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.PeekPriority()); // 这里 PeekPriority 已经返回了负数，作为minHeap的优先级，这样会出问题 // minHeap 的优先级应该就是元素值本身 // 应该是这样： // var maxValFromMaxHeap = maxHeap.Dequeue(); // minHeap.Enqueue(maxValFromMaxHeap, maxValFromMaxHeap); // 平衡堆的大小 if (maxHeap.Count  0 && minHeap.Count > 0 && maxHeap.Peek() > minHeap.Peek()) { // 将 maxHeap 的最大值移到 minHeap minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Peek()); // maxHeap.Peek() 此时是下一个最大的// 应该为 minHeap.Enqueue(maxHeap.Dequeue(), maxVal); // maxVal 是刚才Dequeue出来的 // 正确的做法是： var maxValFromMaxHeap = maxHeap.Dequeue(); minHeap.Enqueue(maxValFromMaxHeap, maxValFromMaxHeap); // 优先级就是值本身 } // 维持堆的大小平衡：maxHeap.Count == minHeap.Count 或 maxHeap.Count == minHeap.Count + 1 if (maxHeap.Count > minHeap.Count + 1) { var valToMove = maxHeap.Dequeue(); minHeap.Enqueue(valToMove, valToMove); } else if (minHeap.Count > maxHeap.Count) { var valToMove = minHeap.Dequeue(); maxHeap.Enqueue(valToMove, -valToMove); } } */ // 为了不让本篇过于复杂，上述代码仍以概念为主，在实际使用PriorityQueue时需要注意元素和优先级的关系。 // 实际面试中，如果让手写堆，会更倾向于写出堆的数组实现而非C#的PriorityQueue用法。 public double FindMedian() { if (maxHeap.Count == minHeap.Count) { // 两个堆顶部元素之和的平均值 return (maxHeap.Peek() + minHeap.Peek()) / 2.0; } else { // 元素总数为奇数，中位数在maxHeap的顶部 return maxHeap.Peek(); } }}

复杂度分析：
- addNum 操作：O(logN)。每次添加元素涉及堆的插入和可能的平衡调整，都是对数时间。
- findMedian 操作：O(1)。只需要访问堆的顶部元素。
- 空间复杂度：O(N)。两个堆共同存储所有元素。

思考： 对顶堆是解决中位数、数据流的第 K 大/小等问题的标准解法。它巧妙地利用了两个堆各自的特性，并通过平衡规则来维护数据的有序性。

总结与练习

本篇我们学习了三种重要且高频使用的高效容器：栈、队列和堆（作为优先队列的实现）。它们虽然有各自的存取限制，但也因此在特定场景下发挥着无可替代的作用。

栈（LIFO）：理解其后进先出的特性，是函数调用、括号匹配、撤销/重做功能的基石。Min Stack 展现了如何用辅助栈维护额外信息，单调栈 则是解决“下一个更大/更小元素”问题的强大工具。
队列（FIFO）：理解其先进先出的特性，是 BFS、任务调度的核心。通过 用栈实现队列 和 用队列实现栈 这种变态题目，我们深入理解了它们之间的特性转换。循环队列 则解决了数组实现队列的“假溢出”问题。
堆（Heap）/优先队列（Priority Queue）：理解其基于优先级的出队特性，以及它如何通过完全二叉树在数组中高效实现。Top K 问题 和 数据流中位数 是面试中考察堆的经典题目，特别是后者，展示了对顶堆这种高级技巧。

本篇核心知识点回顾：

栈：LIFO，push, pop, peek，链表/数组实现。
单调栈：用于查找下一个更大/更小元素。
队列：FIFO，enqueue, dequeue, peek，链表/数组实现。
循环队列：用数组实现队列，通过模运算处理环绕。
堆/优先队列：完全二叉树、堆序性，O(logN) 的插入和删除根节点，O(1) 的获取根节点。
最大堆/最小堆：两种堆的性质。
对顶堆：解决数据流中位数问题。

课后练习（推荐力扣 LeetCode 题目）：

有效括号 (Valid Parentheses)：LeetCode 20
最小栈 (Min Stack)：LeetCode 155
每日温度 (Daily Temperatures)：LeetCode 739
下一个更大元素 I (Next Greater Element I)：LeetCode 496 (与每日温度类似)
用栈实现队列 (Implement Queue using Stacks)：LeetCode 232
用队列实现栈 (Implement Stack using Queues)：LeetCode 225
设计循环队列 (Design Circular Queue)：LeetCode 622
前 K 个高频元素 (Top K Frequent Elements)：LeetCode 347
数据流中的中位数 (Find Median from Data Stream)：LeetCode 295
Kth 最大的元素 (Kth Largest Element in an Array)：LeetCode 215 (可以使用最小堆)

熟练掌握这些高效容器及其典型应用，将为你在面试中处理各种数据结构问题打下坚实的基础。下篇我们将进入哈希表与字符串的世界，探索高效查找和文本处理的奥秘！准备好了吗？

算法入门第三篇：高效容器：栈、队列与堆

引言：容器的哲学

栈（Stack）：后进先出的“桶”

概念

基本操作

实现方式

应用场景

经典面试题与解法（栈）

1. 有效括号 (Valid Parentheses)

2. 最小栈 (Min Stack)

3. 每日温度 (Daily Temperatures) / 下一个更大元素 (Next Greater Element)

队列（Queue）：先进先出的“队伍”

概念

基本操作

实现方式

应用场景

经典面试题与解法（队列）

1. 用栈实现队列 (Implement Queue using Stacks)

2. 用队列实现栈 (Implement Stack using Queues)

3. 循环队列 (Circular Queue)

堆（Heap）/优先队列（Priority Queue）：按优先级出队

概念

基本操作（基于堆实现的优先队列）

堆的实现核心：上浮（Heapify Up）与下沉（Heapify Down）

应用场景

经典面试题与解法（堆/优先队列）

1. 前 K 个高频元素 (Top K Frequent Elements)

2. 数据流中的中位数 (Find Median from Data Stream)

总结与练习

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

算法入门第三篇：高效容器：栈、队列与堆

引言：容器的哲学

栈（Stack）：后进先出的“桶”

概念

基本操作

实现方式

应用场景

经典面试题与解法（栈）

1. 有效括号 (Valid Parentheses)

2. 最小栈 (Min Stack)

3. 每日温度 (Daily Temperatures) / 下一个更大元素 (Next Greater Element)

队列（Queue）：先进先出的“队伍”

概念

基本操作

实现方式

应用场景

经典面试题与解法（队列）

1. 用栈实现队列 (Implement Queue using Stacks)

2. 用队列实现栈 (Implement Stack using Queues)

3. 循环队列 (Circular Queue)

堆（Heap）/优先队列（Priority Queue）：按优先级出队

概念

基本操作（基于堆实现的优先队列）

堆的实现核心：上浮（Heapify Up）与下沉（Heapify Down）

应用场景

经典面试题与解法（堆/优先队列）

1. 前 K 个高频元素 (Top K Frequent Elements)

2. 数据流中的中位数 (Find Median from Data Stream)

总结与练习

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签