? ? ? ?////// ? ? 歡迎來到 aramae 的博客，愿 Bug 遠離，好運常伴！ ?//////

博主的Gitee地址：阿拉美 (aramae) - Gitee.com

• 1. stack的介紹和使用
• 2. queue的介紹和使用
• 3. priority_queue的介紹和使用
• 4. 容器適配器

引言： 本章介紹 STL的 stack 和 queue 容器的使用，priority_queue的介紹和使用。簡單介紹適配器相關內容。

1. stack的介紹和使用

1.1 stack的介紹

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

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

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

• empty：判空操作
• back：獲取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部刪除元素操作

4.標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。?

stack文檔介紹：https://cplusplus.com/reference/stack/stack/?kw=stack?

1.2 stack的使用?

?簡單代碼演示：

#include <iostream>
// 包含 stack 相關頭文件
#include <stack> 
using namespace std;int main() {// stack()：構造空的棧，這里存儲 int 類型元素stack<int> stk; // empty()：檢測 stack 是否為空，剛開始棧空，輸出 1（true）cout << "棧是否為空：" << stk.empty() << endl; // push()：將元素壓入 stack 中，依次壓入 10、20、30stk.push(10); stk.push(20);stk.push(30);// size()：返回 stack 中元素的個數，此時有 3 個元素，輸出 3cout << "棧中元素個數：" << stk.size() << endl; // top()：返回棧頂元素的引用，棧頂是 30，輸出 30cout << "棧頂元素：" << stk.top() << endl; // pop()：將 stack 中尾部（棧頂）的元素彈出，彈出 30 后，棧里剩下 10、20stk.pop(); // 再次查看棧頂，變為 20，輸出 20cout << "彈出后棧頂元素：" << stk.top() << endl; return 0;
}

1.3 stack的模擬實現

#include <iostream>
#include <vector>
// 用于異常處理
#include <stdexcept> 
using namespace std;template <typename T>
class MyStack {
private:// 使用 vector 作為底層容器存儲數據vector<T> data;public:// 構造函數，創建一個空棧MyStack() {}// 判斷棧是否為空bool empty() const {return data.empty();}// 獲取棧中元素的個數size_t size() const {return data.size();}// 入棧操作，將元素壓入棧頂void push(const T& value) {data.push_back(value);}// 出棧操作，刪除并返回棧頂元素T pop() {if (empty()) {// 如果棧為空，拋出異常throw out_of_range("Stack is empty, can't pop element.");}T topElement = data.back();data.pop_back();return topElement;}// 獲取棧頂元素（不刪除）T& top() {if (empty()) {// 如果棧為空，拋出異常throw out_of_range("Stack is empty, can't get top element.");}return data.back();}//  const 版本的 top，用于 const 對象獲取棧頂元素（不刪除）const T& top() const {if (empty()) {throw out_of_range("Stack is empty, can't get top element.");}return data.back();}
};// 測試函數
void testStack() {MyStack<int> stack;// 入棧stack.push(10);stack.push(20);stack.push(30);cout << "Stack size: " << stack.size() << endl;cout << "Top element: " << stack.top() << endl;// 出棧int popped = stack.pop();cout << "Popped element: " << popped << endl;cout << "Now top element: " << stack.top() << endl;cout << "Is stack empty? " << (stack.empty() ? "Yes" : "No") << endl;
}int main() {testStack();return 0;
}

2. queue的介紹和使用

2.1 queue的介紹

• empty：檢測隊列是否為空
• size：返回隊列中有效元素的個數
• front：返回隊頭元素的引用
• back：返回隊尾元素的引用
• push_back：在隊列尾部入隊列
• pop_front：在隊列頭部出隊列

queue文檔介紹：?https://cplusplus.com/reference/queue/queue/

2.2 queue的使用?

簡單代碼演示：

