C++雙向隊(duì)列

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

圖 5-7   雙向隊(duì)列的操作

雙向隊(duì)列常用操作

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

表 5-3   雙向隊(duì)列操作效率

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

deque.cpp

/* 初始化雙向隊(duì)列 */
deque<int> deque;

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

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

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

/* 獲取雙向隊(duì)列的長(zhǎng)度 */
int size = deque.size();

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

雙向隊(duì)列實(shí)現(xiàn) *

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

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

回顧上一節(jié)內(nèi)容，我們使用普通單向鏈表來實(shí)現(xiàn)隊(duì)列，因?yàn)樗梢苑奖愕貏h除頭節(jié)點(diǎn)（對(duì)應(yīng)出隊(duì)操作）和在尾節(jié)點(diǎn)后添加新節(jié)點(diǎn)（對(duì)應(yīng)入隊(duì)操作）。

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

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

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

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

linkedlist_deque.cpp

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    /* 返回?cái)?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ù)組的實(shí)現(xiàn)

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

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

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

array_deque.cpp

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

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

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

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

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

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

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

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

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

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

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

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

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

雙向隊(duì)列應(yīng)用

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

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