【C++】stack与queue的使用与模拟实现
【C++】stack与queue的使用与模拟实现
✨前言：在C++ STL中，stack和queue是两个重要的数据结构组件，它们虽然简单却非常实用。与vector、list等容器不同，它们属于容器适配器，通过封装现有容器并提供特定接口来实现栈和队列的功能。接下来，让我们一起学习一下吧！！！
📖专栏：【C++成长之旅】
目录
说在前面
对于stack与queue的学习更为简单，但是它们与前面的string、vector……还是有本质区别，string是容器（container ），stack与queue是容器适配器（container adaptor）：
是因为它在现有容器的基础上，通过限制功能、改变接口，来“适配”出栈这种特定的数据结构。
也就是说，它的底层，可以是已有的容器，比如：list、vector……
关于容器适配器我会在下篇博客中来详细阐述，敬请期待，现在让我们来学习stack与queue吧。
对于stack和queue的思想，学过数据结构的都知道了，没学过的话也可以看看【栈与队列】。
一、stack与queue使用
【stack的参考文档】
【queue的参考文档】
两者的接口都很简单，我们要不展开说明了，来简单应用一下吧。
// stack使用示例#include<stack>#include<iostream>usingnamespace std;intmain(){ stack<int> st; st.push(1); st.push(2); st.push(3);while(!st.empty()){ cout << st.top()<<" ";// 输出: 3 2 1 st.pop();}return0;}输出：3 2 1
接着就直接来看几个相对应的题吧：
题1：《用栈实现队列》
这个题很简单，但是我们要来体会C++中STL的方便，假设我们用C语言来完成的话，首先要自己实现一个栈才可以解题，但C++不需要。
参考题解：
classMyQueue{private: stack<int> inStack, outStack;voidin2out(){while(!inStack.empty()){ outStack.push(inStack.top()); inStack.pop();}}public:MyQueue(){}voidpush(int x){ inStack.push(x);}intpop(){if(outStack.empty()){in2out();}int x = outStack.top(); outStack.pop();return x;}intpeek(){if(outStack.empty()){in2out();}return outStack.top();}boolempty(){return inStack.empty()&& outStack.empty();}};有兴趣的自己也可以练练，STL我们要多使用才可以掌握，多练。
题2：《用队列实现栈》，有时间也可以练练
二、stack模拟实现
对于两者的模拟实现也很简单，前面说过，它们两者是容器适配器。
所以对于stack我们可以用vector来封装：
template<classT,classCon= std::vector<T>>classstack{public:stack()//默认构造函数{}voidpush(const T& x)//入栈操作{ _c.push_back(x);//使用底层容器的push_back}voidpop()// 出栈操作{ _c.pop_back();// 使用底层容器的pop_back} T&top(){return _c.back();}const T&top()const{return _c.back();} size_t size()const{return _c.size();}boolempty()const{return _c.empty();}private: Con _c;};怎么，是不是很简单，不要我们再像vector一样实现一个底层的结构。
三、queue模拟实现
对于queue，我们也可以用vector来封装，因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低（vector在头部删除时需要移动所有后续元素，时间复杂度为O(n)，而list的pop_front是O(1)操作。），故可以借助list来模拟实
现queue，具体如下：
template<classT,classCon= std::list<T>>classqueue{public:queue(){}voidpush(const T& x){ _c.push_back(x);}voidpop(){ _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();}boolempty()const{return _c.empty();}private: Con _c;};注意：
对于stack和queue的实现，官方的库中底层则是deque，但是鉴于我们可能不知道deque，下篇博客就会来说deque，但是实现是一样的，如果是deque，我们只需要把容器改为deque即可。
如果本文对您有启发：
✅ 点赞 -让更多人看到这篇硬核技术解析 ！
✅ 收藏 -实战代码随时复现
✅ 关注 -获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨
