C++ -- STL-- stack and queue

       //////     欢迎来到 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;
}

结语：感谢相遇

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