【C++】stack和queue

阅读本书更多章节>>>>

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、stack的介绍和使用

1.1 stack的介绍

1.2 stack的使用

最小栈

栈的弹出压入序列

逆波兰表达式求值(后缀表达式)

1.3 stack的模拟实现

二、queue的介绍和使用

2.1 queue的介绍

2.2 queue的使用

2.3 queue的模拟实现

三、priority_queue的介绍和使用

3.1 priority_queue的介绍

3.2 priority_queue的使用

3.3 priority_queue的模拟实现

3.4 看一下Date类的priority_queue的模拟实现

四、容器适配器

4.1 什么是适配器

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

4.3 deque的简单介绍(了解)

4.3.1 deque的原理介绍

4.3.2 deque的缺陷

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

总结

---

---

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、stack的介绍和使用

1.1 stack的介绍

stack的文档介绍

翻译:

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

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

empty：判空操作back：获取尾部元素操作push_back：尾部插入元素操作pop_back：尾部删除元素操作标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

1.2 stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

最小栈

准备两个栈：st栈存正常数据；minst栈存当前位置的最小数据

minst栈压栈进入数据的情况：

1、minst栈为空；2、st栈顶的元素比minst栈顶的元素小时；3、st栈顶元素和minst栈顶元素相等(比如：st栈中的最上面有两个最小值-1，如果minst栈中只压栈一个-1元素，那么当st栈要pop()操作的时候，minst栈也要跟着pop()操作；那么此时minst栈存放的是当前位置的最小数据0，而st栈中的最小数据为-1；此时就不对了)。

class MinStack {public:    MinStack() {    }        stack<int> _st;    stack<int> _minst;    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();    }};

栈的弹出压入序列

解题思路：

1、先把入栈序列入栈；

2、栈顶元素和出栈序列是否匹配；

a、如果匹配，持续出数据，直到不匹配或者栈为空，栈为空，继续将入栈序列入栈；b、如果不匹配，继续将入栈序列入栈；

结束标志：入栈序列走完了。

不匹配序列：

1、入栈序列走完了，栈不为空；

2、出栈序列没有到尾。