#include <iostream>
// 包含 queue 容器的頭文件
#include <queue> 
using namespace std;int main() {// queue()：構造空的隊列，這里隊列存儲 int 類型數據queue<int> q; // empty()：檢測隊列是否為空，剛開始隊列為空，輸出 trueif (q.empty()) { cout << "隊列初始為空" << endl;}// push()：在隊尾將元素入隊列，依次把 10、20、30 入隊q.push(10); q.push(20); q.push(30); // size()：返回隊列中有效元素的個數，此時隊列有 3 個元素，輸出 3cout << "隊列中元素個數：" << q.size() << endl; // front()：返回隊頭元素的引用，隊頭是 10，輸出 10cout << "隊頭元素：" << q.front() << endl; // back()：返回隊尾元素的引用，隊尾是 30，輸出 30cout << "隊尾元素：" << q.back() << endl; // pop()：將隊頭元素出隊列，執行后隊頭元素 10 被移除，隊列剩下 20、30q.pop(); // 再次查看隊頭，變為 20，輸出 20cout << "執行 pop 后，新的隊頭元素：" << q.front() << endl; return 0;
}

2.3 queue的模擬實現

#include <iostream>
#include <list>
#include <stdexcept>  // 用于異常處理
using namespace std;template <typename T>
class MyQueue {
private:// 使用 list 作為底層容器存儲數據list<T> data;public:// 構造函數，創建一個空隊列MyQueue() {}// 判斷隊列是否為空bool empty() const {return data.empty();}// 獲取隊列中元素的個數size_t size() const {return data.size();}// 入隊操作，將元素添加到隊尾void push(const T& value) {data.push_back(value);}// 出隊操作，刪除并返回隊首元素T pop() {if (empty()) {// 如果隊列為空，拋出異常throw out_of_range("Queue is empty, can't pop element.");}T frontElement = data.front();data.pop_front();return frontElement;}// 獲取隊首元素（不刪除）T& front() {if (empty()) {// 如果隊列為空，拋出異常throw out_of_range("Queue is empty, can't get front element.");}return data.front();}// const 版本的 front，用于 const 對象獲取隊首元素（不刪除）const T& front() const {if (empty()) {throw out_of_range("Queue is empty, can't get front element.");}return data.front();}// 獲取隊尾元素（不刪除）T& back() {if (empty()) {// 如果隊列為空，拋出異常throw out_of_range("Queue is empty, can't get back element.");}return data.back();}// const 版本的 back，用于 const 對象獲取隊尾元素（不刪除）const T& back() const {if (empty()) {throw out_of_range("Queue is empty, can't get back element.");}return data.back();}
};// 測試函數
void testQueue() {MyQueue<int> queue;// 入隊queue.push(10);queue.push(20);queue.push(30);cout << "Queue size: " << queue.size() << endl;cout << "Front element: " << queue.front() << endl;cout << "Back element: " << queue.back() << endl;// 出隊int dequeued = queue.pop();cout << "Dequeued element: " << dequeued << endl;cout << "Now front element: " << queue.front() << endl;cout << "Is queue empty? " << (queue.empty() ? "Yes" : "No") << endl;
}int main() {testQueue();return 0;
}

?

priority_queue文檔介紹：https://cplusplus.com/reference/queue/priority_queue/

3.2 priority_queue的使用

?簡單代碼演示：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {// 1. 構造空的優先級隊列（默認最大堆）priority_queue<int> pq1;// 也可以用迭代器范圍構造，比如從 vector 構造vector<int> v = {3, 1, 4};priority_queue<int> pq2(v.begin(), v.end());// 2. empty()：檢測是否為空cout << "pq1 is empty? " << (pq1.empty() ? "true" : "false") << endl;cout << "pq2 is empty? " << (pq2.empty() ? "true" : "false") << endl;// 3. push(x)：插入元素pq1.push(5);pq1.push(2);pq1.push(7);// 4. top()：返回堆頂（最大）元素cout << "pq1 top element: " << pq1.top() << endl;cout << "pq2 top element: " << pq2.top() << endl;// 5. pop()：刪除堆頂元素pq1.pop();cout << "After pop, pq1 top element: " << pq1.top() << endl;pq2.pop();cout << "After pop, pq2 top element: " << pq2.top() << endl;return 0;
}

