数据结构与算法 - Deque

2026-06-07

全文 ≈ 1.9k字 | 预计阅读时长 8分钟

Deque（Double-Ended Queue，双端队列）是一种允许在头尾两端进行插入和删除的线性数据结构。

前言

从定义上来看，Deque 只是比 Queue 多了一端的操作能力。但与 Queue 不同的是，Deque 同时具备 Stack 和 Queue 的访问模式，因此在需要灵活处理头尾两端元素的场景中广泛应用。

它们之间的区别很直观：

Queue: FIFO（First In, First Out，先进先出）

Deque: FIFO / LIFO（先进先出 / 后进先出）

为什么需要双端队列

假设现在有一个任务调度的场景，使用队列顺序存放任务，由 worker 负责消费队列中的任务。理想情况下，这种设计并没有什么问题，任务会以先进先出（FIFO）的顺序依次被处理。

但随着业务量上升，队列中的任务会越来越多，逐渐形成反压，系统的整体吞吐量也会随之下降。那么，这时候该如何优化？

一个很粗暴的方式就是增加 worker 数量以提高任务消费能力。但是多个 worker 频繁竞争同一个队列，为了保证并发安全，通常需要给队列加锁，随着 worker 数量的增加，锁冲突和调度开销会越来越明显，系统吞吐量未必能线性提升。

既然多个 worker 竞争同一个队列的成本越来越高，就可以进一步将任务拆分到多个队列中，让每个 worker 都维护一个本地队列。

不过，这种方式依然存在缺陷。由于不同的 worker 处理速度并不一致，所以可能会出现 worker A 已经把本地队列消费完，但是 worker B 本地队列中还积压大量任务。

这种负载不均衡的结果很难避免。即使在任务投递阶段已经尽可能做了均匀分配，例如通过 crc32 等方式将任务平均散列到不同队列中，也无法保证每个 worker 在运行过程中始终保持相同的处理进度。

要解决这个问题，一种常见的做法是允许空闲 worker 从其他 worker 的本地队列中“偷”走一部分任务，也就是工作窃取算法（work-stealing）。

但是到了这个阶段，队列的访问模式已经不同于普通 Queue。假设 worker A 已经处理完本地队列，这时候需要去“偷” worker B 本地队列中的任务，如果双方仍然从同一端操作队列，很容易产生新的并发问题：

worker A 和 worker B 会更频繁地竞争同一批任务，增加同步开销。
worker A 可能拿到 worker B 即将处理的任务，从而进一步加剧访问冲突。

如果可以从两端分别访问队列，就可以在一定程度上缓解这个问题：worker B 作为队列所有者，继续从尾部压入和消费本地任务；worker A 作为窃取者，则从头部窃取较早进入队列的任务。

也就是说，“所有者”和“窃取者”对于同一个队列的访问方向并不一样。可以用访问模式来概括：

Owner: LIFO

Thief: FIFO

双端队列用于工作窃取的场景

Deque

双端队列的常见 API 包括：

push_front: 从队头插入元素

push_back: 从队尾插入元素

pop_front: 从队头弹出元素

pop_back: 从队尾弹出元素

如果只从队尾插入、从队头弹出，那么访问模式和普通 Queue 一样：

FIFO
push_back -> pop_front

如果固定从同一端插入和弹出，那么访问模式就和 Stack 一样：

LIFO
push_back -> pop_back

简而言之，Deque 并不是一种新的访问模式，而是把 Queue 和 Stack 的访问模式统一到一个结构中。

一般有两种常见实现方案：

双向链表
循环数组

双向链表实现起来更直观，但在更关注性能的场景中，循环数组通常更常见。

循环数组

循环数组并不真的是个环，而是通过取模运算把数组从逻辑上变成一个头尾相接的环。

next = (index + 1) % n

prev = (index - 1 + n) % n

假设有个长度 8 的数组：

1 2	idx: [0, 1, 2, 3, 4, 5, 6, 7] vec: [_, _, _, _, _, _, _, _]

可以通过 head 和 len（元素数量）计算出 tail 的位置：

tail = (head + len) % n

初始状态下，head 和 tail 都指向 index 0，head 表示队头元素位置，tail 表示队尾下一个可写位置。

