【C++】stack与queue和deque

什么是适配器

适配器是一种计划模式(计划模式是一套被反复利用的、多数人知晓的、经太过类编目标、代码计划履历的总结)，该种模式是将一个类的接口转换成客户渴望的别的一个接口。
可普通明白，当我们出国旅游时国外插座我们无法直接利用，而须要一个交换电适配器来资助我们利用本身的充电插头。而这个交换电适配器就是我们所说的适配器
1.stack的先容

适配器的本质是复用

• stack是一种容器适配器，专门用在具有后进先出操纵的上下文情况中，其删除只能从容器的一端举行元素的插入与提取操纵。
  
• stack是作为容器适配器被实现的，容器适配器便是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
  
• stack的底层容器可以是任何尺度的容器类模板大概一些其他特定的容器类，这些容器类应该支持以下操纵：
  empty：判空操纵
  back：获取尾部元素操纵
  push_back：尾部插入元素操纵
  pop_back：尾部删除元素操纵
  
• 尺度容器vector、deque、list均符合这些需求，默认情况下，假如没有为stack指定特定的底层容器，默认情况下利用deque
  

1.2.stack的利用

最小栈

怎样获取栈中最小元素？
创建一个栈专门用来存储最小元素，起首栈中入一个元素，最小栈也入雷同元素，接着栈中再入元素，若<=上个元素则入最小栈，否则继续在栈中入元素。
pop之后怎样获取最小元素？
若栈顶元素便是最小栈顶元素，一起删撤除，否则只删除栈顶元素。如许能保持两个栈的同步性，终极会同时为空
假设最初push3451元素

1. class MinStack {
2. public:
3.     MinStack() {
4.         
5.     }
6.    
7.     void push(int val) {
8.         st.push(val);
9.         if(minst.empty()||st.top()<=minst.top())
10.         {
11.             minst.push(val);
12.         }
13.     }
14.    
15.     void pop() {
16.         if(st.top()==minst.top())
17.         {
18.             minst.pop();
19.         }
20.         st.pop();
21.     }
22.     //职责是返回栈顶元素，所以不是minst.top()
23.     //minst的是该类的对象，也可以调用该成员函数
24.     int top() {
25.         return st.top();
26.     }
27.    
28.     int getMin() {
29.         return minst.top();
30.     }
31.     private:
32.     stack<int> st;
33.     stack<int> minst;
34. };

复制代码

栈的弹出压入序列

思绪：
1.用一个栈来入数据，数据个数便是第一个序列(栈的压入序次)
2.跟出栈序列匹配，若匹配把匹配的数据都pop掉，若不匹配则继续入数据直到匹配
3.末了用来入数据的栈若便是空，则该弹出序次公道

1. bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
2.        stack<int> st;
3.        int pushi=0,popi=0;
4.         while(pushi<pushV.size())
5.         {
6.             //先入一个看是否匹配
7.             st.push(pushV[pushi++]);
8.             if(st.top()!=popV[popi])
9.             {
10.                 //不匹配情况，继续循环
11.                 continue;
12.             }
13.             else {
14.                 while(!st.empty()&&st.top()==popV[popi])
15.                 {
16.                     st.pop();
17.                     popi++;
18.                 }
19.         
20.             }
21.         }
22.         return st.empty();
23.     }

复制代码

须要留意不要在条件判定中对索引举行自增或自减操纵，制止条件判定失败而造成的索引变革。
通过创建一个stack<>的对象st来从pushV中入数据，再和popV中弹出序列举行比力
逆波兰表达式求值

逆波兰表达式是一种不包罗括号的算术表达式，此中操纵符（如加、减、乘、除）位于操纵数的背面。这种表达式也被称为后缀表达式。
逆波兰表达式可以直接用栈（stack）数据结构举行盘算，盘算过程简朴且高效。

怎样将中缀表达式转化为后缀表达式？
1.操纵数输出
2.操纵符入栈举行比力
a，栈为空或操纵符比栈顶的优先级高，继续入栈
b，栈不为空且当前操纵符比栈顶的优先级低或相称，输出栈顶操纵符
c，表达式竣过后依次出栈内里的操纵符
怎样举行后缀表达式运算？
1.操纵数入栈
2.操纵符，取栈顶两个元素举行运算，运算效果继续入栈。
碰到括号标题？
与转化后缀表达式一样，只是碰到左括号时举行递归，竣事标志为压入右括号。

1. class Solution {
2. public:
3.     int evalRPN(vector<string>& tokens) {
4.         stack<int> st;
5.         for(auto& str:tokens)
6.         {
7.             if(str=="+"||str=="-"||str=="*"||str=="/")
8.             {
9.                 int right=st.top();
10.                 st.pop();
11.                 int left=st.top();
12.                 st.pop();
13.                 switch(str[0])
14.                 {
15.                     case '+':
16.                     st.push(left+right);
17.                     break;
18.                     case '-':
19.                     st.push(left-right);
20.                     break;
21.                     case '*':
22.                     st.push(left*right);
23.                     break;
24.                     case '/':
25.                     st.push(left/right);
26.                     break;
27.                 }
28.             }
29.             else
30.             {
31.                 st.push(stoi(str));
32.             }
33.         }
34.         return st.top();
35.     }
36. };

