stack 和 queue

一、stack

1.1 stack 的介绍

1.2 stack的使用

1）最小栈

2）栈的弹出压入序列

3）逆波兰表达式求值

1.3 stack 的模拟使用

二、queue

2.1 queue的介绍

2.2 queue的使用

2.3 queue的模拟使用

三、容器适配器

3.1 什么是容器适配器

3.2 STL标准库中stack 和 queue的底层结构

四、deque

4.1 deque的原理介绍

4.2 deque的缺陷

4.3 为什么选择 deque 作为stack 和 queue的底层默认容器

五、priority_queue

5.1 priority_queue的介绍

5.2 priority_queue的使用

1）数组中第K个大的元素

5.3 priority_queue的模拟实现

一、stack

1.1 stack 的介绍

stack文档 : stack - C++ Reference

stack 不支持适配器 ，因为需要满足 后进先出的 特性：

相关接口如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
using namespace std;int main()
{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;return 0;
}

1.2 stack的使用

1）最小栈

155. 最小栈 - 力扣（LeetCode）

class MinStack {
public:void push(int val) {_st.push(val);if(_minst.empty() || val <= _minst.top())_minst.push(val);}void pop() {if(_st.top() == _minst.top())_minst.pop();_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}stack<int> _st;stack<int> _minst;
};

2）栈的弹出压入序列

栈的压入、弹出序列_牛客题霸_牛客网

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {stack<int> st;size_t pushi = 0,popi = 0;while(pushi < pushV.size()){st.push(pushV[pushi++]);while(!st.empty() && st.top() == popV[popi]){st.pop();popi++;}}return st.empty();}
};

3）逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

为了更加方便理解，下面是有关中缀表达式转后缀表达式的题目，加深理解。

题号	中缀表达式	后缀表达式
1	`a + b - c`	`a b + c -`
2	`x * y / z`	`x y * z /`
3	`3 + 5 * 2`	`3 5 2 * +`
4	`10 - 6 / 3`	`10 6 3 / -`
5	`(a + b) * c`	`a b + c *`
6	`x / (y - z)`	`x y z - /`
7	`(3 + 5) * 2 - 4`	`3 5 + 2 * 4 -`
8	`10 - (2 * 3 + 5)`	`10 2 3 * 5 + -`
9	`a + (b * c - d) / e`	`a b c * d - e / +`
10	`( (3 + 5) * 2 ) / (10 - 8)`	`3 5 + 2 * 10 8 - /`
11	`x * (y + z) - w / v`	`x y z + * w v / -`
12	`(a - b) * (c + d / e)`	`a b - c d e / + *`

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto & str:tokens){if(str == "+" || str == "-" || str == "*" || str == "/"){int right = st.top();st.pop();int left = st.top();st.pop();switch(str[0]){case '+':st.push(left + right);break;case '-':st.push(left - right);break;case '*':st.push(left * right);break;case '/':st.push(left / right);break;}}else{st.push(stoi(str));}}return st.top();}
};

1.3 stack 的模拟使用

通过复用来实现相关接口，

stack.h

#pragma oncenamespace LF
{template<class T, class Container>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top()const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

test.cpp 测试：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include"Stack.h"
using namespace std;int main()
{//LF::stack<int,vector<int>> st;LF::stack<int,list<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;return 0;
}

二、queue

queue文档：queue - C++ Reference

2.1 queue的介绍

1. 队列是一种容器适配器，专门用于在 FIFO上下文(先进先出) 中操作，其中从容器一端插入元素，另一端提取元素 .

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

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列

2.2 queue的使用

2.3 queue的模拟使用

注意 : vector 不能匹配队列，因为 vector 不支持头删

queue.h

#pragma once
#include<deque>namespace LF
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front() const{return _con.front();}const T& back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

test.cpp测试

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include"Stack.h"
using namespace std;
#include"queue.h"int main()
{LF::queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;return 0;
}

三、容器适配器

3.1 什么是容器适配器

适配器是一种设计模式 （设计模式是一套被反复使用的、多人知晓的、经过反复编目的、代码设计经验的总结）， 该模式就是将一个类的接口转换成客户希望的另外一个接口。

3.2 STL标准库中stack 和 queue的底层结构

虽然 stack 和 queue中也可以存放元素，但在 STL中并没有将其划分在容器的行列 ，而是将其称为容器适配器 ， 这是因为 stack 和队列只是对其他容器的接口进行了包装 ， STL中stack 和 queue 默认使用 deque , 如下：

四、deque

4.1 deque的原理介绍

deque - C++ Reference

deque(双端队列) ：是一种双开口的“连续” 空间的数据结构， 双开口的含义是：可以在头尾两端进行插入和删除操作， 且时间复杂度为O(1) , 与 vector 比较，头插效率高，不需要搬移元素；与list 比较，空间利用率高。

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

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

那deque 是如何借助其迭代器维护其假象连续的结构呢？

4.2 deque的缺陷

1. 与 vector 比较 ， deque 的优势是：头部插入和删除时候，不需要搬移元素， 效率特别高，而且在扩容时，也不需要搬移大量元素，因此其效率是比 vector 高。

2. 与list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

3. 但是， deque有一个致命的缺陷 ：

不适合遍历， 因为在遍历时， deque 的迭代器要频繁的去检测其是否移动到某一段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list , deque 的应用并不多，而目前能看到的一个应用就是， STL用其作为stack 和 queue 的底层结构。

4.3 为什么选择 deque 作为stack 和 queue的底层默认容器

1 . stack 是一种后进先出的特殊结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为stack的底层容器，比如vector 和 list 都可以 。

2. queue 是 先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue的底层容器， 比如 list 。

但是STL中对stack 和 queue 默认选择 deque 作为底层容器，主要是因为：

1. stack 和 queue不需要遍历（因此 stack 和 queue没有迭代器），只需要固定的一端或者两端进行操作。

2. 在 stack 中元素增长时， deque比vector 的效率高（扩容时不需要搬移大量数据）;queue中的元素增长时， deque不经效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了缺陷

五、priority_queue

priority_queue - C++ Reference

5.1 priority_queue的介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素 总是它所包含的元素中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

5.2 priority_queue的使用

优先级队列默认使用 vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<queue>
using namespace std;int main()
{
//默认是大的优先级高priority_queue<int> pq;pq.push(15);pq.push(2);pq.push(31);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

1）数组中第K个大的元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> p(nums.begin(),nums.end());while(--k){p.pop();} return p.top();}
};

5.3 priority_queue的模拟实现

#pragma once
#include<vector>namespace bit
{template <class T>struct less {bool operator() (const T& x, const T& y) const{ return x < y;}};template <class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:// 强制生成priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){// 建堆for (int i = (_con.size()-1-1)/2; i >= 0; i--){AdjustDown(i);}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// 假设法，选出左右孩子中小的那个孩子//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}