使用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 容器，能夠充分利用空間，同時保證了鏈表的操作。