C++ stack与queue的使用与简单实现

 

目录

0. 适配器

1. stack的简要介绍

 2. stack的简单使用

3. queue的简要介绍

 4. queue的简单使用

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

 deque简单介绍

5. stack的模拟实现

6. queue的模拟实现

---

0. 适配器

在文章开始前我们先了解一下适配器的概念

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

1. stack的简要介绍

是一个容器适配器，提供了后进先出(或先进后出)的数据结构，其元素仅能从容器的一端插入和提取。

使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的背面出栈

 2. stack的简单使用

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

如下代码所示

#include<iostream>
#include<stack>
#include<queue>
using namespace std;int main()
{stack<int> st;st.push(1);//往栈里压入元素st.push(12);st.push(123);st.push(1234);while (!st.empty())//如果栈里没有元素了就停止循环{cout << "栈里的元素个数为: " << st.size() << "  栈顶的元素为:  " << st.top() << endl;st.pop();//删除栈里的元素，后进来的先出去，所以先删1234}return 0;
}

 输出结果如下图所示

 验证了我们所说的后入栈的先出栈，而栈顶的元素就是最后入栈的元素(如果入栈过程中没有元素提前pop出栈)。

3. queue的简要介绍

队列是一种容器适配器，专门用于先进先出中操作，从容器一端插入元素，另一端提取元素。

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

 4. queue的简单使用

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

标准容器类deque和list满足了这些要求，如果我们没为queue实例化指定容器类(没使用下方定义)，则其默认使用deque。

queue<int,list<int>> qu;

代码如下

#include<iostream>
#include<stack>
#include<queue>
#include<list>
using namespace std;int main()
{//queue<int,list<int>> qu;queue<int> qu;qu.push(1);//元素入队qu.push(12);qu.push(123);qu.push(1234);while (!qu.empty())//如果队列里里没有元素了就停止循环{cout << "队列里的元素个数为: " << qu.size() << "  队头的元素为:  " << qu.front()<<"  队尾的元素为:  " << qu.back()<< endl;qu.pop();//删除队列里的元素，先进来的先出去，所以先删1}return 0;
}

输出结果如下

可以直观的看到，先入队的队头元素先出队了，后入队的队尾元素后出队 

---

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

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

 deque简单介绍

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

 其并不是真正的连续的空间，而是由一段段连续的小空间拼接而成，实际deque类似一个动态的二维数组

双端队列底层是一段假想的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，就交给deque的迭代器了，所以deque的迭代器设计就比较复杂

迭代器元素与功能大致有

1. cur :用来遍历当前数组

2. first :指向一个数组的头

3. last :指向一个数组的尾

4. node :指向一个数组

 优：

1. 与vector相比：头插(如果前面没有空间了，就在前面再开一个数组，将元素插入新开辟数组的最后的位置)和尾删时，不需要搬移元素，效率特别高，而且在扩容时也不需要搬移大量的元素，因此效率比vector高
2. 与list相比：其底层有连续空间，空间利用率比较高，不需要存储额外字段

劣：

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

5. stack的模拟实现

默认使用deque的原因

1. 头插头删效率极高，又不需要遍历

 2. 扩容不用搬移元素，比vector强

实现非常简单，我们用容器自带的接口来实现即可

#include<iostream>
#include<deque>
#include<list>
#include<vector>
using namespace std;
namespace Pc
{//template<class T, class container = vector<T> >//template<class T, class container = list<T> >template<class T, class container = deque<T> >class stack{public:stack(){}void push(const T& x){_sta.push_back(x);}void pop(){_sta.pop_back();}T& top(){return _sta.back();//传最后的引用返回}const T& top() const{return _sta.back();//传最后的引用返回}size_t size() const{return _sta.size();}bool empty(){return _sta.empty();}private:container _sta;};
}

由于我们上面的push_back、pop_back、size等无论list、vector还是deque都有所以这三个容器都可以实现

6. queue的模拟实现

默认使用deque的原因

1. 依然是不需要遍历，只需要尾插头删(vector没有头删)

2. deque元素在内存中相对集中，减少了缓存未命中的次数，提高程序运行效率。list元素太过分散，缓存命中率低

 实现代码如下

#include<iostream>
#include<deque>
#include<list>
#include<vector>
using namespace std;
namespace Pc
{//template<class T, class container = list<T> >template<class T, class container = deque<T> >class queue{public:queue(){}void push(const T& x){_que.push_back(x);}void pop(){_que.pop_front();}T& back(){return _que.back();//传最后的引用返回}const T& back() const{return _que.back();//传最后的引用返回}T& front(){return _que.front();//传最后的引用返回}const T& front() const{return _que.front();//传最后的引用返回}size_t size() const{return _que.size();}bool empty(){return _que.empty();}private:container _que;};
}

---

这篇就到这里啦~（づ￣3￣）づ╭❤～