Basillica 2024-03-27
队列在许多程序中是一种非常有用的数据结构。它允许你将元素添加到队列的一端，并从另一端移除元素，遵循先进先出（FIFO）的顺序。在这篇博客文章中，我将提供一份完整的指南，介绍如何在 Rust 中实现和使用队列。
什么是队列？
队列是一种线性数据结构，允许将元素添加到一端（称为“队尾”），并从另一端（称为“队首”）移除元素。元素被移除的顺序与其被添加的顺序相同，从而实现了 FIFO（先进先出）的排序方式。
这种排序方式使得队列在需要按到达顺序处理元素时非常有用。常见的应用场景包括：
- 任务处理 —— 将任务添加到队尾，然后从队首依次处理
- 打印任务排队 —— 将打印作业加入队列，打印机从队首取出作业进行处理
- Web 请求处理 —— 按照请求到达的顺序接收并处理请求
队列与栈不同，栈是 LIFO（后进先出）的结构；队列也不同于优先队列，后者出队顺序取决于优先级，而不仅仅是到达顺序。
在 Rust 中实现队列
Rust 的标准库中没有内置的队列数据结构。不过，我们可以使用 Vec 作为底层存储来实现一个基本的队列。
下面是一个简单的队列实现：
struct Queue {
data: Vec<i32>
}
impl Queue {
fn new() -> Self {
Queue { data: Vec::new() }
}
fn enqueue(&mut self, item: i32) {
self.data.push(item);
}
fn dequeue(&mut self) -> Option<i32> {
self.data.pop()
}
fn peek(&self) -> Option<&i32> {
self.data.first()
}
fn len(&self) -> usize {
self.data.len()
}
fn is_empty(&self) -> bool {
self.data.is_empty()
}
}
该实现提供了一个基本的队列，包含用于添加和删除元素的 enqueue 和 dequeue 方法、用于查看下一个元素的 peek 方法，以及用于检查队列状态的 len 和 is_empty 方法。
我们使用 Rust 的 Option 枚举作为 dequeue 和 peek 的返回类型，以处理队列为空的情况。
队列操作
让我们看看如何使用这个队列实现：
let mut queue = Queue::new();
// 添加一些元素
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 检查值
assert_eq!(queue.peek(), Some(&1));
assert_eq!(queue.len(), 3);
// 移除一个元素
assert_eq!(queue.dequeue(), Some(1));
// 检查结果
assert_eq!(queue.peek(), Some(&2));
assert_eq!(queue.len(), 2);
这展示了基本的队列操作：
- Enqueue（入队） —— 将元素添加到队尾
- Dequeue（出队） —— 从队首移除元素
- Peek（窥视） —— 查看下一个将被出队的元素
- Len（长度） —— 获取当前队列长度
此外，还有 is_empty 和 len 等方法用于检查队列的状态。
处理下溢（Underflow）
我们当前的队列实现在对空队列调用 dequeue 或 peek 时会引发 panic：
let mut queue = Queue::new();
// 这里会 panic！
let x = queue.dequeue();
为了正确处理这种情况，当队列为空时，我们应该让 dequeue 和 peek 返回 None：
impl Queue {
// ...
fn dequeue(&mut self) -> Option<i32> {
if self.is_empty() {
None
} else {
self.data.pop()
}
}
fn peek(&self) -> Option<&i32> {
self.data.first().copied()
}
}
现在，当队列为空时，dequeue 和 peek 会安全地返回 None，而不会 panic。
实现有界队列（Bounded Queue）
上面的队列具有无界长度，因为我们使用 Vec 存储元素。我们可以通过实现一个具有固定容量的有界队列来改进这一点。
下面是一个使用固定大小数组作为存储的实现：
struct BoundedQueue {
data: [i32; 5],
head: usize,
tail: usize,
len: usize
}
impl BoundedQueue {
fn new() -> Self {
BoundedQueue {
data: [0; 5],
head: 0,
tail: 0,
len: 0
}
}
// ... enqueue, dequeue, 其他方法 ...
}
这里我们不再使用 Vec，而是使用一个包含 5 个元素的固定大小数组来存储队列项。
我们还需要跟踪 head（队首）和 tail（队尾）索引，以确定在数组中的哪个位置添加或移除元素。
这种有界队列的一些优点包括：
- 固定的最大容量
- 数组存储带来可预测的内存使用
- 更容易分析时间和空间复杂度（Big O）
当然，固定容量意味着我们在入队时需要处理队列已满的情况。
我们可以返回一个 Result 而不是 panic：
enum Error {
Full
}
impl BoundedQueue {
// ...
fn enqueue(&mut self, item: i32) -> Result<(), Error> {
if self.len >= self.data.len() {
return Err(Error::Full)
}
self.data[self.tail] = item;
self.tail = (self.tail + 1) % self.data.len();
self.len += 1;
Ok(())
}
}
这展示了有界队列如何为我们提供对队列行为的更多控制。
使用 Mutex 实现线程安全
到目前为止，我们的队列实现都不是线程安全的。多个线程同时访问可能会导致错误和状态不一致。
为了让队列线程安全，我们可以使用 Rust 的 Mutex 类型，它提供了互斥锁机制：
use std::sync::Mutex;
struct Queue {
data: Mutex<Vec<i32>>
}
impl Queue {
fn new() -> Self {
Queue {
data: Mutex::new(Vec::new())
}
}
fn enqueue(&self, item: i32) {
let mut data = self.data.lock().unwrap();
data.push(item);
}
// ... 其他方法 ...
}
通过将内部的 Vec 包裹在 Mutex 中，我们确保同一时间只有一个线程可以访问队列。lock 方法返回一个锁守卫（lock guard），当它离开作用域时会自动释放锁。
这样就可以安全地在多个线程中并发地进行入队和出队操作。
阻塞队列实现
到目前为止的队列实现都是非阻塞的。enqueue 和 dequeue 方法要么立即成功，要么返回一个错误结果。
有时我们希望队列在出队时如果为空则阻塞，或者在入队时如果已满则阻塞。这种阻塞队列在同步线程或进程时非常有用。
下面是一种使用 Rust 通道（channel）实现阻塞队列的方式：
use std::sync::{Arc, Mutex};
use std::sync::mpsc::{channel, Receiver, Sender};
struct BlockingQueue {
sender: Mutex<Option<Sender<i32>>>,
receiver: Mutex<Option<Receiver<i32>>>
}
impl BlockingQueue {
fn new() -> Self {
let (sender, receiver) = channel();
BlockingQueue {
sender: Mutex::new(Some(sender)),
receiver: Mutex::new(Some(receiver))
}
}
fn enqueue(&self, item: i32) {
let mut send = self.sender.lock().unwrap();
send.as_ref().unwrap().send(item).unwrap();
}
fn dequeue(&self) -> i32 {
let mut recv = self.receiver.lock().unwrap();
recv.as_mut().unwrap().recv().unwrap()
}
}
通过使用 Rust 的通道作为内部队列存储，send 和 recv 操作会在通道满或空时自动阻塞。
这样就无需自己管理阻塞逻辑，即可获得阻塞队列的语义。