某日二師兄參加XXX科技公司的C++工程師開發崗位第26面： > 面試官：`deque`用過嗎？ > > 二師兄：說實話，很少用，基本沒用過。 > > 面試官：為什麼？ > > 二師兄：因為使用它的場景很少，大部分需要性能、且需要自動擴容的時候使用`vector`，需要隨機插入和刪除的時候可以使用` ...
某日二師兄參加XXX科技公司的C++工程師開發崗位第26面：
面試官：
deque用過嗎？二師兄：說實話，很少用，基本沒用過。
面試官：為什麼？
二師兄：因為使用它的場景很少，大部分需要性能、且需要自動擴容的時候使用
vector，需要隨機插入和刪除的時候可以使用list。面試官：那你知道STL中的
stack是如何實現的嗎？二師兄：預設情況下，
stack使用deque作為其底層容器，但也可以使用vector或list作為底層容器。面試官：你覺得為什麼STL中預設使用
deque作為stack的底層容器嗎？二師兄：額。。（
stack也不需要雙端插入啊，不應該vector更好嗎。。）不是很清楚。。面試官：沒關係。那你知道
deque是如何實現的嗎？二師兄：與
vector記憶體空間連續不同，deque是部分連續的。deque通常維護了一個map（不是std::map），map的每個元素指向一個固定大小的chunk。同時維護了兩個指針，指向頭chunk和尾chunk。在deque的頭部或尾部插入元素時，deque會找到頭部或尾部的指針，並通過指針找到對應的chunk。如果chunk中還有未被元素填充的位置，則將元素填充到數組中，如果此指針指向的chunk已經被元素填滿，則需要重新開闢一塊固定大小的chunk，並將chunk記錄在map中。
面試官：
deque的查找、插入、刪除的時間複雜度是什麼？二師兄：
dqueue查找的時間複雜度是O(N)，插入要分情況，如果是頭插和尾插，時間複雜度為O(1)，如果是中間插入，則是O(N)。刪除元素和插入元素的時間複雜度相同。面試官：好的。面試結束，回去等通知吧。
讓我們來看一下二師兄的表現：
為什麼STL中預設使用
deque作為stack的底層容器嗎？
STL預設選擇deque最為stack的底層容器肯定是有原因的。vector和list同樣可以作為deque的底層容器，讓我們比較一下三個容器的差異：(只考慮頭插和尾插，因為stack不需要隨機插入)
| deque | vector | list | |
|---|---|---|---|
| 插入 | O(1) | O(1) | O(1) |
| 刪除 | O(1) | O(1) | O(1) |
從上表中看到，三種容器的插入和是刪除的時間複雜度相同。
但是如果連續插入時，情況發生變化。vector的capacity被耗盡，元素髮生搬移。
list倒沒有這個顧慮，但是當元素尺寸很小時，list的空間利用率太低。
deque雖然遍歷效率不如vector、隨機插入效率不然list，但stack並不需要這兩種操作，所以deque是stack底層容器的最佳選擇。
今天的面試分享到這裡就結束了，讓我們繼續期待二師兄的表現吧。
關註我，帶你21天“精通”C++！（狗頭）
