簡介：雙端隊列(deque)

1.概述

雙端隊列：是一種順序表和順序表的結合數據結構，不是隊列。
它提供順序表的[]下標訪問和鏈表的中間頭部的較高效率插入刪除操作。

2.特點

順序表的優缺點：
優點：支持下標隨機訪問
缺點：頭部或者中間插入刪除效率低 + 擴容有消耗

鏈表的優缺點：
優點：任意位置插入刪除效率都不錯
缺點：不支持下表隨機訪問

雙端隊列優缺點：順序表鏈表都沾點邊，但都不夠極致。
優點：

• 既有著順序表支持下表隨機訪問的功能，又有鏈表任意位置插入刪除效率都還可以。
• 而且頭插尾插效率很好。

缺點：

• 雙端隊列支持的下標隨機訪問性能上不如順序表，雙端隊列的任意位置插入刪除效率不如鏈表

3.底層原理

簡化抽象圖：

迭代器圖：

因為deque優點是頭尾插入刪除效率很好，剛好與棧和隊列相一致，因而常被用做棧和隊列的默認容器。

---

EOF