C++ ----------- 栈和队列
1.Stack的使用1.1习题1.2 Stack 模拟实现（容器） 2.queue队列使用2.1 练习2.2队列的模拟实现（容器） 3.priority_queue的使用和介绍3.1 push_heap(插入堆)3.2 make_heap(建堆)3.3 pop_heap3.2 priority_queue 的使用3.3练习3.4 priority_queue模拟实现 4 适配容器4.1 什么是适配器4.2 STL标准库中stack和queue的底层结构4.3 deque的简单介绍(了解)4.5 deque的缺陷4.6为什么选择dequeue作为queue或stack的底层默认容器4.7 STL标准库中对于stack和queue的模拟实现
1.Stack的使用
| 函数 | 功能说明 |
|---|---|
| stack() | 构造 |
| empty() | 判空 |
| size() | 返回stack中元素个数 |
| top() | 返回栈顶元素 |
| push() | 压栈 |
| pop() | 出栈 |
1.1习题
最小栈
class MinStack {public: MinStack() {} void push(int val) { x_stack.push(val); if (min_stack.empty() || min_stack.top() >= val) { min_stack.push(val); } } void pop() { //如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除 if (x_stack.top() == min_stack.top()) { min_stack.pop(); } x_stack.pop(); } int top() { return x_stack.top(); } int getMin() { return min_stack.top(); }private: stack<int> x_stack;//保存入栈元素 stack<int> min_stack;//保存最小元素};解题思想:建俩个栈，一个入数据，一个记录最小数据:
判断栈的弹出压入序
#include <stack>class Solution {public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here size_t pos=0; stack<int> s1; for(auto& e:pushV) { //入栈 s1.push(e); //出栈 while(!s1.empty()&&s1.top()== popV[pos]) { s1.pop(); pos++; } } return s1.empty(); }};解题思想:
1.2 Stack 模拟实现（容器）
template<class T, class Container>//适配容器来实现栈class StacK{public:void push_back(const T& x){_con.push_back(x);//把尾当做栈顶}const T& top(){return _con.back();}void pop(){_con.pop_back();}size_t size() const{return _con.size();}bool empty(){return _con.empty();}private:Container _con;//容器};
用不同容器来实现栈，数组栈，链表栈…；
2.queue队列使用
| 函数 | 功能说明 |
|---|---|
| queue() | 构造 |
| empty() | 判空 |
| size() | 返回stack中元素个数 |
| front() | 返回队列头元素 |
| push() | 在队尾将元素入队列 |
| pop() | 将对头出队列 |
2.1 练习
队列实现栈
class MyStack {queue<int> in;queue<int> out;public: MyStack() {} void push(int x) { in.push(x); while(!out.empty()) { in.push(out.front()); out.pop(); } swap(in,out); } int pop() { int s=out.front(); out.pop(); return s; } int top() { return out.front(); } bool empty() { return out.empty(); }};解题思想：
入栈队列q1，出栈q2q1入栈,如q2的值不为空，那么先要吧q2的值给q1，在把q1的值换给q2。这样才能保持栈的后进先出
2.2队列的模拟实现（容器）
template<class T, class Container>//适配容器来实现栈class queue{public: queue() {}void push(const T& x){_con.push_back(x);}const T& front(){return _con.front();}const T& back(){return _con.back();}void pop(){_con.pop_back();}const size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;//容器};3.priority_queue的使用和介绍
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的 2. 此类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素) 3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器， queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过
随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
5.标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。6. 需要支持随机访问迭代器，以便始终在内部保持堆结构. 容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
提醒：push_heap,pop_heap,make_heap,都包含在algorithm里面
3.1 push_heap(插入堆)
//形式 push_heap(随机迭代器1，随机迭代器2，仿函数)//调堆//make_heap调堆int myints[] = { 10,20,30,5,15 };std::vector<int> v(myints, myints + 5);v.push_back(99); std::push_heap(v.begin(), v.end());std::cout << "max heap after push: " << v.front() << '\n';3.2 make_heap(建堆)
int myints[] = { 10,20,30,5,15 };std::vector<int> v(myints, myints + 5);std::make_heap(v.begin(), v.end());std::cout << "initial max heap : " << v.front() << '\n';
3.3 pop_heap
int myints[] = { 10,20,30,5,15 };std::vector<int> v(myints, myints + 5);std::pop_heap(v.begin(), v.end()); v.pop_back();std::cout << "max heap after pop : " << v.front() << '\n';
3.2 priority_queue 的使用
| 函数 | 功能说明 |
|---|---|
| priority_queue(),priority_queue(first,last) | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空，是返回true，否则返回false |
| top() | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
【注意】
1.默认情况下，priority_queue 是大堆
1.2如果要建小堆，那么要用仿函数来建 大或小堆
2.如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
using namespace std;class Date{public:Date(int year=2000,int month=01,int data=01):_year(year),_month(month),_data(data){}bool operator<(const Date& x) const {return (_year < x._year)||((_year==x._year)&&(_month < x._month))||((_month == x._month)&&(_data < x._data));}bool operator==(const Date& x) const {return _year == x._year&& _month == x._month && _data == x._data;}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._data;return _cout;}private:int _data;int _month;int _year;};void TestPriorityQueue(){//自定义类型要支持<的比较priority_queue<Date> s;s.push(Date(2000, 2, 2));s.push(Date(2001, 2, 2));s.push(Date(2002, 2, 2));cout << s.top() << endl;}3.3练习
top_k问题
class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> s; for (auto e : nums) { s.push(e); } for (int i = 0; i < k - 1; ++i) { s.pop(); } return s.top(); }};解题思路：运用priority_queue,来解决top_k问题,priority_queue底层是堆。
1：先把nums数据建堆
2：再用for循环来遍历出第k最大个数
3.4 priority_queue模拟实现
template<class T>struct compare{bool operator()(const T& x, const T& y){return x < y;}};template<class T,class Container = vector<T>,class compare= compare<T>> class priority_queue//优先队列本质是个堆{public:void Adjust(size_t child)//向上调堆{compare com;size_t parent = (child-1)/2;while (child > 0){if (com(_con[child],_con[parent])){ swap(_con[child],_con[parent]); child = parent; parent = (child - 1) / 2;}else{break;}}}void Adjustdown(size_t parent)//向下调堆{size_t child = (parent * 2) + 1;compare com;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1],_con[child])){child = child + 1;}if (com(_con[child] , _con[parent])){swap(_con[child],_con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){//调堆_con.push_back(x);Adjust(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjustdown(0);}const T& top(){return _con[0]; }size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;}; priority_queue底层是堆，而对于调堆如果不懂的话可以去看《数据结构》堆， 再来这里看priority_queue模拟实现，这里不做解释。4 适配容器
4.1 什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
相当于安卓，苹果，三星充电接口各有不同
4.2 STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
4.3 deque的简单介绍(了解)
1:deque的原理介绍deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
【注意】deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
dequeue 迭代器有四个结点，cur ，first ，last，node。node指针指向中控器上的结点，firs指向buffer的第一个buffer第一个结点，而cur指向是有buffer有效结点的下一个结点，而last指向的是buffer最后一个结点
4.5 deque的缺陷
优势
1: 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
2:与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
缺点：
deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
4.6为什么选择dequeue作为queue或stack的底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如: list
但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。 2.在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。4.7 STL标准库中对于stack和queue的模拟实现
Stack
#include<deque>namespace bite{template<class T, class Con = deque<T>>//template<class T, class Con = vector<T>>//template<class T, class Con = list<T>>class stack{public:stack() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};}queue
#include<deque>#include <list>namespace bite{template<class T, class Con = deque<T>>//template<class T, class Con = list<T>>class queue{public:queue() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};}