16-集合：堆栈和队列
堆栈（Stack）和队列（Queue）是两种特殊的数据结构，常用于特定的数据处理场景。
一、Stack<T> vs Queue<T> 核心区别
| 特性 | Stack<T> | Queue<T> |
|---|---|---|
| 数据结构 | 后进先出（LIFO） | 先进先出（FIFO） |
| 添加元素 | Push(item) 到栈顶 | Enqueue(item) 到队尾 |
| 移除元素 | Pop() 从栈顶移除 | Dequeue() 从队首移除 |
| 查看元素 | Peek() 查看栈顶（不移除） | Peek() 查看队首（不移除） |
| 现实类比 | 一叠盘子 | 排队买票 |
| 典型应用 | 括号匹配、撤销操作、函数调用栈 | 消息队列、BFS、任务调度 |
二、Stack<T>（堆栈）
1. 结构示意图
Push(入栈) Pop(出栈)
↓ ↑
┌──────┐ ┌──────┐
│ C │ ← 栈顶（最后进，最先出）
├──────┤
│ B │
├──────┤
│ A │ ← 栈底（最先进，最后出）
└──────┘2. 基本操作
csharp
Stack<string> stack = new Stack<string>();
// 入栈
stack.Push("第一行");
stack.Push("第二行");
stack.Push("第三行");
// 查看栈顶
Console.WriteLine($"栈顶元素：{stack.Peek()}"); // 输出：第三行
// 出栈
string top = stack.Pop(); // 移除并返回栈顶元素："第三行"
Console.WriteLine($"出栈：{top}");
// Count：元素数量
Console.WriteLine($"剩余元素：{stack.Count}"); // 2
// 遍历（从栈顶到栈底）
foreach (string item in stack)
Console.WriteLine(item); // 第二行 → 第一行
// 转换为数组（索引0是栈顶）
string[] arr = stack.ToArray();
Console.WriteLine(arr[0]); // 第二行（栈顶）3. 应用场景
场景一：括号匹配
csharp
static bool IsValidBrackets(string expression)
{
Stack<char> stack = new Stack<char>();
foreach (char c in expression)
{
// 左括号入栈
if (c == '(' || c == '[' || c == '{')
{
stack.Push(c);
}
// 右括号检查匹配
else if (c == ')' || c == ']' || c == '}')
{
if (stack.Count == 0) return false; // 没有对应的左括号
char top = stack.Pop();
// 检查是否匹配
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{'))
{
return false; // 匹配错误
}
}
}
return stack.Count == 0; // 全部匹配完成后栈应为空
}
Console.WriteLine(IsValidBrackets("(1+2)")); // True
Console.WriteLine(IsValidBrackets("([1+2])")); // True
Console.WriteLine(IsValidBrackets("([1+2]}")); // False
Console.WriteLine(IsValidBrackets("([1+2]")); // False
Console.WriteLine(IsValidBrackets(")1+2(")); // False场景二：撤销/重做（Undo/Redo）
csharp
class Editor
{
private Stack<string> undoStack = new Stack<string>();
private Stack<string> redoStack = new Stack<string>();
private string current = "";
public void Type(string text)
{
undoStack.Push(current); // 保存当前状态
current += text;
redoStack.Clear(); // 新操作清除重做栈
Console.WriteLine($"当前内容：{current}");
}
public void Undo()
{
if (undoStack.Count > 0)
{
redoStack.Push(current); // 保存当前状态到重做栈
current = undoStack.Pop(); // 恢复到上一个状态
Console.WriteLine($"撤销后：{current}");
}
}
public void Redo()
{
if (redoStack.Count > 0)
{
undoStack.Push(current); // 保存当前状态到撤销栈
current = redoStack.Pop(); // 从重做栈恢复
Console.WriteLine($"重做后：{current}");
}
}
}
var editor = new Editor();
editor.Type("Hello"); // Hello
editor.Type(" World"); // Hello World
editor.Undo(); // Hello
editor.Undo(); // （空）
editor.Redo(); // Hello场景三：进制转换
csharp
// 十进制转二进制
static string DecimalToBinary(int decimalNumber)
{
Stack<int> stack = new Stack<int>();
while (decimalNumber > 0)
{
stack.Push(decimalNumber % 2); // 余数入栈
decimalNumber /= 2;
}
// 从栈顶到栈底拼接就是二进制结果
return string.Join("", stack);
}
Console.WriteLine(DecimalToBinary(10)); // 1010
Console.WriteLine(DecimalToBinary(255)); // 11111111三、Queue<T>（队列）
1. 结构示意图
入队(Enqueue) 出队(Dequeue)
↓ ↓
┌────┬────┬────┬────┐
│ A │ B │ C │ D │
└────┴────┴────┴────┘
↑ ↑
队尾 队首
（后进，后出） （先进，先出）2. 基本操作
csharp
Queue<string> queue = new Queue<string>();
// 入队
queue.Enqueue("第一个");
queue.Enqueue("第二个");
queue.Enqueue("第三个");
// 查看队首
Console.WriteLine($"队首元素：{queue.Peek()}"); // 输出：第一个
// 出队
string first = queue.Dequeue();
Console.WriteLine($"出队：{first}"); // 输出：第一个
Console.WriteLine($"剩余元素：{queue.Count}"); // 2
// 遍历（从队首到队尾）
foreach (string item in queue)
Console.WriteLine(item); // 第二个 → 第三个3. 应用场景
场景一：消息队列（生产者-消费者）
csharp
class MessageQueue
{
private Queue<string> queue = new Queue<string>();
private readonly object lockObj = new object();
// 生产者——发送消息
public void Send(string message)
{
lock (lockObj)
{
queue.Enqueue(message);
Console.WriteLine($"→ 发送消息：{message}（队列长度：{queue.Count}）");
}
}
// 消费者——处理消息
public void ProcessAll()
{
Console.WriteLine("\n开始处理消息...");
while (true)
{
string message;
lock (lockObj)
{
if (queue.Count == 0) break;
message = queue.Dequeue();
}
Console.WriteLine($"← 处理消息：{message}");
Thread.Sleep(200); // 模拟处理耗时
}
Console.WriteLine("所有消息处理完成\n");
}
}
var mq = new MessageQueue();
mq.Send("用户注册");
mq.Send("发送邮件");
mq.Send("写入日志");
mq.ProcessAll();
// 输出（按发送顺序处理）：
// 用户注册 → 发送邮件 → 写入日志场景二：广度优先搜索（BFS）
csharp
// 二叉树层序遍历
class TreeNode
{
public int Value;
public TreeNode? Left;
public TreeNode? Right;
public TreeNode(int val) => Value = val;
}
static void LevelOrderTraversal(TreeNode root)
{
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int level = 0;
while (queue.Count > 0)
{
int levelSize = queue.Count; // 当前层的节点数
Console.Write($"第 {level} 层：");
for (int i = 0; i < levelSize; i++)
{
TreeNode node = queue.Dequeue();
Console.Write($"{node.Value} ");
if (node.Left != null) queue.Enqueue(node.Left);
if (node.Right != null) queue.Enqueue(node.Right);
}
Console.WriteLine();
level++;
}
}
// 构建二叉树
TreeNode root = new TreeNode(1)
{
Left = new TreeNode(2)
{
Left = new TreeNode(4),
Right = new TreeNode(5)
},
Right = new TreeNode(3)
{
Left = new TreeNode(6),
Right = new TreeNode(7)
}
};
LevelOrderTraversal(root);
// 输出：
// 第 0 层：1
// 第 1 层：2 3
// 第 2 层：4 5 6 7场景三：请求限流（令牌桶）
csharp
class RateLimiter
{
private Queue<DateTime> requestTimes = new Queue<DateTime>();
private readonly int maxRequests;
private readonly TimeSpan window;
public RateLimiter(int maxRequests, TimeSpan window)
{
this.maxRequests = maxRequests;
this.window = window;
}
public bool AllowRequest()
{
DateTime now = DateTime.Now;
// 清除窗口外的旧记录
while (requestTimes.Count > 0 && now - requestTimes.Peek() > window)
{
requestTimes.Dequeue();
}
if (requestTimes.Count < maxRequests)
{
requestTimes.Enqueue(now);
return true; // 允许请求
}
return false; // 限流
}
}
// 使用：每分钟最多允许 5 个请求
var limiter = new RateLimiter(5, TimeSpan.FromMinutes(1));
for (int i = 0; i < 10; i++)
{
bool allowed = limiter.AllowRequest();
Console.WriteLine($"请求 {i + 1}：{(allowed ? "✅ 通过" : "❌ 限流")}");
}
// 前 5 个通过，后 5 个被限流四、Stack 与 Queue 的内存和性能
| 操作 | Stack<T> | Queue<T> |
|---|---|---|
| Push/Enqueue | O(1) 平摊 | O(1) 平摊 |
| Pop/Dequeue | O(1) | O(1) |
| Peek | O(1) | O(1) |
| 内存结构 | 数组（动态扩容） | 环形数组（动态扩容） |
两者内部都使用数组实现，扩容策略与 List<T> 类似（翻倍扩容）。
五、非泛型版本
csharp
using System.Collections;
// ❌ 不推荐——有装箱拆箱和类型安全问题
Stack oldStack = new Stack();
oldStack.Push(1);
oldStack.Push("string");
int val = (int)oldStack.Pop(); // 拆箱
Queue oldQueue = new Queue();
oldQueue.Enqueue(1);
oldQueue.Enqueue("string");
int num = (int)oldQueue.Dequeue(); // 拆箱建议： 始终使用泛型版本
Stack<T>和Queue<T>。
六、综合案例：表达式计算
csharp
// 简单的后缀表达式（逆波兰表达式）计算器
static int EvaluateRPN(string[] tokens)
{
Stack<int> stack = new Stack<int>();
foreach (string token in tokens)
{
if (int.TryParse(token, out int number))
{
stack.Push(number); // 数字直接入栈
}
else
{
// 运算符：弹出两个数，计算结果后入栈
int b = stack.Pop(); // 注意顺序：先弹出的是右操作数
int a = stack.Pop();
int result = token switch
{
"+" => a + b,
"-" => a - b,
"*" => a * b,
"/" => a / b,
_ => throw new NotSupportedException()
};
stack.Push(result);
}
}
return stack.Pop(); // 最终结果
}
// 中缀: (3 + 4) × 5 - 6
// 后缀: 3 4 + 5 × 6 -
string[] rpn = { "3", "4", "+", "5", "*", "6", "-" };
Console.WriteLine(EvaluateRPN(rpn)); // 输出：29核心知识点总结
Stack<T> 核心操作
| 方法 | 说明 | 栈变化 |
|---|---|---|
Push(item) | 入栈 | 元素添加到栈顶 |
Pop() | 出栈 | 移除并返回栈顶元素（栈空则异常） |
Peek() | 查看栈顶 | 返回但不移除栈顶元素（栈空则异常） |
Count | 元素数量 | — |
Queue<T> 核心操作
| 方法 | 说明 | 队列变化 |
|---|---|---|
Enqueue(item) | 入队 | 元素添加到队尾 |
Dequeue() | 出队 | 移除并返回队首元素（队空则异常） |
Peek() | 查看队首 | 返回但不移除队首元素（队空则异常） |
Count | 元素数量 | — |
选择建议
| 场景 | 选择 |
|---|---|
| 需要"后进先出" | Stack<T> |
| 需要"先进先出" | Queue<T> |
| 需要双端操作 | LinkedList<T> 或自定义 |
| 需要优先级处理 | PriorityQueue<T>（.NET 6+） |
注意事项
- Pop/Dequeue 空集合会异常：操作前检查
Count > 0 - Peek 空集合会异常：同样需要先检查
- 优先使用泛型版本：避免装箱拆箱
- foreach 不会改变集合内容：只是遍历，不会影响栈/队列状态
- Stack<T>/Queue<T> 不是线程安全的：多线程需要加锁或使用
ConcurrentStack<T>/ConcurrentQueue<T>