前言

本篇主要講解stack與queue的底層，但并不會進行實現，stack的接口
queue的接口 ，關于stack與queue的接口在這里不做講解，因為通過前面的對STL的學習，這些接口都是大同小異的。

容器適配器

我們可以發現，stack與queue的第二個參數都是deque。并且在STL里，stack與queue都沒有被分配到容器那一分類，，而是容器適配器中。

容器適配器是一種設計模式，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。即我們的stack與queue是對deque的接口進行了包裝而已。我們在前期學習數據結構的時候，stack與queue可以通過數組和鏈表進行實現，那么對應到C++里面，是可以通過vector與list進行實現的，那么為什么默認使用deque進行實現呢？

deque

deque其命為雙端隊列，即可以在兩端進行插入刪除切時間復雜度為O(1)，那既然有deque，那么其是否可以取代vector與list呢？當然不行。
先進行補充CPU緩存區的概念：CPU要訪問內存中的數據，需要看這個數據是否在緩沖區中，在的話就叫緩存命中，如果沒有命中那么就需要先加載到緩存再進行訪問緩存。讀取數據根據局部性原理（如果一個數據被訪問，那么它附近的數據也可能很快被訪問。）是不會進行每次只讀一個數據的，內存會先把一部分連續的數據讀入到緩存區中的。

vector的優點:
1.vector支持隨機訪問。
2.CPU高速緩存命中率高。因為vector的數據地址是連續的，所以其連續的數據會在緩存區中，所以其高速緩存命中率高
vector的缺點：
1.頭部與中部插入與刪除數據效率低，因為要挪動數據。
2.擴容后會存在空間浪費的問題
list的優點:
1.任意位置支持O(1)的時間插入刪除
2.不存在擴容，也就不會有浪費空間的問題
list的缺點:
1.不支持下標隨機訪問
2.CPU高速緩存命中率低，因為其內存地址是碎片的。

那么我們的deque是同時兼具兩者的優點的，即支持隨機訪問，CPU高速緩存命中率高，頭插的效率高，也沒有擴容的問題與list相比其空間利用率也更高。但是deque在vector與list的優點上是比不過的，例如vector的隨機訪問的效率是比deque快的。
但是deque的致命缺陷就是其遍歷非常困難，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。
stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。

那么為什么選擇deque作為stack與queue的底層默認容器呢

1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高