push_back(A)
push_back(B)

idx: [0,  1,  2,  3,  4,  5,  6,  7]
vec: [A,  B,  _,  _,  _,  _,  _,  _]

从队尾写入数据 A、B 以后，head 依然指向 index 0，但是 tail 现在指向的是 index 2。

pop_front() -> A

idx: [0,  1,  2,  3,  4,  5,  6,  7]
vec: [_,  B,  _,  _,  _,  _,  _,  _]

从队头弹出元素 A 之后，其他元素的位置没有发生变更，只是 head 的位置由 index 0 变成 index 1。

目前看起来好像和环还没什么关系，现在执行多次队尾写入。

push_back(C)
push_back(D)
push_back(E)
push_back(F)
push_back(G)
push_back(H)

idx: [0,  1,  2,  3,  4,  5,  6,  7]
vec: [_,  B,  C,  D,  E,  F,  G,  H]

此时 tail 指向是：

(1 + 7) % 8 = 0

这时候数组元素通过取模运算在逻辑上形成了一个环。

实现

直接看代码：

struct Deque<T> {
    buf: Vec<Option<T>>,
    head: usize,
    len: usize,
}

impl<T> Deque<T> {
    fn new() -> Self {
        Self::with_capacity(8)
    }

    fn with_capacity(capacity: usize) -> Self {
        let capacity = capacity.max(1);
        let mut buf = Vec::with_capacity(capacity);
        buf.resize_with(capacity, || None);

        Self {
            buf,
            head: 0,
            len: 0,
        }
    }

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

    fn is_empty(&self) -> bool {
        self.len == 0
    }

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

    fn is_full(&self) -> bool {
        self.len == self.capacity()
    }

    fn push_back(&mut self, value: T) -> Result<(), T> {
        if self.is_full() {
            return Err(value);
        }

        let tail = self.physical_index(self.len);
        self.buf[tail] = Some(value);
        self.len += 1;
        Ok(())
    }

    fn push_front(&mut self, value: T) -> Result<(), T> {
        if self.is_full() {
            return Err(value);
        }

        self.head = self.prev(self.head);
        self.buf[self.head] = Some(value);
        self.len += 1;
        Ok(())
    }

    fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        let tail = self.physical_index(self.len - 1);
        self.len -= 1;
        self.buf[tail].take()
    }

    fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }

        let old_head = self.head;
        self.head = self.next(self.head);
        self.len -= 1;
        self.buf[old_head].take()
    }

    fn front(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            self.buf[self.head].as_ref()
        }
    }

    fn back(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            let tail = self.physical_index(self.len - 1);
            self.buf[tail].as_ref()
        }
    }

    fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }

        self.buf[self.physical_index(index)].as_ref()
    }

    fn physical_index(&self, logical_index: usize) -> usize {
        (self.head + logical_index) % self.capacity()
    }

    fn next(&self, index: usize) -> usize {
        (index + 1) % self.capacity()
    }

    fn prev(&self, index: usize) -> usize {
        (index + self.capacity() - 1) % self.capacity()
    }
}

#[cfg(test)]
mod tests {
    use super::Deque;

    fn values(deque: &Deque<char>) -> Vec<char> {
        (0..deque.len()).map(|i| *deque.get(i).unwrap()).collect()
    }

    #[test]
    fn push_back_wraps_around() {
        let mut deque = Deque::new();

        assert_eq!(deque.push_back('A'), Ok(()));
        assert_eq!(deque.push_back('B'), Ok(()));
        assert_eq!(deque.pop_front(), Some('A'));

        for ch in ['C', 'D', 'E', 'F', 'G', 'H'] {
            assert_eq!(deque.push_back(ch), Ok(()));
        }

        assert_eq!(values(&deque), vec!['B', 'C', 'D', 'E', 'F', 'G', 'H']);
        assert_eq!(deque.back(), Some(&'H'));

        assert_eq!(deque.push_back('I'), Ok(()));
        assert_eq!(
            deque.buf,
            vec![
                Some('I'),
                Some('B'),
                Some('C'),
                Some('D'),
                Some('E'),
                Some('F'),
                Some('G'),
                Some('H'),
            ]
        );
        assert_eq!(values(&deque), vec!['B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']);
    }
}