复制代码

须要留意，由于栈后进先出的特性，以是左操纵数先入栈，后取，先取的栈顶元素为右操纵数
1.3.stack的模拟实现

1. #pragma once
2. #include<list>
3. #include<vector>
4. #include<deque>
6. namespace ee
7. {
8.         template<class T,class container = deque<T>>
9.         class stack
10.         {
11.         public:
12.                 void push(const T& x)
13.                 {
14.                         _con.push_back(x);
15.                 }
17.                 void pop()
18.                 {
19.                         _con.pop_back();
20.                 }
22.                 T& top()
23.                 {
24.                         return _con.back();
25.                 }
27.                 size_t size()
28.                 {
29.                         return _con.size();
30.                 }
32.                 bool empty()
33.                 {
34.                         return _con.empty();
35.                 }
36.         private:
37.                 container _con;
38.         };
39. }

复制代码

第二个模板参数给了一个容器缺省参数deque，没传值时默认利用。stack一样寻常适配vector和list容器，焦点成员函数中的函数二者对库中都有界说，可以直接复用。
留意：.h文件不会被编译，编译阶段直接在源文件中处理惩罚其睁开的.h文件，编译器遵照向上探求原则，留意定名空间和头文件的声明序次。以是我们直接在须要利用的源文件包罗头文件之前睁开定名空间即可。

2.queue的先容

• 队列是一种容器适配器，专门用于在FIFO上下文(先辈先出)中操纵，此中从容器一端插入元素，另一端提取元素。
  
• 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
  
• 底层容器可以是尺度容器类模板之一，也可以是其他专门计划的容器类。该底层容器应至少支持以下操纵:
  empty：检测队列是否为空
  size：返回队列中有效元素的个数
  front：返回队头元素的引用
  back：返回队尾元素的引用
  push_back：在队列尾部入队列
  pop_front：在队列头部出队列
  

• 尺度容器类deque和list满足了这些要求。默认情况下，假如没有为queue实例化指定容器类，则利用尺度容器deque。
  

2.1.queue的利用

二叉树的层序遍历

思绪1：
双队列：一个队列1用于存储当前层节点，另一个2用来存储下一层的节点。取出根节点，将其左右节点存储到2中，当1为空时将2的节点转移到1中并清空2，开始处理惩罚下一层。
思绪2：

1. class Solution {
2. public:
3.     vector<vector<int>> levelOrder(TreeNode* root) {
4.         vector<vector<int>> vv; // 用于存储最终结果
5.         queue<TreeNode*> q;      // 用于层序遍历的队列
6.         int levelSize = 0;       // 当前层的节点数量
8.         if (root) {
9.             q.push(root);        // 将根节点加入队列
10.             levelSize = 1;       // 根节点所在的层有1个节点
11.         }
13.         while (!q.empty()) {
14.             vector<int> v;       // 用于存储当前层的节点值
15.             for (int i = 0; i < levelSize; ++i) {
16.                 TreeNode* front = q.front(); // 获取队列前端的节点
17.                 q.pop();                     // 移除队列前端的节点
18.                 v.push_back(front->val);     // 将节点值加入当前层的向量
19.                 // 如果当前节点有左子节点，将其加入队列
20.                 if (front->left) {
21.                     q.push(front->left);
22.                 }
23.                 // 如果当前节点有右子节点，将其加入队列
24.                 if (front->right) {
25.                     q.push(front->right);
26.                 }
27.             }
28.             vv.push_back(v);      // 将当前层的节点值加入结果向量
29.             levelSize = q.size(); // 更新下一层的节点数量
30.         }
31.         return vv; // 返回层序遍历的结果
32.     }
33. };

复制代码

层序遍历：利用while循环处理惩罚队列中的节点，直到队列为空。每次循环处理惩罚一层的节点：
创建一个向量v用于存储当前层的节点值。
利用for循环处理惩罚当前层的全部节点（levelSize次）：
获取队列前端的节点。将节点值到场v。
假如节点有左子节点，将其到场队列。假如节点有右子节点，将其到场队列。
将v到场效果向量vv。
焦点：levelsize为当前队列的巨细，每次层序遍历之后更新，一遍处理惩罚下一层
2.2.queue的模拟实现

queue接口中存在头删和尾删，用vector封装服从低下(会挪动数据)，一样寻常用list或deque来实现