3.4 priority_queue的模擬實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;template <typename T>
class MyPriorityQueue {
private:vector<T> data;// 向上調整堆void siftUp(int index) {while (index > 0) {int parent = (index - 1) / 2;if (data[parent] < data[index]) {swap(data[parent], data[index]);index = parent;} else {break;}}}// 向下調整堆void siftDown(int index) {int n = data.size();while (true) {int left = 2 * index + 1;int right = 2 * index + 2;int maxIndex = index;if (left < n && data[left] > data[maxIndex]) {maxIndex = left;}if (right < n && data[right] > data[maxIndex]) {maxIndex = right;}if (maxIndex != index) {swap(data[index], data[maxIndex]);index = maxIndex;} else {break;}}}public:// 構造空隊列MyPriorityQueue() {}// 用迭代器范圍構造template <typename Iter>MyPriorityQueue(Iter first, Iter last) {while (first != last) {data.push_back(*first);first++;}// 構建堆，從最后一個非葉子節點開始向下調整for (int i = data.size() / 2 - 1; i >= 0; i--) {siftDown(i);}}bool empty() const {return data.empty();}T top() const {if (empty()) {throw "Queue is empty!";}return data[0];}void push(const T& x) {data.push_back(x);siftUp(data.size() - 1);}void pop() {if (empty()) {throw "Queue is empty!";}swap(data[0], data.back());data.pop_back();siftDown(0);}
};int main() {// 測試模擬實現的優先級隊列MyPriorityQueue<int> pq1;vector<int> v = {3, 1, 4};MyPriorityQueue<int> pq2(v.begin(), v.end());cout << "pq1 is empty? " << (pq1.empty() ? "true" : "false") << endl;cout << "pq2 is empty? " << (pq2.empty() ? "true" : "false") << endl;pq1.push(5);pq1.push(2);pq1.push(7);cout << "pq1 top element: " << pq1.top() << endl;cout << "pq2 top element: " << pq2.top() << endl;pq1.pop();cout << "After pop, pq1 top element: " << pq1.top() << endl;pq2.pop();cout << "After pop, pq2 top element: " << pq2.top() << endl;return 0;
}

---

4.容器適配器

4.1 什么是適配器

適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總 結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。

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

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

4.3 deque的簡單介紹(了解)

4.3.1 deque的原理介紹

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

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

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

那deque是如何借助其迭代器維護其假想連續的結構呢？?

4.3.2 deque的缺陷

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

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

4.5 STL標準庫中對于stack和queue的模擬實現

4.5.1 stack的模擬實現

#include <iostream>
#include <deque>// 模擬實現stack
template <typename T, typename Container = std::deque<T>>
class Stack {
public:// 構造函數，默認使用deque作為底層容器Stack() {}// 入棧操作，將元素壓入棧頂void push(const T& value) {container.push_back(value);}// 出棧操作，移除棧頂元素void pop() {if (!empty()) {container.pop_back();}}// 獲取棧頂元素的引用T& top() {return container.back();}const T& top() const {return container.back();}// 判斷棧是否為空bool empty() const {return container.empty();}// 獲取棧中元素的個數size_t size() const {return container.size();}private:Container container;
};

測試代碼：?

int main() {Stack<int> myStack;myStack.push(10);myStack.push(20);std::cout << "棧頂元素: " << myStack.top() << std::endl;myStack.pop();std::cout << "棧是否為空: " << (myStack.empty()? "是" : "否") << std::endl;return 0;
}

?

4.5.2 queue的模擬實現

#include <iostream>
#include <deque>// 模擬實現queue
template <typename T, typename Container = std::deque<T>>
class Queue {
public:// 構造函數，默認使用deque作為底層容器Queue() {}// 入隊操作，將元素添加到隊尾void push(const T& value) {container.push_back(value);}// 出隊操作，移除隊頭元素void pop() {if (!empty()) {container.pop_front();}}// 獲取隊頭元素的引用T& front() {return container.front();}const T& front() const {return container.front();}// 獲取隊尾元素的引用T& back() {return container.back();}const T& back() const {return container.back();}// 判斷隊列是否為空bool empty() const {return container.empty();}// 獲取隊列中元素的個數size_t size() const {return container.size();}private:Container container;
};

測試代碼：?

int main() {Queue<int> myQueue;myQueue.push(10);myQueue.push(20);std::cout << "隊頭元素: " << myQueue.front() << std::endl;std::cout << "隊尾元素: " << myQueue.back() << std::endl;myQueue.pop();std::cout << "新的隊頭元素: " << myQueue.front() << std::endl;return 0;
}

結語：感謝相遇

/// 高山仰止，景行行止。雖不能至，心向往之 ///