lass Solution {public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *     *      * @param pushV int整型vector      * @param popV int整型vector      * @return bool布尔型     */    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {        // pushV:入栈序列   popV:出栈序列  都是顺序表        int pushi = 0, popi = 0;// 出栈序列和入栈序列的最开始的位置        stack<int> st;// 创建一个栈        // 结束标志：入栈序列走完了        while(pushi < pushV.size())        {            st.push(pushV[pushi++]);            while(!st.empty() && st.top() == popV[popi])            {                ++popi;                st.pop();            }        }        return st.empty();    }};

逆波兰表达式求值(后缀表达式)

class Solution {public:    int evalRPN(vector<string>& tokens) {        // tokens：顺序表中的每一个元素都是string        stack<int> st;// 为数字入栈准备                // 遍历顺序表        for(size_t i = 0;i < tokens.size();++i)        {            string& str = tokens[i];            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.c_str()));            }        }        return st.top();    }};

1.3 stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

Stack.h

#pragma once#include<vector>#include<list>// 一个字符也是是整数namespace bit{/*template<class T>class stack{private:T* _a;int _top;int _capacity;};*/// 设计模式// 适配器模式 -- 转换// stack<int, vector<int>> st1;// stack<int, list<int>> st2;// 模板参数和函数参数很相似，函数参数传的是对象，模板参数传的是类型// 函数的参数可以是缺省参数，模板参数也可以是缺省参数，规则类似，都是从右往左缺省template<class T, class Container = vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con.back();}private:Container _con;};}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1// container adaptor:容器适配器// 栈和队列不支持迭代器：栈：后进先出；队列：先进先出；迭代器无法满足这两个规则#include<iostream>using namespace std;#include<stack>#include<deque>#include<algorithm>#include"Stack.h"void test_stack1(){//bit::stack<int, list<int>> st;//bit::stack<int, vector<int>> st;bit::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;}int main(){test_stack1();return 0;}

二、queue的介绍和使用

2.1 queue的介绍

queue的介绍文档

翻译：

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

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

empty：检测队列是否为空size：返回队列中有效元素的个数front：返回队头元素的引用back：返回队尾元素的引用push_back：在队列尾部入队列pop_front：在队列头部出队列标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2.2 queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

2.3 queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue， 具体如下：

#include <list>namespace bite{template<class 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:std::list<T> _c;};}

三、priority_queue的介绍和使用

3.1 priority_queue的介绍

priority_queue的文档介绍

翻译：

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问，并支持以下操作：

empty()：检测容器是否为空size()：返回容器中有效元素个数front()：返回容器中第一个元素的引用push_back()：在容器尾部插入元素pop_back()：删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指 定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。

3.2 priority_queue的使用

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

函数声明	接口说明
priority_queue()/priority_queue(frist,last)	构造一个空的优先级队列
empty()	检测优先级队列是否为空，是返回true，否则返回 false
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

3.3 priority_queue的模拟实现

Priority_queue.h

namespace bit{// less仿函数：自定义类型template<class T>class less // 小于控制大堆{public:bool operator()(const T& x, const T& y){return x < y;}};// greater仿函数：自定义类型template<class T>class greater // 大于控制小堆{public:bool operator()(const T& x, const T& y){return x > y;}};// 我们让这里的模板函数的第三个参数默认和库里的一样，是小于，来控制大堆template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;// 类型创建对象，函数对象int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])// 对象可以像函数一样的去使用；通过第三个参数，来调用对应的仿函数来控制大堆和小堆if (com(_con[parent], _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//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();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};}

Test.cpp

// 优先级队列：不是队列void test_priority_queue1(){// 按优先级取数据// 默认大的优先级高，底层是个大堆//priority_queue<int> pq;//bit::priority_queue<int, deque<int>> pq;//bit::priority_queue<int, vector<int>> pq;// 大堆//bit::priority_queue<int> pq;// 小堆bit::priority_queue<int, vector<int>, bit::greater<int>> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);pq.push(7);pq.push(8);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;// 仿函数//vector<int> v = { 3,1,7,4,6,3 }; 升序//sort(v.begin(), v.end());//for (auto e : v)//{//cout << e << " ";//}//cout << endl; 降序 >(降序我们用的是大于符号，但是第三个参数不能用大于符号，要用仿函数)greater<int> gt;sort(v.begin(), v.end(), gt);//sort(v.begin(), v.end(), greater<int>());// 第三个参数为匿名对象//for (auto e : v)//{//cout << e << " ";//}//cout << endl;}int main(){test_priority_queue2();//Less<int> lessfunc;//cout << lessfunc(1, 2) << endl;//cout << lessfunc.operator()(1, 2) << endl;//cout << Less<int>()(1, 2) << endl;// Less():匿名对象//cout << Less<int>().operator()(1, 2) << endl;return 0;}

3.4 看一下Date类的priority_queue的模拟实现

情况一：

priority_queue.h

namespace bit{// less仿函数：自定义类型template<class T>class less // 小于控制大堆{public:bool operator()(const T& x, const T& y){return x < y;}};// greater仿函数：自定义类型template<class T>class greater // 大于控制小堆{public:bool operator()(const T& x, const T& y){return x > y;}};// 我们让这里的模板函数的第三个参数默认和库里的一样，是小于，来控制大堆template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;// 类型创建对象，函数对象int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])// 对象可以像函数一样的去使用；通过第三个参数，来调用对应的仿函数来控制大堆和小堆if (com(_con[parent], _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//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();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};}

Test.cpp

class Date{public:friend ostream& operator<<(ostream& _cout, const Date& d);Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}void test_priority_queue2(){bit::priority_queue<Date, vector<Date>, bit::greater<Date>> pq;Date d1(2024, 4, 8);pq.push(d1);pq.push(Date(2024, 4, 10));pq.push({ 2024, 2, 15 });// 隐式类型转换，中间要生成临时对象；多参数的构造函数，用花括号括起来，支持隐式类型的转换while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue2();return 0;}

情况二：

Priority_queue.h

namespace bit{// 我们让这里的模板函数的第三个参数默认和库里的一样，是小于，来控制大堆template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;// 类型创建对象，函数对象int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])// 对象可以像函数一样的去使用；通过第三个参数，来调用对应的仿函数来控制大堆和小堆if (com(_con[parent], _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//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();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};}

Test.cpp

class Date{public:friend ostream& operator<<(ostream& _cout, const Date& d);Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}// GreaterPDate仿函数class GreaterPDate{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};void test_priority_queue2(){// Date*不能进行运算符的重载；运算符重载必须是对自定义类型；不能对内置类型进行重载bit::priority_queue<Date*, vector<Date*>, GreaterPDate> pqptr;pqptr.push(new Date(2024, 4, 14));pqptr.push(new Date(2024, 4, 11));pqptr.push(new Date(2024, 4, 15));while (!pqptr.empty()){cout << *(pqptr.top()) << " ";pqptr.pop();}cout << endl;}int main(){test_priority_queue2();return 0;}

四、容器适配器

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的缺陷

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

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

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

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

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不仅效率高，而且内存使用率高。

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

反向迭代器和正向迭代器的不同点在哪？

功能类似，++和--方向不一样。

本来每个容器都要写一个反向迭代器的类，但是自己写，太费劲了。本质写一个反向迭代器的类模板，给编译器传不同容器的正向迭代器实例化，编译器帮助我们实例化出各种容器的对应反向迭代器。

迭代器性质分类：

单向 -----> forward_list（++）、双向 -----> list（++/--）、随机 -----> vector/deque（++/--/+/-）

迭代器功能上的分类：正向、反向、const

---

总结

好了，本篇博客到这里就结束了，如果有更好的观点，请及时留言，我会认真观看并学习。
不积硅步，无以至千里；不积小流，无以成江海。

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-23/161517.html，文章来源：网络cs，作者：利杜鹃，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！