C++雙向隊列

在隊列中，我們僅能在頭部刪除或在尾部添加元素。如圖 5-7 所示，「雙向隊列 deque」提供了更高的靈活性，允許在頭部和尾部執(zhí)行元素的添加或刪除操作。

圖 5-7   雙向隊列的操作

雙向隊列常用操作

雙向隊列的常用操作如表 5-3 所示，具體的方法名稱需要根據(jù)所使用的編程語言來確定。

表 5-3   雙向隊列操作效率

同樣地，我們可以直接使用編程語言中已實現(xiàn)的雙向隊列類。

deque.cpp

/* 初始化雙向隊列 */
deque<int> deque;

/* 元素入隊 */
deque.push_back(2);   // 添加至隊尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // 添加至隊首
deque.push_front(1);

/* 訪問元素 */
int front = deque.front(); // 隊首元素
int back = deque.back();   // 隊尾元素

/* 元素出隊 */
deque.pop_front();  // 隊首元素出隊
deque.pop_back();   // 隊尾元素出隊

/* 獲取雙向隊列的長度 */
int size = deque.size();

/* 判斷雙向隊列是否為空 */
bool empty = deque.empty();

雙向隊列實現(xiàn) *

雙向隊列的實現(xiàn)與隊列類似，可以選擇鏈表或數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)。

1.   基于雙向鏈表的實現(xiàn)

回顧上一節(jié)內(nèi)容，我們使用普通單向鏈表來實現(xiàn)隊列，因為它可以方便地刪除頭節(jié)點（對應(yīng)出隊操作）和在尾節(jié)點后添加新節(jié)點（對應(yīng)入隊操作）。

對于雙向隊列而言，頭部和尾部都可以執(zhí)行入隊和出隊操作。換句話說，雙向隊列需要實現(xiàn)另一個對稱方向的操作。為此，我們采用“雙向鏈表”作為雙向隊列的底層數(shù)據(jù)結(jié)構(gòu)。

如圖 5-8 所示，我們將雙向鏈表的頭節(jié)點和尾節(jié)點視為雙向隊列的隊首和隊尾，同時實現(xiàn)在兩端添加和刪除節(jié)點的功能。

圖 5-8   基于鏈表實現(xiàn)雙向隊列的入隊出隊操作

實現(xiàn)代碼如下所示。

linkedlist_deque.cpp

/* 雙向鏈表節(jié)點 */
struct DoublyListNode {
    int val;              // 節(jié)點值
    DoublyListNode *next; // 后繼節(jié)點指針
    DoublyListNode *prev; // 前驅(qū)節(jié)點指針
    DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {
    }
};

/* 基于雙向鏈表實現(xiàn)的雙向隊列 */
class LinkedListDeque {
  private:
    DoublyListNode *front, *rear; // 頭節(jié)點 front ，尾節(jié)點 rear
    int queSize = 0;              // 雙向隊列的長度

  public:
    /* 構(gòu)造方法 */
    LinkedListDeque() : front(nullptr), rear(nullptr) {
    }

    /* 析構(gòu)方法 */
    ~LinkedListDeque() {
        // 遍歷鏈表刪除節(jié)點，釋放內(nèi)存
        DoublyListNode *pre, *cur = front;
        while (cur != nullptr) {
            pre = cur;
            cur = cur->next;
            delete pre;
        }
    }

    /* 獲取雙向隊列的長度 */
    int size() {
        return queSize;
    }

    /* 判斷雙向隊列是否為空 */
    bool isEmpty() {
        return size() == 0;
    }

    /* 入隊操作 */
    void push(int num, bool isFront) {
        DoublyListNode *node = new DoublyListNode(num);
        // 若鏈表為空，則令 front, rear 都指向 node
        if (isEmpty())
            front = rear = node;
        // 隊首入隊操作
        else if (isFront) {
            // 將 node 添加至鏈表頭部
            front->prev = node;
            node->next = front;
            front = node; // 更新頭節(jié)點
        // 隊尾入隊操作
        } else {
            // 將 node 添加至鏈表尾部
            rear->next = node;
            node->prev = rear;
            rear = node; // 更新尾節(jié)點
        }
        queSize++; // 更新隊列長度
    }

    /* 隊首入隊 */
    void pushFirst(int num) {
        push(num, true);
    }

    /* 隊尾入隊 */
    void pushLast(int num) {
        push(num, false);
    }

    /* 出隊操作 */
    int pop(bool isFront) {
        if (isEmpty())
            throw out_of_range("隊列為空");
        int val;
        // 隊首出隊操作
        if (isFront) {
            val = front->val; // 暫存頭節(jié)點值
            // 刪除頭節(jié)點
            DoublyListNode *fNext = front->next;
            if (fNext != nullptr) {
                fNext->prev = nullptr;
                front->next = nullptr;
                delete front;
            }
            front = fNext; // 更新頭節(jié)點
        // 隊尾出隊操作
        } else {
            val = rear->val; // 暫存尾節(jié)點值
            // 刪除尾節(jié)點
            DoublyListNode *rPrev = rear->prev;
            if (rPrev != nullptr) {
                rPrev->next = nullptr;
                rear->prev = nullptr;
                delete rear;
            }
            rear = rPrev; // 更新尾節(jié)點
        }
        queSize--; // 更新隊列長度
        return val;
    }

