C++初阶学习——探索STL奥秘——标准库中的queue与stack

1、适配器模式

STL 中的适配器可以分为三类:

从应用角度出发

容器适配器 container adapters

迭代器适配器 iterator adapters

仿函数适配器 functor adapters

其中，容器适配器可修改底层为指定容器

如由 vector 构成的栈、由 list 构成的队列

迭代器适配器可以实现其他容器的反向选代器

最后的仿函数适配器就厉害了

几乎可以无限制的创造出各种可能的表达式

本文介绍的是容器适配器，栈和队列都用到了容器适配器

最后还会介绍一下常作为这两种容器适配器的默认底层容器双端队列

2.stack

2.1介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3.可以看出，栈有两个模板参数
参数1:T 栈中的元素类型，同时也是底层容器中的元素类型
参数2: container 实现栈时用到的底层容器，这里为缺省参数，缺省结构为双端队列 deque

4. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作

back：获取尾部元素操作

push_back：尾部插入元素操作

pop_back：尾部删除元素操作

5. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2.2使用

可通过刷题来巩固对stack使用的理解

通过一个栈来存储数据，另一个栈来存储最小值

class MinStack
{
public: void push(int x){ // 只要是压栈，先将元素保存到_elem中_elem.push(x);// 如果x小于_min中栈顶的元素，将x再压入_min中if(_min.empty() || x <= _min.top())_min.push(x);}void pop(){// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除if(_min.top() == _elem.top())_min.pop();_elem.pop();}int top(){return _elem.top();}int getMin(){return _min.top();}private:// 保存栈中的元素std::stack<int> _elem;// 保存栈的最小值std::stack<int> _min;
};

class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {//入栈和出栈的元素个数必须相同if(pushV.size() != popV.size())return false;// 用s来模拟入栈与出栈的过程int outIdx = 0;int inIdx = 0;stack<int> s;while(outIdx < popV.size()){// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈while(s.empty() || s.top() != popV[outIdx]){if(inIdx < pushV.size())s.push(pushV[inIdx++]);elsereturn false;}// 栈顶元素与出栈的元素相等，出栈s.pop();outIdx++;}return true;}
};

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){string& str = tokens[i];// str为数字if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(atoi(str.c_str()));}else{// str为操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':// 题目说明了不存在除数为0的情况s.push(left / right);break;}}}return s.top();}
};

2.3模拟实现

#pragma once
#include <vector>using namespace std;namespace Yohifo
{//这里选择模板参数2 底层容器 的缺省值为 vectortemplate<class T, class Container = vector<int>>class stack{public:/*创建出Container的对象_c的时候就已经调用了Container中的默认构造，所以这边不必特地编写stack的默认构造函数*/stack(){}{}//不需要显式的去写析构函数，默认生成的够用了//同理拷贝构造、赋值重载也不需要bool empty() const{return _c.empty();}size_t size() const{return _c.size();}//top 需要提供两种版本T& top(){return _c.back();}const T& top() const{return _c.back();}//选取的底层容器必须支持尾部操作void push(const T& val){_c.push_back(val);}void pop(){//空栈不能弹出，可在底层容器中检查出来_c.pop_back();}private:Container _c;	//成员变量为具体的底层容器};
}

适配器的厉書之处就在于只要底层容器有我需要的函数接口，那么我就可以为其适配出一个容器适配器，比如 vector 构成的栈、list构成的栈、 deque 构成的栈，甚至是 string 也能适配出一个栈

只要符合条件，都可以作为栈的底层容器，当然不同结构的效率不同，因此库中选用的是效率较高的 deque 作为默认底层容器

3.queue

3.1介绍

1.队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作

其中从容器一端插入元素，另一端提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。

元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。

该底层容器应至少支持以下操作:

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

3.2queue的使用

同样我们可以通过刷题巩固对queue使用时的理解

class MyStack {
private:queue<int>q1;queue<int>q2;
public:MyStack() {}void push(int x) {//q1用来存储数据，q2仅起辅助作用q1.push(x);}int pop() {int n=q1.size()-1;//把q1前n-1个元素放入q2，取最后一个，q2再重新放入q1int ans=0;while(n--){q2.push(q1.front());q1.pop();}ans=q1.front();q1.pop();while(!q2.empty()){q1.push(q2.front());q2.pop();}return ans;}int top() {return q1.back();}bool empty() {return q1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr){return ret;}queue<TreeNode*> q;q.push(root);while(!q.empty()){   ret.push_back(vector<int>());int levelsize=q.size();for(int i=1;i<=levelsize;i++){if(q.front()->left)q.push(q.front()->left);if(q.front()->right)q.push(q.front()->right);ret.back().push_back(q.front()->val);q.pop();}}return ret;}
};

3.3模拟实现

原理和stack差不多

#pragma once
#include <list>using namespace std;namespace Yohifo
{template<class T, class Container = list<T>>class queue{public:queue(){}/*创建出Container的对象_c的时候就已经调用了Container中的默认构造，所以这边不必特地编写queue的默认构造函数*/                        //这里也不需要提供拷贝构造、赋值重载、析构函数bool empty() const{return _c.empty();}size_t size() const{return _c.size();}//选取的底层容器中，已经准备好了相关函数，如 front、backT& front(){return _c.front();}const T& front() const{return _c.front();}T& back(){return _c.back();}const T& back() const{return _c.back();}void push(const T& val){_c.push_back(val);	//队列只能尾插}void pop(){_c.pop_front();	//队列只能头删}private:Container _c;	//成员变量为指定的底层容器对象};
}

4.总结

栈和队列在实际开发中作为一种辅助结构被经常使用，比如内存空间划分中的栈区，设计规则符合栈FILO;

操作系统中的各种队列，如

阻塞队列，设计规则符合队列 FIFO。

除此以外，在很多OJ题中，都需要借助栈和队列进行解题

注意:
栈和队列都属于特殊的数据结构，原则上是不支持遍历的，因为一旦进行遍历，其中的数据必然被弹出，因此两者都没有提供迭代器

假设容器没有提供头尾操作，比如 map 和 set ，那么就不能拿它们适配出栈或队列，强行使用会报错

5.双端队列deque（了解就行）

5.1介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是

可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)

与vector比较，头插效率高，不需要搬移元素。

与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的

deque 的扩容机制:只需要对中控数组 map 进行扩容，再将原 map 中的数组指针拷贝过来即可，效率比较高

deque 中的随机访问:

1.(下标 -前预留位)/单个数组长度获取对应小数组位置

2.(下标 -前预留位)%单个数组长度获取其在小数组中的对应下标

示例
假设我们有一个std::deque，它由3个数组组成，每个数组可以存储4个元素。现在我们想要访问下标为8的元素:
1.确定数组索引:
设前预留位为0(即没有预留空间)，
则数组索引为(8-0)/4=2。这意味着我们要找的元素在第三个数组中。
2.确定数组内偏移:
数组内偏移为(8-0)%4=0。这意味着元素是第三个数组的第一个元素

由此可见，单个数组大小(缓冲区大小)需要定长，否则访问时计算会比较麻烦，但长度定长后，会引发中间位置插入删除效率低的问题

对此 sGI 版的 STL 选择牺牲中间位置插入，提高下标随机访问速度，令小数组定长，这也是将它作为栈和队列默认底层容器的原因之，因为栈和队列不需要对中间进行操作

为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上