按照本來的順序, 應該是寫完佇列與堆疊之後才會開始雙向佇列. 但是, 雙向佇列 (Deque) 是以容器的形式存在於 STL 中的, 堆疊與佇列都是以容器配接器的形式存在於 STL 中的. 而這一次的重構, 也以 STL 的思想為基準, 所以我們首先要說的就是雙向佇列

這次的介紹與之前完全不同, 之前寫的雙向佇列它相當於一個 Container Adapter, 即容器配接器, 而且只是以 int 型態存在. 我們這次要維護的雙向佇列它是一個完完全全雙向開口的容器

我們還是要對雙向佇列的基本進行介紹. 儘管雙向佇列名稱中存在佇列, 但是它實際上並不是佇列, 但是它可以通過容器配接器來演變成佇列, 也可以通過容器配接器演變為堆疊. 所以, 它同時具有佇列和堆疊的所有性質, 除此之外, 它還有一些自己的性質, 例如可以在前面進行插入元素的操作

我們使用一張比較簡單的 SVG 圖像來表示雙向佇列 :

所以, 根據圖像的描述, 雙向佇列既支援在最前端進行插入以及彈出的操作外, 最後端也支援一樣的操作. 因此, 它具有佇列和堆疊的性質

我們這次的重點並不是在資料結構本身, 而是在於雙向佇列本身. 所以, 資料結構部分, 也只是簡單地介紹而已. 因為從資料結構上來說, 雙向佇列並不算複雜

但是, 我們所要實現的雙向佇列, 並非上面的線性結構的雙向佇列. 因為實際在 C++ 中, 線性的雙向佇列是很難做到前端增長的 (但是不是不可以做到, 在接下來的文章中, 我們同樣會嘗試實現一個相對簡單的線性結構的雙向佇列). 我們需要通過複雜的結構來保持雙向佇列前後雙開的這種性質, 因此 Deque 會比 Vector 複雜的多. 在日常的程式設計中, 基本上 C++ 大師們也會告訴大家, 在能使用 Vector 時, 儘量使用 Vector 而不是 Deque. 原因就是在此

首先, 我們以一個 SVG 圖像示例來展示一個正在被使用到一定程度的雙向佇列 :

在 Deque 的結構中, 我們看到了一個叫做 Buffer Manager 的中控器, Deque 中的所有 Buffer 都由其控制. 因此, 控制 Deque 雙向開口性質的也是它. 當每次頂部或者底部任意一個 Buffer 遇滿或者不夠的時候, 中控器就會在特定的位置自動增加一些 Buffer (增加的數量由具體的需求決定)

因此, 我們可以總結, Deque 其實並不是連續線性的結構, 而是一個看起來像線性的資料結構, 但是實際上是一個片段線性的結構. 而且 Deque 為了維護 '看起來', Deque 要耗費的精力要比 Vector 大得多

為了具體講解 Deque, 我不得不提前介紹 Deque 的疊代器. Deque 的疊代器是一個特殊的疊代器, 它不僅僅是一個對指標進行封裝的智慧指標類別. 從 STL 的 std::deque 中, 我們可以得知, Deque 的疊代器應該是一個隨機訪問疊代器. 因此, 我們自創的 Deque 的疊代器也必須支援隨機訪問. 但是 Deque 的結構並不是線性的, 所以 Deque 的疊代器需要有在 Buffer 之間跳躍的能力. 它必須知道, 自己跳躍之後是否還處於現在這個 Buffer 內, 還是已經跳躍至別的 Buffer 了. 為了實現跳躍, Deque 的疊代器類別內必須可以部分掌控中控器. 它至少可以知道目前自己是否處於 Buffer 的邊緣, 又或者下一個 Buffer 的記憶體位址是什麼. 因此, Deque 的疊代器類別內可能會有一個二級指標, 指向中控器的其中一個 Buffer 區域. 你可以直接在疊代器內設定其範圍, 也可以通過 Buffer 對應的類別獲取到範圍

這是其中一種設計模式, 寫成 C++ 程式碼類似於 :

template <typename T, size_t BufferSize>
class deque_iterator {
private:
    T *ptr;
    T **buffer;
    //...
};

