数据结构：双端队列 (Deque)

什么是双端队列？

双端队列 (Deque, Double-Ended Queue) 是一种支持在两端插入和删除元素的线性数据结构。它结合了队列与栈的优点，既能从头部取元素，也能从尾部取元素。

基本操作

• PushFront: 在队首插入元素。
• PushBack: 在队尾插入元素。
• PopFront: 移除并返回队首元素。
• PopBack: 移除并返回队尾元素。
• PeekFront/PeekBack: 查看队首或队尾元素。

实现方式

常见实现包括环形数组与双向链表：

• 环形数组: 空间连续，适合高效的缓存访问。
• 双向链表: 插入删除常数时间，但内存分配开销更高。

C++ STL 中的 std::deque

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;
    dq.push_back(10);
    dq.push_front(5);
    std::cout << "front=" << dq.front() << ", back=" << dq.back() << std::endl;
    dq.pop_back();
    std::cout << "size=" << dq.size() << std::endl;
    return 0;
}

应用场景

• 单调队列: 维护窗口内的最大值/最小值。
• 缓存淘汰: LRU、LFU 等需要双向删除的场景。
• 双端调度: 任务既可能从头部也可能从尾部处理。