使用C++实现高效双端队列

一、STL提供的deque实现

C++ STL提供了deque （Double-Ended Queue，双端队列）容器，其能够快速地在首位添加和删除元素。下面是例子代码：

#include
#include
using namespace std;

int main()
{
    deque q; // 定义一个deque
    q.push_back(1); // 在末尾添加元素
    q.push_front(2); // 在头部添加元素
    q.pop_back(); // 删除末尾元素
    q.pop_front(); // 删除头部元素
    return 0;
}

deque 容器的底层实现是一块连续的内存空间，但是容器在各个元素之间预留了一些空间，以便实现常数时间的在头部和尾部添加或删除元素。deque 还提供了随机访问元素的能力，其时间复杂度为 O(1)。但是，deque 的空间利用率不是很高，虽然是连续内存，但预留空间一定程度浪费了空间。

二、双向链表实现

1. 链表节点的定义

双向链表是一种很好的选择，其可以充分利用空间，同时又具有快速在首尾添加或删除元素的能力。下面是链表节点的定义：

template 
struct LinkedNode {
    T data; // 数据域
    LinkedNode* prev; // 前驱指针
    LinkedNode* next; // 后继指针

    LinkedNode(const T& ele = T(), LinkedNode* ptr = nullptr) : data(ele), prev(ptr), next(ptr) {}
};

链表节点中 data 字段是该节点的数据域，prev 和 next 分别是该节点的前驱指针和后继指针。链表节点的构造函数可以传入一个值，用于初始化该节点的数据域。

2. 双向链表的实现

双向链表中，头结点的 prev 指向尾结点，尾结点的 next 指向头结点。链表模板类的实现如下：

template 
class LinkedList {
private:
    LinkedNode* head;
    LinkedNode* tail;
    int _size;

public:
    LinkedList() : head(new LinkedNode()), tail(head), _size(0) {}

    // 在链表尾部添加元素
    void push_back(const T& ele) {
        insert(tail, ele); // 将元素插入到尾结点之后
    }

    // 在链表头部添加元素
    void push_front(const T& ele) {
        LinkedNode* node = new LinkedNode(ele, head->next); // 新建一个节点
        node->next->prev = node; // 修改相邻节点的prev指针
        head->next = node; // 修改头结点的后继指针
        _size++; // 长度+1
    }

    // 删除链表尾部元素
    void pop_back() {
        if (empty()) return;
        LinkedNode* node = tail->prev; // 暂存尾结点的前驱节点
        node->prev->next = tail; // 修改相邻节点的next指针
        tail->prev = node->prev; // 修改尾结点的前驱指针
        delete node; // 删除节点
        _size--; // 长度-1
    }

    // 删除链表头部元素
    void pop_front() {
        if (empty()) return;
        LinkedNode* node = head->next; // 暂存头结点的后继节点
        head->next = node->next; // 修改头结点的后继指针
        node->next->prev = head; // 修改相邻节点的prev指针
        delete node; // 删除节点
        _size--; // 长度-1
    }

    // 判断链表是否为空
    bool empty() const { return _size == 0; }

    // 返回链表中元素的个数
    int size() const { return _size; }

private:
    // 将元素插入到列表中某个节点的后面
    void insert(LinkedNode* node, const T& elem) {
        LinkedNode* new_node = new LinkedNode(elem, node->next); // 新建一个节点
        new_node->next->prev = new_node; // 修改相邻节点指针
        node->next = new_node; // 插入节点
        if (new_node->next == nullptr) { // 如果插入的节点是尾结点的后继
            tail = new_node; // 更新尾结点指针
        }
        _size++; // 长度+1
    }
};

链表的构造函数中，初始化了头结点，并令尾结点指向头结点。链表中 _size 为节点个数。

三、使用自定义的双向链表实现双端队列

使用自定义的双向链表实现双端队列，只需要在链表的基础上添加队列的操作即可。下面是例子代码：

template 
class Deque {
public:
    void push_back(const T& ele) { list.push_back(ele); } // 在队尾添加元素
    void push_front(const T& ele) { list.push_front(ele); } // 在队头添加元素
    void pop_back() { list.pop_back(); } // 删除队尾元素
    void pop_front() { list.pop_front(); } // 删除队头元素
    bool empty() const { return list.empty(); } // 判断队列是否为空
    int size() const { return list.size(); } // 返回队列中元素的个数
private:
    LinkedList list; // 双向链表
};

该双端队列从 LinkedList 继承，包含 push_back、push_front、pop_back、pop_front 等方法，可以实现在首尾添加和删除元素并且保证了链表的特性不变。

四、总结

本文介绍了使用 C++ STL 中的 deque 容器实现和自定义链表实现的双端队列。双端队列是一种常用的数据结构，具有快速在首尾添加和删除元素的能力，非常适合对队列操作频繁的场景。链表实现的双端队列，相对于 STL 提供的 deque 容器，能够充分利用空间，同时保证了链表的操作。