1. #pragma once
2. #include<vector>
3. #include<list>
4. #include<deque>
6. namespace ee
7. {
8.         template<class T,class container =deque<T>>
9.         class queue
10.         {
11.         public:
12.                 void push(const T& x)
13.                 {
14.                         _con.push_back(x);
15.                 }
17.                 void pop()
18.                 {
19.                         _con.pop_front();
20.                         //vector容器强制适配，不推荐
21.                         //_con.erase(_con.begin());
22.                 }
24.                 T& front()
25.                 {
26.                         return _con.front();
27.                 }
29.                 T& back()
30.                 {
31.                         return _con.back();
32.                 }
34.                 bool empty()
35.                 {
36.                         return _con.empty();
37.                 }
38.         private:
39.                 container _con;
40.         };
41.        
42. }

复制代码

复用list在stl库中的接口界说即可，deque都满足。
3.相识deque

deque的原理先容

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的寄义是：可以在头尾两端举行插入和删除操纵，且时间复杂度为O(1)，与vector比力，头插服从高，不须要搬移元素；与list比力，空间利用率比力高。而且可以举行下标随机访问操纵

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

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“团体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器计划就比力复杂

deque迭代器中封装了四个指针，cur指向buffer中当前位置，first和last分别指向头尾位置，node用于指向差异的buffer，当firts便是last时node指向下一个buffer，云云往复举行遍历。
普通明白如下

deque本质是指针数组，每个数组巨细唯一。当指针数组满了，中控指针数组扩容即可。需留意头插时元素是从指针数组的尾部往头部去插入的
对比：vector<vector>是对象数组，每个对象巨细不一
对比及缺陷

deque的功能大有集list与vector于一体的感觉，那为什么它不能取代它们而且实际应用场景不多呢？
vector
上风：下标随机访问服从高
劣势：扩容（异地）代价高，中心和头部插入服从标题（数据团体挪动）
list
上风：恣意位置插入删除，空间按需申请开释
劣势：不支持下标随机访问
deque
相比vector
上风：极大缓解了扩容标题（复制指针数组无需拷贝数据代价低，头插头删标题（无需挪动数据）
劣势：[]下标访问不敷极致，须要盘算在哪个buffer，在哪个buffer中的第几个

测试deque的[]访问服从

1. void test_op()
2. {
3.         srand(time(0));
4.         const int N = 10000;
5.         vector<int> v1;
6.         vector<int> v2;
7.         v1.reserve(N);
8.         v2.reserve(N);
10.         deque<int> dq1;
11.         deque<int> dq2;
13.         for (int i = 0; i < N; ++i)
14.         {
15.                 auto e = rand();
16.                 //v1.push_back(e);
17.                 //v2.push_back(e);
18.                 dq1.push_back(e);//间接测
19.                 dq2.push_back(e);//直接测
20.         }
22.         // 拷贝到vector排序，排完以后再拷贝回来
23.         int begin1 = clock();
24.         // 先拷贝到vector
25.         for (auto e : dq1)
26.         {
27.                 v1.push_back(e);
28.         }
30.         // 排序
31.         sort(v1.begin(), v1.end());
33.         // 拷贝回去
34.         size_t i = 0;
35.         for (auto& e : dq1)
36.         {
37.                 e = v1[i++];
38.         }
40.         int end1 = clock();
42.         int begin2 = clock();
43.         //sort(v2.begin(), v2.end());
44.         sort(dq2.begin(), dq2.end());
46.         int end2 = clock();
48.         printf("deque copy vector sort:%d\n", end1 - begin1);
49.         printf("deque sort:%d\n", end2 - begin2);
50. }

复制代码

这还只是通过vector资助排序后再拷贝会deque举行比力，已经做出捐躯但deque还是比不外，若直接与vector举行快排比力，随着数据量增大，将会屁滚尿流
相比list
上风:可支持下标随机访问，一段段小空间拼接而成的空间cpu高速缓存服从不错
劣势：中心插入服从低下。
1.内存块的固定巨细：
每个内存块巨细是固定的。当须要在中心插入元素时，大概须要在多个内存块之间移动元素，以腾出空间给新元素。这种操纵涉及到大量的内存复制，服从较低。
2.元素的重新分配：
假如插入位置所在的内存块已满，大概须要重新分配内存块，并将现有元素复制到新的内存块中。这会导致额外的内存分配和复制操纵，进一步低沉服从。
3.指针的更新：
插入元素后，须要更新多个指针来维护内存块之间的链接关系。这增长了操纵的复杂性和时间开销。
因此在实际中，须要线性结构时，大多数情况下优先思量vector和list，deque的应用并不多
而如今能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
缘故原由：
1.stack和queue不须要遍历(因此stack和queue没有迭代器，计划目标限定了访问方式)，只须要在固定的一端大概两端举行操纵。
2.2. 在stack中元素增长时，deque比vector的服从高(扩容时不须要搬移大量数据)；queue中的元素增长时，deque不光服从高，而且内存利用率高。团结了deque的优点，而完善的避开了其缺陷。