共计 1113 个字符，预计需要花费 3 分钟才能阅读完成。
某日二师兄加入 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++！（狗头）