在這種模式中, Buffer 掌控著自己的三個指標, Deque 的疊代器除了需要具體的位置之外, 還需要緩衝區的記憶體位址, 這是因為在條約時, 疊代器指向的位置需要從緩衝區中得知 :

template <typename T, size_t BufferSize>
class deque_iterator {
private:
    T *ptr;
    T **buffer;
public:
    deque_iterator &operator++() & noexcept {
        if(++this->ptr == *this->buffer + static_cast<ptrdiff_t>(BufferSize)) {     //若疊代器到達目前緩衝區的尾後位置
            ++this->buffer;     //切換為下一個緩衝區
            this->ptr = *this->buffer;      //將疊代器移動到下一個緩衝區的頭部
        }
        return *this;
    }
};

在這個設計模式中, 真正掌控緩衝區的是 Deque 本身而不是 Deque 的疊代器

這是另外一種設計模式. 此時, Buffer 將只是指向區域的第一個記憶體位址, 而掌控 Buffer 的是 Deque 的疊代器. 一般來說不建議使用這種模式, 因為所有記憶體應該有 Deque 本身來控制, 而不是由一個疊代器進行控制

至此, 你可能有一個疑問 : 其它資料結構, 我們都沒有具體去介紹疊代器的架構, 而 Deque 為什麼要介紹呢?

這是因為 Deque 中有兩個成員變數, 一個是指向第一個元素, 一個是指向尾後元素, 這兩個屬性成員如果只是普通的指標, 那麼將會使 Deque 的程式碼變得非常複雜. 因此, 我們直接使用已經架構好的疊代器來完成這樣的工作就可以了

於是你會發現, 我們已經完成了對 Deque 的基本架構, 接下來就是實作了

對於實作部分, 我還是主張自己完成, 因為 Deque 只有你寫過了, 你才會清楚地知道它的實作的難度非常高, 你要方方面面地考慮. 稍不小心, 就會產生記憶體方面的錯誤

我將特別介紹 Deque 的元素操作部分, 也就是插入與彈出

Deque 的元素插入 (insertpush)

對於元素的插入來說, 我們需要考慮的是目前的 Buffer 總數是否足夠

每一次, 我們都應當對插入的元素數量進行判斷, 如果 Buffer 總署已經足夠應付了, 那麼直接插入就可以了; 否則的話, 可能就需要申請一個新的 Buffer 來完成插入了

當然, 你也可以提前備好一些區域. 例如, 目前有 4 個 Buffer, 但是 Deque 中的尾部疊代器已經處於第四個 Buffer 的尾部位置了. 此時, 即使沒有新的插入需求, 你也可以提前配置好 Buffer. 這樣做的好處就是每一次插入的數量只要不超過一個 Buffer 的大小, 那麼就可以直接執行插入, 從而無需考慮是否需要新增 Buffer 來應付新的需求; 但是, 這樣同樣也有一個壞處, 就是如果最後一次插入完, 配置好新的 Buffer, 但是新的 Buffer 直到程式結束都用不到, 這就顯得有點浪費了

Deque 的元素彈出 (erasepop)

對於元素的彈出, 我們考慮的方面就不如插入那麼多了, 因此彈出相對於插入來說, 是稍微簡單的. 我們只需要每一次都考慮彈出之後, 是否存在一個甚至一個以上的 Buffer 是完全空著的. 如果存在的話, 你需要考慮是否將其釋放, 從而達到節省記憶體的目的 (並不是每一台電腦的記憶體都是那麼足夠). 如果讓我選擇的話, 我肯定會釋放掉它, 因為我以記憶體優先為原則, 使用一點時間來換取記憶體

Deque 的指示疊代器

在 C++ 中, 存在尾後疊代器這樣的實體. 通常來說, 尾後疊代器的記憶體都是沒有被使用或者沒有被配置的. 當一個範圍內的遍歷疊代器遇到尾後疊代器的時候, 就代表著遍歷結束, 並且不對尾後疊代器中的元素進行遍歷, 因為這可能會造成錯誤. 因此, 我們不應該讓 Deque 的疊代器指向一個 Buffer 的尾後疊代器

當然, 這只是我的一個建議, 具體的實作方式取決於你

資料結構 Deque : GitHub 點擊直達

資料結構 Deque 使用說明 : GitHub 點擊直達