摘要訊息 : 向量頭尾插入操作的時間複雜度並不能真正達到常數時間, 而通過向量改進的雙向佇列卻可以接近常數時間.

目錄 隱藏
0. 前言
1. 定義
2. 空間佈局
3. 疊代器
3.1 移動一個位置
3.2 移動 k 個位置
3.3 實作
4. 偽連續結構
5. 插入, 移除, 搜尋, 字典比較和旋轉
6. 對比向量
7. 實作

0. 前言

在程式設計中, 向量 (《【資料結構】向量 (順序表)》) 一般採用動態陣列來表示. 在向量的頭部位置插入元素是需要將全部向後移動元素的, 插入的時間複雜度為 \Theta(n). 在向量的尾部插入元素是平攤 \Theta(1) 的, 但是在向量的空間足夠的情況下, 尾部插入元素的時間複雜度就是 \Theta(1). 對於前項連結串列 (《【資料結構】前向連結串列》), 在其頭部插入元素的時間複雜度是 \Theta(1) 的, 而在其尾部插入元素需要尋訪全部結點, 這樣就導致尾部插入元素的時間複雜度為 \Theta(n). 在連結串列 (《【資料結構】連結串列》) 的頭部和尾部插入元素雖然都是 \Theta(1) 的, 但是連結串列一個結點維護了兩個指向型標記, 過於消耗空間. 另外, 由於連結串列中結點不一定連續, 從而導致了連結串列是搜尋不友好的.

我們希望有一種資料結構, 在它的頭部和尾部插入元素的時間複雜度都是 \Theta(1). 另外, 我們還希望它可以像向量一樣儘量節省空間, 並且看起來儘量連續.

更新紀錄 :

  • 2022 年 4 月 3 日進行第一次更新和修正.

1. 定義

為了得到期望的資料結構, 我們首先考慮空間問題. 前向連結串列和連結串列這兩個資料結構除了需要維護其中的元素之外, 還需要至少維護一個指向型標記, 那麼 n 個元素就至少有 n 個指向型標記. 雖然連結串列的插入操作很快, 但是它消耗了太多的空間, 我們不考慮改進這種結構. 那麼剩下的選擇就是改進向量.

在 C/C++ 中, 內建型別的建構, 複製, 移動和解構操作都是極其快速的, 為了利用這個特點 (我們將在第 2 節講述這個特點帶來的好處), 我們將向量進行分組. 假設每個分組內至多有 m 個元素, 並且記 \widehat {\infty} 是佔位標記. 那麼對於向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 我們可以將其分組後記為 \displaystyle {\begin {aligned} \boldsymbol {\alpha} = \Bigg \{ &\underbrace {(\widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty}, \alpha_{1}, \alpha_{2}, ..., \alpha_{i})}_{m \text { 個}}, (\alpha_{i + 1}, \alpha_{i + 2}, ..., \alpha_{i + m}), \\ &(\alpha_{i + m + 1}, \alpha_{i + m + 2}, ..., \alpha_{i + 2m}), ..., \underbrace {(\alpha_{i + km + 1}, \alpha_{i + km + 2}, ..., \alpha_{n}, \widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty})}_{m \text { 個}} \Bigg \}. \end {aligned}} 其中, k 為正整數. 我們可以發現, 比較特殊的是第一個分組 (\widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty}, \alpha_{1}, \alpha_{2}, ..., \alpha_{i}) 和最後一個分組 (\alpha_{i + km + 1}, \alpha_{i + km + 2}, ..., \alpha_{n}, \widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty}). 第一個分組最開始的元素並不是 \alpha_{1}, 而是佔位標記; 最後一個分組在 \alpha_{n} 之後的位置也不是空的, 而是被佔位標記所佔位.

定義 1. 我們稱向量 \boldsymbol {\alpha}_{0} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 的擴展 \displaystyle {\begin {aligned} \boldsymbol {\alpha} = \Bigg \{ &\underbrace {(\widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty}, \alpha_{1}, \alpha_{2}, ..., \alpha_{i})}_{m \text { 個}}, (\alpha_{i + 1}, \alpha_{i + 2}, ..., \alpha_{i + m}), \\ &(\alpha_{i + m + 1}, \alpha_{i + m + 2}, ..., \alpha_{i + 2m}), ..., \underbrace {(\alpha_{i + km + 1}, \alpha_{i + km + 2}, ..., \alpha_{n}, \widehat {\infty}, \widehat {\infty}, ..., \widehat {\infty})}_{m \text { 個}} \Bigg \}. \end {aligned}} 為雙向佇列或者雙端佇列 (dequeue, 簡寫為 deque, 有時也叫它迴圈佇列).

由於第一分組和最後一個分組的特殊性, 我們可以以 \Theta(1) 的時間複雜度在前後插入元素, 這便是雙向佇列所具有的特性.

2. 空間佈局

理解雙向佇列在記憶體或者其它空間中的佈局是很重要的. 一般來說, 如果雙向佇列有 g 個分組, 我們可以選擇配置 g \times m 個連續的空間, 然後在前面和後面預留一些位置 :

