【C++】11. stack和queue

文章目录

• 一、stack的介绍和使用
• • 1、stack的介绍
  • 2、stack的使用
  • 3、练习
  • 4、stack的模拟实现
  • • 1）Stack.h
    • 2）Test.cpp
• 二、queue的介绍和使用
• • 1、queue的介绍
  • 2、queue的使用
  • 3、queue的模拟实现
  • • 1）Queue.h
    • 2）Test.cpp
• 三、priority_queue的介绍和使用
• • 1、priority_queue的介绍
  • 2、仿函数
  • 3、priority_queue的使用
  • 4、priority_queue的模拟实现
  • • 1）PriorityQueue.h
    • 2）Test.cpp
• 四、容器适配器
• • 1、什么是适配器
  • 2、STL标准库中stack和queue的底层结构
  • 3、deque的简单介绍
  • • 1）deque的原理介绍
    • 2）deque的缺陷
    • 3）deque排序的效率
  • 4、为什么选择deque作为stack和queue的底层默认容器

一、stack的介绍和使用

1、stack的介绍

stack的文档介绍

2、stack的使用

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

示例如下：

#include#includeusing namespace std;int main(){stack<int> st;st.push(1);//入栈st.push(2);st.push(3);st.push(4);st.pop();//出栈cout << st.size() << endl;//元素个数cout << st.top() << endl;//栈顶元素cout << st.empty() << endl;//检查是否为空//遍历while (!st.empty()){cout << st.top() << \" \";st.pop();}cout << endl;return 0;}

运行结果：

3、练习

我们使用stack的接口在这里完成两道练习题：

最小栈

分析：在这里可以通过创建两个栈来实现。

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

栈的弹出压入序列

分析：

