网站建设公司推荐理由,网站系统怎么建设,如何做网站主题,网络推广的基本渠道stack和queue介绍以及模拟实现 1.stack1.1stack的介绍1.2stack的使用 2.queue2.1queue的介绍2.2queue的使用 3.容器适配器3.1什么是适配器 4.stack模拟实现5.queue的模拟实现6.deque#xff08;双端队列#xff09; 1.stack
1.1stack的介绍
stack的文档介绍
stack是一种容… stack和queue介绍以及模拟实现 1.stack1.1stack的介绍1.2stack的使用 2.queue2.1queue的介绍2.2queue的使用 3.容器适配器3.1什么是适配器 4.stack模拟实现5.queue的模拟实现6.deque双端队列 1.stack
1.1stack的介绍
stack的文档介绍
stack是一种容器适配器专门用在具有后进先出操作的上下文环境中只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。
1.2stack的使用
stack的接口现在看起来对于前面已经学过stringvectorlist已经是很简单的了。 这里就不再对接口进行详细介绍。来写几道题对stack的接口有更熟悉的使用。
最小栈 思路一 这道题大部分人的思路可能是这样的再申请一个变量每次都和插入的数据进行比较如果比新插入的数据小就更新。 思路二 申请两个栈其中一个栈记录插入最小的元素。 会初始化的那为什么会初始化呢 这个成员变量会走初始化列表对内置类型不处理对自定义类型调用它的构造函数。 那如果把这个Minstack()删掉成员变量会不会初始化 同样也是会的系统默认生成的构造函数对内置类型不处理除非给内置类型缺省值对自定义类型调用它的构造函数。
因此这里也没有析构函数。
class MinStack {
public:MinStack() {}void push(int val) {_min.push(val);//这里必须判空在前面否则_count.top()会报错if(_count.empty() || _count.top() _min.top())_count.push(val);}void pop() {if(_count.top() _min.top())_count.pop();_min.pop();}int top() {return _min.top();}int getMin() {return _count.top();}stackint _min;stackint _count;
};JZ31 栈的压入、弹出序列 思路 这道题穷举是不可能的 其实可以这样想第一个是入栈序列第二个是出栈序列如果第一个的出栈序列可以和第二个出栈序列互相匹配那不就是true了吗不能匹配return false 这里就不再演示不匹配了
写法1返回条件以push1pop1来进行判断。
class Solution {
public:bool IsPopOrder(vectorint pushV, vectorint popV) {stackint _st;int i0,j0;_st.push(pushV[i]);while(1){//相等就出栈if(!_st.empty() _st.top() popV[j]){_st.pop();j;if(j popV.size())return true;}//不相等/栈为空就入栈else {if(i pushV.size() j ! popV.size() )return false;_st.push(pushV[i]);}}}
};写法2返回条件以循环结构st栈是否为空来判断
class Solution {
public:bool IsPopOrder(vectorint pushV, vectorint popV) {stackint _st;size_t pop10;for(size_t push10;push1pushV.size();push1){_st.push(pushV[push1]);while(!_st.empty() _st.top() popV[pop1]){_st.pop();pop1;}}return _st.empty();}
}; 150. 逆波兰表达式求值 逆波兰表达式就在后缀表达式。 后缀转中缀思路 遇见操作数直接入栈遇到运算符“”-“”*“”/“出栈先出的是右操作数这是因为”-“”/要分左右。然后把结果入栈。最后栈中剩下的元素就是最终结果。 class Solution {
public:int evalRPN(vectorstring tokens) {stackint _st;for(auto str : tokens){if(str || str - || str * || str /){int right_st.top();_st.pop();int left_st.top();_st.pop();switch(str[0]){case :_st.push(leftright);break;case -:_st.push(left-right);break;case *:_st.push(left*right);break;case /:_st.push(left/right);break;default:break;}}else{//字符串转为int,stoi函数_st.push(stoi(str));}}return _st.top();}
};这里介绍一下C把字符串变成各种类型的接口
前面是把后缀变成中缀这里再提供把中缀变成后缀的思路。 申请一个存放运算符的栈 1.操作数直接输出 2.栈空时碰见运算符直接入栈栈不空时碰见运算符需要外面运算符和栈顶的运算符比较。如果栈里面运算符优先级比外面的高或者相等就一直出栈直到栈空或者碰见优先级低于外面的运算符就停止。这个时候再把外面的运算符入栈。当遍历完之后再把栈里面所有运算符依次出栈。 这个有兴趣可以写一下。 232. 用栈实现队列 提示用两个栈。一个入栈一个出栈。
2.queue
2.1queue的介绍
queue的文档介绍
队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。
2.2queue的使用 关于队列的题这里就不再讲解。 有兴趣可以写下面这道题 225. 用队列实现栈 提示用两个队列。
3.容器适配器
3.1什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。
其实到目前为止我们已经接触了两种设计模式 1.适配器模式 把已有的东西封装起来转换出你想要的东西。 2.迭代器模式 不暴露底层实现细节封装后提供统一的方式访问容器。
如果我们还是按照以往的想法实现一个栈如果是顺序栈肯定是申请一个变长数组一个size一个capacity再写一些成员函数。
templateclass T
class stack
{
public://成员函数
private:T* _a;size_t _size;size_t _capacity;
};但是stackqueue都是适配器模式我们可以不再自己写而是可以用已有的东西封装起来转换成自己想要的东西。 4.stack模拟实现
既然stack即可以用vector/list封装因此模板我们给两个参数
#includeiostream
#includevector
#includelist
using namespace std;namespace bit
{templateclass T,class containerclass stack{public://自定义类型也可以不写构造stack() {};void push(const T val){_con.push_back(val);}void pop(){_con.pop_back();}const T top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}发现stack的模拟实现就是这么简单。。。
stack用list封装也是没有问题。 有人可能会说不对啊我自己使用的stack可没有你传参这么麻烦 这里解决方法给第二个容器参数一个缺省值就行了。 5.queue的模拟实现
namespace bit
{templateclass T,class containerlistTclass queue{public:queue() {};void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();}const T front(){return _con.front();}const T back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}6.deque双端队列
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 但是deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组。
可能有人看了官方库发现我们这里和库里面使用的容器不一样。 为什么库里面用的是deque双端队列
这里就不得不提到vectorlist的缺点了
deque兼容了vector和list的优点 看起来deque这么好那我们就只学这一种容器不就好了还要学vector和list干吗但是到现在我们还是在学vector和list从这一方面就证明了deque并不是那么完美。
deque底层结构 deque底层是由多个buffer数组以及一个中控指针数组所组成。 deque这样的底层才会即支持下标随机访问又支持尾插尾删头插头删。
deque的缺点: 1.下标随机访问。 要算下标在第几个buffer在这个buffer种第几个位置因此下标随机访问有一定的时间消耗不如vector快。 2.中间插入和删除。 也有一定的时间消耗相比list中间插入删除不够极致没有list快。 虽然deque有这些缺点但是队友栈和队列是够用了。
那什么地方可以用deque双端队列呢 中间插入和删除少头尾插入删除多偶尔下标随机访问。
