? ?在C++標準庫中，stack是一種容器適配器，它以后進先出的方式組織數據，其刪除只能從容器的棧頂進行元素的插入與取出操作。

stack的使用

stack的構造函數

stack的成員函數

empty：判斷棧是否為空
back：返回當前棧中元素的數量（大小）

top:獲取棧頂元素的引用
push:將一個新的元素壓入棧中

emplace:在棧頂處構造一個新的元素，使用傳遞的參數來進行構造
pop:將棧頂元素彈出（刪除）

swap:用于交換兩個棧的內容，使得兩個棧中的元素互換

容器適配器

? ? 容器適配器（Container Adapters）是 C++ 標準庫提供的一種數據結構，它們基于現有的容器類型，提供了特定的接口和功能，以便更方便地實現某些特定的數據結構和算法。容器適配器本質上是對底層容器的封裝，提供了不同的數據訪問方式，使它們適用于特定的用途。

標準庫中提供了三種常用的容器適配器：

stack：棧適配器，基于底層容器提供了棧數據結構的操作，如壓入（push）、彈出（pop）、查看棧頂元素等。默認底層容器是 std::deque，但也可以使用其他支持 back() 和 push_back() 操作的容器。
queue：隊列適配器，基于底層容器提供了隊列數據結構的操作，如入隊（push）、出隊（pop）、查看隊首元素等。默認底層容器是 std::deque，但也可以使用其他支持 back() 和 push_back() 操作的容器。
priority_queue：優先隊列適配器，基于底層容器提供了優先隊列數據結構的操作，支持在插入元素時根據優先級進行排序。默認底層容器是 std::vector，但也可以使用其他支持隨機訪問和插入操作的容器。

雙端隊列

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

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

雙端隊列底層是一段假想的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假想，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜，如下圖所示：

雙端隊列的缺陷

與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。

與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。

stack的模擬實現

//適配器模式/配接器

template<class T,class Container=vector<T>>
class stack {
public:
?? ?void push(const T& x) {
?? ??? ?_con.push_back(x);
?? ?}
?? ?void pop() {
?? ??? ?_con.pop_back();
?? ?}
?? ?const T& top() {
?? ??? ?return _con.back();
?? ?}
?? ?size_t size() {
?? ??? ?return _con.size();
?? ?}
?? ?bool empty() {
?? ??? ?return _con.empty();
?? ?}
private:
?? ?//vector<T> _v;
?? ?Container _con;
};
void test_stack() {
?? ?//stack<int, vector<int>> st;
?? ?//stack<int, list<int>> st;
?? ?stack<int> st;
?? ?st.push(1);
?? ?st.push(2);
?? ?st.push(3);
?? ?st.push(4);
?? ?while (!st.empty()) {
?? ??? ?cout << st.top() << " ";
?? ??? ?st.pop();
?? ?}
?? ?cout << endl;
}

成員函數的模擬實現

push(const T& x)：將傳入的元素值 x 添加到底層容器的末尾，實現了入棧操作。
pop()：從底層容器的末尾刪除一個元素，實現了出棧操作。
T& top() 和 const T& top() const：分別返回底層容器的末尾元素的引用（允許修改）和常量引用（只讀），實現了查看棧頂元素操作。
bool empty() const：返回底層容器是否為空。
size_t size() const：返回底層容器中元素的數量。
私有成員變量 _con：這是一個模板類的私有成員變量，用于存儲實際的棧元素。其類型是根據模板參數 Container 確定的，在實例化時會被替換為具體的容器類型。