雙端佇列是指允許兩端都可以進行入隊和出隊操作的佇列，其元素的邏輯結構仍是線性結構。將佇列的兩端分別稱為前端和後端，兩端都可以入隊和出隊。
基本介紹
- 中文名：雙端佇列
- 外文名：double-ended queue
- 性質：一種數據結構
- 最佳化類型：deque
- 套用：數據編程
基本簡介,基本操作,插入,刪除,分類,套用,
基本簡介
雙端佇列是限定插入和刪除操作在表的兩端進行的線性表。這兩端分別稱做端點1和端點2。也可像棧一樣，可以用一個鐵道轉軌網路來比喻雙端佇列。
基本操作
這裡，只討論deque類的插入和刪除操作。
插入
雙端佇列不僅提供了push_back成員函式，還提供了push_front成員函式，從而可以在序列的前後兩端進行插入操作。
對於雙端佇列，在序列的兩端插入元素的時間複雜度均為常數，在中間插入元素的時間複雜度與插入點到最近序列端點的距離成正比。並且，對於雙端佇列的插入操作(包括在雙端插入和中間插入)，將會使所有的疊代器失效，只能採用下標操作。
刪除
雙端佇列不僅提供了pop_back成員函式，還提供了pop_front成員函式，從而可以在序列的前後兩端進行刪除操作。在中間的刪除操作將會使所有疊代器失效；而在兩端的刪除操作，僅當刪除位置就是疊代器所指向位置時會使疊代器失效。
分類
輸出受限的雙端佇列：允許在一端進行插入和刪除，但在另一端只允許插入的雙端佇列稱為輸出受限的雙端佇列，如圖3-11所示。
輸出受限的雙端佇列輸入受限的雙端佇列：允許在一端進行插入和刪除，但在另一端只允許刪除的雙端佇列稱為輸入受限的雙端佇列，如圖3-12所示。而如果限定雙端佇列從某個端點插入的元素只能從該端點刪除，則該雙端佇列就蛻變為兩個棧底相鄰接的棧了。
輸入受限的雙端佇列套用
正是由於雙端佇列在兩端插入、刪除操作的便利性，並且它又具有隨機訪問疊代器，其套用十分廣泛。STL的適配器，如堆疊、佇列和優先佇列都可以採用雙端佇列來實現，其中前兩者默認採用deque來保存自己的元素。
