stack的介紹（可以想象成棧）

1.stack是一種容器適配器，專門用在具有后進先出操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與提取操作

2.stack是作為容器適配器被實現的，容器適配器即是對特點類封裝作為其底層的容器，并提供一組特定的成員函數來訪問其元素，將特定類作為其底層，元素特定容器的尾部（即棧頂）被壓入和彈出

3.stack的底層容器可以是任何標準的容器類模板或者是一些其他特定的容器類，這些容器類應該支持以下操作：

empty() /? back? / push_back / pop_back

4.標準容器vector/list/deque均符合這些需求，默認情況下，如果沒有stack指定特定的底層容器，就使用deque（等會會介紹）

stack的使用

它是一個適配器，就是通過別的容器轉換過來的，只是提供一些特定的接口，讓其具有棧的特性

特性：LIFO（last-in first-out，后進先出）

?

可以看到默認使用的模板容器類是deque

?

constructor

stack<int> s;//構造一個空的對象

如果你想指定你的stack使用的底層容器可以stack<int,vector<int>> s;

三種構造方式：1.構造空的stack對象

? ? ? ? ? ? ? ? ? ? ? ? ?2.使用一個模板容器構造，例如你已經構造vector v1對象了，傳參可以傳v1

? ? ? ? ? ? ? ? ? ? ? ? ?3.拷貝構造函數，傳一個stack對象

其他重要函數接口

empty()：判斷是否為空

size()：返回棧的元素的個數（返回棧的大小）

top()：取棧頂的元素

push()：將元素val壓入stack中

pop()：將棧頂的元素val刪除

swap():交換兩個棧

總結

1.棧是沒有迭代器的，因為棧的特性是先進后出，不能隨便訪問，所以不支持迭代器

2.如何遍歷？先判斷為不為空，不為就取棧頂的數據，取完之后pop就行

3.為什么沒有析構函數？因為它底層是別的容器，當stack出了作用域自動銷毀時會調底層容器的析構函數

queue的介紹（想象成隊列）：

1.隊列是一種容器適配器，專門用于在FIFO（先進先出）中操作，其中從容器的一段插入元素，另一端提取元素

2.隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素，元素從隊尾入隊列，從對頭出隊列

3.底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類，該底層容器至少要滿足以下操作

empty/? ?size? /? front / back /push_back /? pop_front

4.deque/list都滿足這些要求，如果沒有指定，默認使用deque

queue的使用

隊列就是一種容器適配器，是基于一些容器實現的特定的接口以滿足先進先出的特性

默認使用deque容器?

幾乎和棧沒差別，構造函數，還有一些其他函數接口也幾乎一樣

區別在于，stack使用top取棧頂數據

queue可以取隊頭也可以取隊尾的數據?

front隊頭，back隊尾，top棧頂

而且注意這些都是返回引用，也就是你可以修改

總結：

隊列也沒有實現迭代器，因為不能支持隨機訪問，否則就保持不了隊列的先進先出的特性

deque的介紹

deque:雙端隊列，與queue沒關系，不要聯想到一起，它是一種容器，沒有隊列先進先出的特性

STL標準庫中stack和queue的底層結構：

雖然stack和queue都可以存放元素，但STL并沒有將其劃入容器的行列，而是將其稱為容器適配器，這是因為stack和queue只是對其他容器的的接口進行了包裝，STL中的stack和queue默認使用deque

deque（雙端隊列）：是一種雙開口的“連續”空間的數據結構，雙開口的含義：可以在頭尾雙端進行插入和刪除操作，且時間復雜度為O(1)，與vector相比，頭插效率高，不需要挪動數據；與list相比，空間利用率比較高

duque的使用?

?可以看到它支持頭插尾插頭刪尾刪?

?可以看到支持迭代器

支持隨機訪問?

關于deque的使用可以去官網看詳細解釋，這里只要學明白為什么stack和queue底層用deque

deque的原理

duque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似與一個動態的二維數組，其底層結構如下圖所示：

簡單來說，deque底層是由一系列固定大小的連續存儲塊組成，這些存儲塊叫緩沖區（buffer）

此外，還有一個中控器（通常是一個數組map）存儲著指向buffer的指針來管理緩沖區

那它怎么支持隨機訪問？？？，這就落在了deque的迭代器身上了，簡單來說就是用中控器中的結點，然后用來構造迭代器類型，迭代器里面又有cur first last node等管理，每遍歷一個點，cur就往后走，直到last它就遍歷結束這一塊buffer，遍歷完之后node就++就走到下一個結點，然后依次循環下去就是連續遍歷

deque的缺陷

與vector相比，deque的優勢是：頭部插入和刪除時，不需要搬移元素，（我們只要在前面多加一個結點，這個結點新開一些buffer，就能解決頭插，頭刪時只要指針指向的位置變就可以）效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是比vector高的，這些可以歸結與一個原因，就是vector是連續的物理空間，deque不是連續的，它是通過一個中控器去管理，連續的不夠大了就需要重新找一塊連續的，而deque不需要

與list相比，deque底層是類似連續的空間，空間利用率高，不需要存儲額外的字段，你list每個結點還要存前一個結點和后一個結點的指針

但是deque有一個致命缺陷：不適合遍歷，在遍歷時，deque的迭代器要頻繁的檢查是否移動到某段buffer的邊界，導致效率低下，而序列式場景中，可能需要經常的遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，這也就是為什么我們沒有重點學習deque的接口原因，deque的應用并不多，目前我們能看到的就是stack和queue底層使用deque

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

1.stack和queue不需要遍歷（因此其沒有迭代器），只需要在固定的一端或者兩端進行操作，那deque遍歷效率低就在stack和queue這沒啥影響了

2.在stack中元素增長時，deque比vector效率高（擴容時不需要搬移大量數據），queue中的元素增長時，deque不僅效率高，而且內存使用率也高，也就是無論頭插還是尾插，頭刪還是尾刪，deque的效率也不比list和vector低多少，綜合而言，結合了deque的優點，避開了其缺陷

stack和list的模擬實現：

June: 這里包含我的c++和Linux及數據結構https://gitee.com/taifanshu/day2.git已經上傳gitee，有需要可以自行拿取，代碼有問題可以私聊問

?