Figure 1. 連續佈局

在 Figure 1 中, 灰色部分代表著預留出來的空間, 紅色部分代表被已經被元素佔有的空間. 這種解決方案非常直觀, 但是在程式設計中, 一旦前面預留出來的空間被填滿, 再想在前面繼續插入元素的時候, 就會面臨著雙向佇列退化為向量的問題. 此時, 在頭部插入元素的時間複雜度就不再是 \Theta(1), 而是 \Theta(n).

既然雙向佇列進行了分組, 那麼我們就嘗試配置 g 個分組內連續但是分組外可能不連續的空間 :

Figure 2. 分組內連續分組外不連續佈局

這樣的話, 一旦頭部預留的空間被使用完了, 我們只需要再配置一個分組, 把它再放到頭部即可. 這樣, 就不會出現頭部預留的位置滿了, 需要把元素向後移動的情況. 同樣地, 由於分組外的空間並不是連續的, 如果尾部預留的位置也被佔滿了, 那麼我們只需要配置一個新的分組放到最後即可. 總體來說, 頭部和尾部插入元素的時間複雜度維持在了 \Theta(1).

但是分組外不連續這樣的佈局也帶來了一個問題, 當我們需要在不同分組上尋訪元素的時候, 如何在分組之前進行切換? 由於分組外不連續, 當我們停留在第一個分組的最後一個位置, 再向後尋訪一個元素, 現在所停留的位置很可能不屬於雙向佇列 :

Figure 3. 停留在了不屬於雙向佇列的位置

為了避免 Figure 3 中的情況發生, 我們需要記錄每一個分組開始的位置. 因此, 若有 g 個分組, 那麼我們就需要 g 個指向型標記, 這些標記會指向每一個分組的頭部. 在 C/C++ 中, 這個指向型標記就是內建的指標. 那麼也就是說, 我們需要配置一個指標陣列, 陣列中的每一個指標都指向某個分組頭部 :

Figure 4. 雙向佇列空間佈局

現在不妨假設雙向佇列頭部的空間都被佔有了, 沒有空間可以插入新的元素了, 但是我們還需要向頭部插入一個元素, 具體的做法是 (在尾部插入元素也是類似的過程) :

  1. 配置一個具有 g + 1 個指向型標記的新陣列;
  2. 空出陣列第一個指向型標記, 把剩下的 g 個指向型標記由舊的陣列按順序複製過來;
  3. 配置一個新的分組, 並將新陣列的第一個指向型標記指向這個分組頭部;
  4. 在第一個分組尾部插入元素.

那麼現在, 我們並不需要把雙向佇列中的所有元素向後移動一個位置, 只是簡單地複製一下指向型標記陣列, 便可以完成向頭部插入一個新的元素. 我們在第 1 節中的第二段便說過了, 在 C/C++ 中, 對內建型別的複製操作是非常快速的 (特別是在 C++ 中對比起自定型別), 即使把這個複製操作也計入時間複雜度, 那麼在需要配置新分組的時候, 插入的時間複雜度為 \Theta(g). 比起 \Theta(n) 的時間複雜度, \Theta(g) 顯然更快.

為什麼可以把指向型標記陣列複製的操作忽略掉, 而視雙向佇列頭部和尾部插入元素的操作為 \Theta(1) 的呢? 這是因為在 C++ 中, 某些自定型別的建構, 複製甚至移動和指標的複製比起來, 指標的複製可能快幾倍甚至幾十倍. 儘管指向型標記的數量和元素數量是相關的, 然而把上面這個因素考慮進來的話, 我們完全可以忽略掉指向型標記複製所需要的時間. 當然, 如果雙向佇列中的元素型別也是和指標類似的內建型別, 而不是複雜的用戶自訂型別的話, 這個時候, 一旦需要調整指向型標記陣列, 那麼時間複雜度就是 \Theta(g). 但是總體來說, 在雙向佇列的頭部和尾部插入元素的時間複雜度和向量尾部插入元素類似, 是在 g 個分組下平攤 \Theta(1) 的, 可以視為 \Theta(1).

3. 疊代器

現在要解決的另外一個問題就是對於分組的結構, 如何順利地進行元素的尋訪. 在程式設計中, 我們通常通過陣列注標, 也就是 array[i] 的形式來存取陣列中的元素. 但是由於雙向佇列結構的特殊性, 這個方案沒有辦法直接用在雙向佇列上. 我們知道, 有了指向型標記陣列之後, 我們可以通過它在分組之間進行切換.

3.1 移動一個位置

設目前所在的位置是第 i 個分組的第 j 個位置. 其中, 1 \leq i \leq g 且 1 \leq j \leq m. 如果我們要向後移動一個位置 :

  • 如果 j = m, 那麼需要切換到第 i + 1 個分組的第一個位置;
  • 如果 j \neq m, 那麼只需要向後移動一個位置, 即第 j + 1 個位置即可.

如果我們要向前移動一個位置 :

  • 如果 j = 1, 則切換到第 i - 1 個分組的最後一個位置;
  • 如果 j \neq 1, 則後退到第 j - 1 個位置即可.