class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> st; size_t popi = 0; for (auto& e : pushV) { //入栈序列入栈 st.push(e); //栈顶数据与出栈序列匹配 while (!st.empty() && st.top() == popV[popi]) { st.pop(); ++popi; } } return st.empty(); }};

4、stack的模拟实现

1）Stack.h

#pragma once#includenamespace zsy{template<class T, class Container = std::deque<T>>//默认容器dequeclass 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;};}

2）Test.cpp

#include#includeusing namespace std;#include\"Stack.h\"namespace zsy{void test1(){stack<int, vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4); cout << st.size() << endl;while (!st.empty()){cout << st.top() << \" \";st.pop();}}}

运行结果：

二、queue的介绍和使用

1、queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   • empty：检测队列是否为空
   • size：返回队列中有效元素的个数
   • front：返回队头元素的引用
   • back：返回队尾元素的引用
   • push_back：在队列尾部入队列
   • pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
   

2、queue的使用

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

示例如下：

#include#includeusing namespace std;int main(){queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.size() << endl;while (!q.empty()){cout << q.front() << \" \";q.pop();}return 0;}

运行结果：

3、queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list或者deque来模拟实现queue，这里采用deque。

1）Queue.h

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

2）Test.cpp

#include#includeusing namespace std;#include\"Queue.h\"namespace zsy{void test2(){queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.size() << endl;cout << q.back() << endl;while (!q.empty()){cout << q.front() << \" \";q.pop();}}}

运行结果：

三、priority_queue的介绍和使用

1、priority_queue的介绍

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来自动完成此操作。

2、仿函数

仿函数：本质是一个类，这个类重载operator()，他的对象可以像函数一样使用。
可以在排序时自主控制升序或降序。

#includeusing namespace std;//仿函数template<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class Greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class Compare>void BubbleSort(int* a,int n,Compare com){for (int j = 1; j < n; j++){//单趟int flag = 0;for (int i = 0; i < n - j; i++){if (com(a[i], a[i + 1]))//coma[i] < a[i+1] 降序{int temp = a[i];a[i] = a[i + 1];a[i + 1] = temp;flag = 1;}}if (flag == 0){break;}}}int main(){//实例化出对象再调用Less<int> LessFunc;Greater<int> GreaterFunc;int a[] = { 9,1,2,5,7,4,6,3 };;BubbleSort(a, 8, LessFunc);//降序BubbleSort(a, 8, GreaterFunc);//升序//匿名对象直接调用BubbleSort(a, 8, Less<int>());//降序BubbleSort(a, 8, Greater<int>());//升序for (auto e : a){cout << e << \" \";}cout << endl;return 0;}

运行结果：

3、priority_queue的使用

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

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

示例如下：

#include#include#include using namespace std;int main(){vector<int> v{ 1, 2, 3, 4, 5 };priority_queue<int> pq(v.begin(), v.end());//pq.push(5);//pq.push(2);//pq.push(4);//pq.push(3);//pq.push(1);cout << pq.size() << endl;while (!pq.empty()){cout << pq.top() << \" \";pq.pop();}return 0;}

运行结果：

注意：

1. 默认情况下，priority_queue是大堆。

#include #include #include //greater算法的头文件int main(){//默认建大堆vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1(v.begin(), v.end());cout << q1.top() << endl;//如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;return 0;}

运行结果：

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

#include#include#include using namespace std;class Date{public: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);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << \"-\" << d._month << \"-\" << d._day;return _cout;}private:int _year;int _month;int _day;};class DateGreater{public:bool operator()(Date* p1, Date* p2){return *p1 > *p2;}};void TestPriorityQueue(){//默认建大堆(降序)，提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));while (!q1.empty()){cout << q1.top() << endl;q1.pop();}cout << endl;priority_queue<Date*, vector<Date*>, DateGreater> q2;//升序q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();cout << *q2.top() << endl;q2.pop();}

运行结果：

4、priority_queue的模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对堆进行通用的封装即可。

1）PriorityQueue.h

#pragma once#includetemplate<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class Greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T>class Less<T*>{public:bool operator()(T* const& x, T* const& y){return *x < *y;}};template<class T>class Greater<T*>{public:bool operator()(T* const& x, T* const& y){return *x > *y;}};namespace zsy{//默认升序(大堆)template<class T, class Container = std::vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child)//(插入){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child]))//_con[parent]<_con[child]{swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent)//(删除){Compare com;//先假设左孩子小int child = parent * 2 + 1;while (child < _con.size()){//找出较小的孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child]))//_con[parent]<_con[child]{swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_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;};}

2）Test.cpp

#include#includeusing namespace std;#include\"PriorityQueue.h\"namespace zsy{void test3(){//priority_queue pq;priority_queue<int, vector<int>, Greater<int>> pq;//默认大堆pq.push(5);pq.push(3);pq.push(1);pq.push(4);pq.push(2);cout << pq.size() << endl;while (!pq.empty()){cout << pq.top() << \" \";pq.pop();}}}

运行结果：

四、容器适配器

1、什么是适配器

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

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

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

3、deque的简单介绍

1）deque的原理介绍

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

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

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

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

2）deque的缺陷

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

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

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

3）deque排序的效率

我们在这里对比一下deque和vector的效率：

void test_op1(){srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; i++){auto e = rand() + i;dq.push_back(e);v.push_back(e);}int begin1 = clock();sort(dq.begin(), dq.end());int end1 = clock();int begin2 = clock();sort(v.begin(), v.end());int end2 = clock();printf(\"deque: %d\\n\", end1 - begin1);printf(\"vector: %d\\n\", end2 - begin2);}

运行结果：

发现vector的效率是要高于deque的，因此如果想要对deque进行排序的时候，可以先将其拷贝到vector中排序，再将排序后的数据拷贝回deque，我们可以测试一下所花的时间：

void test_op2(){srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; i++){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();//拷贝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());//拷贝回dequedq2.assign(v.begin(), v.end());int end2 = clock();printf(\"deque sort: %d\\n\", end1 - begin1);printf(\"deque copy vector sort, copy back deque: %d\\n\", end2 - begin2);}

运行结果：

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的优点，而完美的避开了其缺陷。