Ch 10: VecDeque - 双端队列

1. 引言

VecDeque<T> 是 Rust 标准库提供的双端队列实现，提供了在两端高效插入和删除操作。相比 Vec，VecDeque 在头部操作具有 O(1) 的时间复杂度，非常适合用作队列或缓冲区。

2. VecDeque 基础

创建 VecDeque：

use std::collections::VecDeque;

fn main() {
    // 空队列
    let mut deque: VecDeque<i32> = VecDeque::new();

    // 从迭代器创建
    let deque = VecDeque::from(vec![1, 2, 3]);

    // with_capacity 预分配
    let mut deque = VecDeque::with_capacity(10);
}

3. push_front 和 push_back - 两端插入

push_back - 队尾插入：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();

    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);

    println!("{:?}", deque);  // [1, 2, 3]
}

push_front - 队首插入：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();

    deque.push_back(2);
    deque.push_back(3);

    deque.push_front(1);  // 插入到队首

    println!("{:?}", deque);  // [1, 2, 3]
}

4. pop_front 和 pop_back - 两端移除

pop_back - 队尾移除：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3]);

    let back = deque.pop_back();
    println!("pop_back: {:?}", back);  // Some(3)
    println!("{:?}", deque);            // [1, 2]
}

pop_front - 队首移除：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3]);

    let front = deque.pop_front();
    println!("pop_front: {:?}", front);  // Some(1)
    println!("{:?}", deque);              // [2, 3]
}

5. make_contiguous - 连续内存

make_contiguous 将 VecDeque 的内部缓冲区转换为连续的内存切片：

方法签名：

pub fn make_contiguous(&mut self) -> (&mut [T], usize)

示例：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3, 4, 5]);

    // 获取连续的 slice
    let (slice, start) = deque.make_contiguous();

    println!("slice: {:?}", slice);
    println!("start index: {}", start);
    // slice: [1, 2, 3, 4, 5]
    // start index: 0
}

用于高效迭代：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3, 4, 5]);

    // 使用 make_contiguous 进行高效迭代
    for (i, &val) in deque.make_contiguous().iter().enumerate() {
        println!("index {}: {}", i, val);
    }
}

6. front 和 back - 查看端点

front - 查看队首（不可变）：

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from(vec![1, 2, 3]);

    println!("front: {:?}", deque.front());  // Some(&1)
    println!("front_mut: {:?}", deque.front_mut().map(|r| *r));  // Some(1)
}

back - 查看队尾（不可变）：

use std::collections::VecDeque;

fn main() {
    let deque = VecDeque::from(vec![1, 2, 3]);

    println!("back: {:?}", deque.back());  // Some(&3)
}

7. insert - 中间插入

insert 在指定位置插入元素：

方法签名：

pub fn insert(&mut self, idx: usize, elt: T)

示例：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3]);

    // 在索引 1 处插入
    deque.insert(1, 10);

    println!("{:?}", deque);  // [1, 10, 2, 3]
}

注意： insert 的时间复杂度是 O(n)。

8. remove - 中间移除

remove 移除并返回指定位置的元素：

方法签名：

pub fn remove(&mut self, idx: usize) -> Option<T>

示例：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3, 4, 5]);

    let removed = deque.remove(2);
    println!("removed: {:?}", removed);  // Some(3)
    println!("{:?}", deque);             // [1, 2, 4, 5]
}

9. retain - 条件保留

retain 保留满足条件的元素：

方法签名：

pub fn retain<F>(&mut self, f: F)
where
    F: FnMut(&T) -> bool,

示例：

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(vec![1, 2, 3, 4, 5, 6]);

    // 保留偶数
    deque.retain(|&x| x % 2 == 0);

    println!("{:?}", deque);  // [2, 4, 6]
}

10. 实战示例：高效队列

use std::collections::VecDeque;

struct Queue<T> {
    deque: VecDeque<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue {
            deque: VecDeque::new(),
        }
    }

    fn enqueue(&mut self, item: T) {
        self.deque.push_back(item);
    }

    fn dequeue(&mut self) -> Option<T> {
        self.deque.pop_front()
    }

    fn peek(&self) -> Option<&T> {
        self.deque.front()
    }

    fn len(&self) -> usize {
        self.deque.len()
    }

    fn is_empty(&self) -> bool {
        self.deque.is_empty()
    }
}

fn main() {
    let mut queue = Queue::new();

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    println!("len: {}", queue.len());      // 3
    println!("peek: {:?}", queue.peek()); // Some(&1)

    while let Some(item) = queue.dequeue() {
        println!("dequeued: {}", item);
    }
    // 1, 2, 3

    println!("is_empty: {}", queue.is_empty());  // true
}

11. Vec vs VecDeque

操作	Vec	VecDeque
push_back	O(1) 均摊	O(1)
push_front	O(n)	O(1)
pop_back	O(1)	O(1)
pop_front	O(n)	O(1)
insert(中间)	O(n)	O(n)
remove(中间)	O(n)	O(n)

12. 需要注意的点

1. VecDeque 的内部结构：使用环形缓冲区实现，避免了每次在头部插入时的元素移动。

2. make_contiguous 的返回值：返回 (slice, start) 元组，start 是有效数据起始位置在 slice 中的偏移。

3. insert 和 remove 的性能：虽然是双端队列，但在中间位置的操作仍然是 O(n)。

4. VecDeque 实现了 From<Vec<T>>：可以方便地将 Vec 转换为 VecDeque。

5. VecDeque 适用于队列和缓冲区：如果你需要频繁在头部操作，VecDeque 是更好的选择。

13. 总结

VecDeque 是 Rust 中的双端队列实现：

方法	作用	复杂度
push_back	队尾插入	O(1)
push_front	队首插入	O(1)
pop_back	队尾移除	O(1)
pop_front	队首移除	O(1)
front/back	查看端点	O(1)
make_contiguous	获取连续切片	O(n)
insert	中间插入	O(n)
remove	中间移除	O(n)
retain	条件保留	O(n)

当需要频繁在两端操作时，VecDeque 是比 Vec 更好的选择。