    /* 隊首出隊 */
    int popFirst() {
        return pop(true);
    }

    /* 隊尾出隊 */
    int popLast() {
        return pop(false);
    }

    /* 訪問隊首元素 */
    int peekFirst() {
        if (isEmpty())
            throw out_of_range("雙向隊列為空");
        return front->val;
    }

    /* 訪問隊尾元素 */
    int peekLast() {
        if (isEmpty())
            throw out_of_range("雙向隊列為空");
        return rear->val;
    }

    /* 返回數(shù)組用于打印 */
    vector<int> toVector() {
        DoublyListNode *node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }
};

2.   基于數(shù)組的實現(xiàn)

如圖 5-9 所示，與基于數(shù)組實現(xiàn)隊列類似，我們也可以使用環(huán)形數(shù)組來實現(xiàn)雙向隊列。

圖 5-9   基于數(shù)組實現(xiàn)雙向隊列的入隊出隊操作

在隊列的實現(xiàn)基礎(chǔ)上，僅需增加“隊首入隊”和“隊尾出隊”的方法。

array_deque.cpp

/* 基于環(huán)形數(shù)組實現(xiàn)的雙向隊列 */
class ArrayDeque {
  private:
    vector<int> nums; // 用于存儲雙向隊列元素的數(shù)組
    int front;        // 隊首指針，指向隊首元素
    int queSize;      // 雙向隊列長度

  public:
    /* 構(gòu)造方法 */
    ArrayDeque(int capacity) {
        nums.resize(capacity);
        front = queSize = 0;
    }

    /* 獲取雙向隊列的容量 */
    int capacity() {
        return nums.size();
    }

    /* 獲取雙向隊列的長度 */
    int size() {
        return queSize;
    }

    /* 判斷雙向隊列是否為空 */
    bool isEmpty() {
        return queSize == 0;
    }

    /* 計算環(huán)形數(shù)組索引 */
    int index(int i) {
        // 通過取余操作實現(xiàn)數(shù)組首尾相連
        // 當(dāng) i 越過數(shù)組尾部后，回到頭部
        // 當(dāng) i 越過數(shù)組頭部后，回到尾部
        return (i + capacity()) % capacity();
    }

    /* 隊首入隊 */
    void pushFirst(int num) {
        if (queSize == capacity()) {
            cout << "雙向隊列已滿" << endl;
            return;
        }
        // 隊首指針向左移動一位
        // 通過取余操作，實現(xiàn) front 越過數(shù)組頭部后回到尾部
        front = index(front - 1);
        // 將 num 添加至隊首
        nums[front] = num;
        queSize++;
    }

    /* 隊尾入隊 */
    void pushLast(int num) {
        if (queSize == capacity()) {
            cout << "雙向隊列已滿" << endl;
            return;
        }
        // 計算尾指針，指向隊尾索引 + 1
        int rear = index(front + queSize);
        // 將 num 添加至隊尾
        nums[rear] = num;
        queSize++;
    }

    /* 隊首出隊 */
    int popFirst() {
        int num = peekFirst();
        // 隊首指針向后移動一位
        front = index(front + 1);
        queSize--;
        return num;
    }

    /* 隊尾出隊 */
    int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    /* 訪問隊首元素 */
    int peekFirst() {
        if (isEmpty())
            throw out_of_range("雙向隊列為空");
        return nums[front];
    }

    /* 訪問隊尾元素 */
    int peekLast() {
        if (isEmpty())
            throw out_of_range("雙向隊列為空");
        // 計算尾元素索引
        int last = index(front + queSize - 1);
        return nums[last];
    }

    /* 返回數(shù)組用于打印 */
    vector<int> toVector() {
        // 僅轉(zhuǎn)換有效長度范圍內(nèi)的列表元素
        vector<int> res(queSize);
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[index(j)];
        }
        return res;
    }
};

雙向隊列應(yīng)用

雙向隊列兼具棧與隊列的邏輯，因此它可以實現(xiàn)這兩者的所有應(yīng)用場景，同時提供更高的自由度。

我們知道，軟件的“撤銷”功能通常使用棧來實現(xiàn)：系統(tǒng)將每次更改操作 push 到棧中，然后通過 pop 實現(xiàn)撤銷。然而，考慮到系統(tǒng)資源的限制，軟件通常會限制撤銷的步數(shù)（例如僅允許保存 50 步）。當(dāng)棧的長度超過 50 時，軟件需要在棧底（即隊首）執(zhí)行刪除操作。但棧無法實現(xiàn)該功能，此時就需要使用雙向隊列來替代棧。請注意，“撤銷”的核心邏輯仍然遵循棧的先入后出原則，只是雙向隊列能夠更加靈活地實現(xiàn)一些額外邏輯。