雙端隊列

雙端隊列（deque，全名double-ended queue）是一個限定插入和刪除操作的數據結構，具有隊列和棧的性質。雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進行。

雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。這兩端分別稱做端點1和端點2。也可像棧一樣，可以用一個鐵道轉軌網路來比喻雙端隊列。

這裡，只討論deque類的插入和刪除操作。

雙端隊列不僅提供了push_back成員函數，還提供了push_front成員函數，從而可以在序列的前後兩端進行插入操作。

對於雙端隊列，在序列的兩端插入元素的時間複雜度均為常數，在中間插入元素的時間複雜度與插入點到最近序列端點的距離成正比。並且，對於雙端隊列的插入操作(包括在雙端插入和中間插入)，將會使所有的迭代器失效，只能採用下標操作。

雙端隊列不僅提供了pop_back成員函數，還提供了pop_front成員函數，從而可以在序列的前後兩端進行刪除操作。在中間的刪除操作將會使所有迭代器失效；而在兩端的刪除操作，僅當刪除位置就是迭代器所指向位置時會使迭代器失效。

輸出受限的雙端隊列：允許在一端進行插入和刪除，但在另一端只允許插入的雙端隊列稱為輸出受限的雙端隊列，如圖3-11所示。

輸入受限的雙端隊列：允許在一端進行插入和刪除，但在另一端只允許刪除的雙端隊列稱為輸入受限的雙端隊列，如圖3-12所示。而如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則該雙端隊列就蛻變為兩個棧底相鄰接的棧了。

正是由於雙端隊列在兩端插入、刪除操作的便利性，並且它又具有隨機訪問迭代器，其應用十分廣泛。STL的適配器，如堆棧、隊列和優先隊列都可以採用雙端隊列來實現，其中前兩者默認採用deque來保存自己的元素。