deque（雙端隊列）是一種具有高效兩端插入和刪除操作的數據結構，常見于C++標準庫（STL）和其他編程語言中。它的底層實現結合了數組和鏈表的優勢，既支持高效的隨機訪問，又能在兩端快速插入/刪除元素。

底層數據結構原理

deque 的核心思想是分段連續存儲：

• 使用多個固定大小的塊（通常是數組）存儲元素。
• 這些塊通過一個中控器（通常是指針數組）連接，形成邏輯上的連續序列。

關鍵組成部分

1. 中控器（Map）

   • 一個動態分配的數組，每個元素是指向數據塊的指針。
   • 當需要擴展容量時，中控器會重新分配并調整指針。

2. 數據塊（Buffer）

   • 固定大小的連續內存塊（數組），存儲實際元素。
   • 每個塊的大小通常是編譯時確定的（如C++ STL中默認大小為512字節）。

3. 迭代器（Iterator）

   • 智能指針，封裝了當前元素在哪個塊、塊內的偏移量等信息。
   • 通過重載運算符（如 ++, --, []）實現透明的隨機訪問。

操作效率

操作	時間復雜度	說明
兩端插入/刪除	O(1)	僅需調整中控器和塊內指針
隨機訪問	O(1)	通過中控器和塊內偏移量直接計算
中間插入/刪除	O(n)	需要移動元素
內存擴展	O(n)	重新分配中控器并復制指針

與其他容器的對比

容器	隨機訪問	兩端插入/刪除	中間插入/刪除	內存布局
vector	O(1)	尾部O(1)*	O(n)	連續內存
deque	O(1)	O(1)	O(n)	分段連續
list	O(n)	O(1)	O(1)	離散節點

*注：vector 尾部插入在需要擴容時為O(n)。

適用場景

• 需要頻繁在兩端插入/刪除元素（如隊列、棧）。
• 需要隨機訪問，但插入/刪除操作不集中在中間位置。
• 避免 vector 擴容時的元素復制開銷。

C++ STL中的實現細節

以下是STL中 deque 的簡化偽代碼，展示其結構：

template<typename T>
class deque {
private:// 中控器：指針數組，每個元素指向一個數據塊T** map;size_t map_size;  // 中控器大小// 數據塊相關size_t block_size;  // 每個塊的元素數量iterator start;     // 指向第一個元素的迭代器iterator finish;    // 指向最后一個元素的下一個位置的迭代器// 迭代器實現（簡化）struct iterator {T** node;       // 當前塊在map中的位置T* cur;         // 當前元素在塊內的指針T* first;       // 塊的起始位置T* last;        // 塊的結束位置// 重載運算符實現隨機訪問iterator& operator++() { /* ... */ }iterator& operator--() { /* ... */ }T& operator*() { return *cur; }// 其他運算符重載...};
};

總結

deque 通過分段連續存儲的方式，平衡了隨機訪問和兩端操作的效率，適合需要高效雙端插入/刪除且偶爾隨機訪問的場景。其實現復雜度高于 vector 和 list，但在特定場景下能提供更優的性能。

deque和queue的異同

deque（雙端隊列）和queue（隊列）都是常見的數據結構，它們既有相似之處，也有不同點，以下是具體分析：

相同點

• 都是線性數據結構：二者都按照元素的先后順序進行存儲和操作，元素之間存在著明確的線性關系。
• 都支持一定的基本操作：都提供了添加元素和刪除元素的操作，例如在queue中通常有enqueue（入隊）和dequeue（出隊）操作，在deque中也有類似的向隊列兩端添加和刪除元素的操作。

不同點

• 操作限制
  • queue：遵循先進先出（FIFO）原則，元素只能從隊尾插入，從隊頭刪除，就像現實生活中的排隊一樣，先到的人先接受服務。
  • deque：雙端隊列允許在隊列的兩端進行插入和刪除操作，更加靈活，既可以像棧一樣在一端進行插入和刪除，也可以像隊列一樣在一端插入另一端刪除。
• 底層實現
  • queue：通常可以用鏈表或者數組來實現。當使用數組實現時，需要考慮數組的擴容和元素的移動等問題；使用鏈表實現時，雖然插入和刪除操作在表頭和表尾的時間復雜度為 $O(1)$，但可能會有一定的空間開銷用于存儲節點的指針。
  • deque：一般采用動態數組或者鏈表來實現。以動態數組實現為例，它可以通過擴展數組的方式來適應元素的增加，并且能夠高效地在兩端進行插入和刪除操作，通常通過維護頭指針和尾指針來確定隊列的邊界。
• 應用場景
  • queue：常用于需要按照順序處理任務的場景，如消息隊列、任務調度等。例如，在一個多線程的應用程序中，任務可以被放入一個隊列中，然后工作線程按照任務進入隊列的順序依次取出并執行。
  • deque：適用于需要在序列兩端進行頻繁插入和刪除操作的場景。例如，在實現一個文本編輯器的撤銷和重做功能時，可以使用deque來存儲操作歷史，方便在兩端進行操作的添加和刪除。

在C++ 等編程語言中，std::queue和std::deque是標準模板庫（STL）中的容器適配器。std::queue默認基于std::deque實現，當然也可以指定其他容器作為其底層實現，而std::deque是一個獨立的容器，具有雙端操作的功能。