3.2 移動 k 個位置

設目前所在的位置是第 i 個分組的第 j 個位置. 其中, 1 \leq i \leq g 且 1 \leq j \leq m. 如果我們要向後移動 k 個位置 (k > 0) :

  • 如果 m - j \leq k, 那麼向後移動 k 個位置就可以了, 即移動到當前分組的第 j + k 個位置;
  • 如果 m - j > k, 那麼我們要切換到第 i + \left \lfloor \frac {k}{m} \right \rfloor 個分組的第 k \mod m 個位置.

如果我們要向前移動 k 個位置 (k > 0) :

  • 如果 k < j, 那麼向前後退 k 個位置就可以了, 即移動到當前分組的第 j - k 個位置;
  • 如果 k \geq j, 那麼我們要切換到第 i - \left \lfloor \frac {k}{m} \right \rfloor 個分組的第 m - k \mod m 個位置.

3.3 實作

如果在每次插入, 移除和尋訪的時候, 都採取上面這樣的操作, 那麼程式碼將會非常複雜. 為了簡化程式碼, 我們將移動的操作委託給疊代器. 通過第 3.1 節和第 3.2 節, 我們知道疊代器除了儲存當前所在的位置之外, 還儲存了當前所在的分組. 接下來, 我們採用 C++ 實作疊代器 :

template <typename T, int GroupSize>
class deque_iterator {
    static_assert(GroupSize > 0, "The size of group must greater than zero!");
private:
    T *position;
    T **group;
public:
    deque_iterator &operator++() noexcept {
        if(++this->position == *this->group + GroupSize) {
            this->position = *++this->group;
        }
        return *this;
    }
    deque_iterator &operator+=(int k) & noexcept {
        const auto offset {k + (this->position - *this->group)};        // the distance from the current position to the head position
        if(offset >= 0 and offset < GroupSize) {
            this->position += k;
        }else {
            const auto node_offset {
                offset > 0 ? offset / GroupSize : (-offset - 1) / GroupSize - 1};
            this->group += node_offset;
            this->position = *this->group + (offset - node_offset * GroupSize);
        }
        return *this;
    }
    // ...
};

在 Code 1 中, 我們主要實作了和移動有關的運算子, 剩餘部分大家可以自行完成. 這裡需要注意的是, 對於 += 運算子, 我們的實作支援 k < 0, 這個時候就會被解釋為向後退. 那麼 -= 運算子的工作就可以委託給 += 運算子, 引數是 -k.

4. 偽連續結構

在程式設計中, 不論是固定大小的陣列還是大小動態的陣列, 它們屬於連續結構的資料結構. 而根據雙向佇列在空間中的結構圖 Figure 4, 雙向佇列必定不是一個連續結構, 因為其內部元素的排列在空間中並不是連續的. 在 C++ 中, 我們一般配置一個動態陣列通常會使用一個指標來標記陣列頭部, 一個指標來標記陣列尾部 (或者使用一個值來表示陣列大小), 還有一個指標用來標記陣列的用量 (或者使用一個值來表示陣列的用量) :

template <typename T>
class vector {
private:
    T *begin;
    T *end;
    T *first_empty;
    // ...
};
/*template <typename T>
class vector {
private:
    T *begin;
    int size;
    int used_size;
    // ...
};*/

因為疊代器包攬了所有移動操作, 因此把一切委託給疊代器的話就可以讓雙向佇列看起來是一個連續結構 :

template <typename T>
class deque {
private:
    T **directional_subscript;
    int directional_subscript_size;
    deque_iterator first;
    deque_iterator last;        // int used_size; last = first + used_size
    // ...
};

5. 插入, 移除, 搜尋, 字典比較和旋轉

由於我們已經讓雙向佇列看起來像一個向量, 也就是偽線性結構, 所以所有的操作都是和向量類似的. 這一些演算法我們在這裡就不再累贅, 大家可以參考《【資料結構】向量 (順序表)》.

6. 對比向量

在空間佈局中的不同, 我們在第 2 節已經說過了, 此處不再累贅. 我們主要比較向量和雙向佇列的插入, 移除, 搜尋, 字典比較和旋轉操作. 由於向量在空間中的佈局是連續的, 因此在尋訪元素的時候, 它的速度比雙向佇列要快一些, 因為它並不需要在分組之間進行切換. 因此在這些演算法上, 一定是向量比雙向佇列要快一些. 然而我們之前也說過, 雙向佇列的優點是不論在頭部插入還是在尾部插入, 都可以視為 \Theta(1) 的. 而向量頭部插入的時間複雜度是 \Theta(n), 在尾部插入的時間複雜度只能達到平攤 \Theta(1), 並不能真正視為 \Theta(1), 特別是向量內部儲存的元素複製, 移動和解構非常複雜的時候.

綜上所述, 如果我們的需求是經常在頭部和尾部插入元素, 極少在中間插入或者移除元素, 那麼我們應該優先選用雙向佇列; 否則, 我們應該優先選擇向量.

7. 實作

我自己用 C++ 實作了雙向佇列 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/deque.hpp, 大家可以參考後自行實作.