定义:队列是先进先出,栈是先进后出。PS:队列就像排队,栈就像装箱子。
栈和队列是STL(C++标准库)中的两种数据结构。STL有多个版本,我们要知道使用的STL是哪个版本,才能知道对应的栈和队列的实现原理。
HPSTL:其他版本的C++STL一般是以HPSTL为蓝本实现的,HPSTL是C++STL的第一个实现版本,而且开放源代码。P.J.PlaugerSTL:由P.J.Plauger参照HPSTL实现,被VisualC++编译器所采用,不是开源的。SGISTL:由SiliconGraphicsComputerSystems公司参照HPSTL实现,被Linux的C++编译器GCC所采用,SGISTL是开源软件,源码可读性很高。
接下来介绍的栈和队列就是SGISTL中的数据结构,知道了STL版本,才知道对应的底层实现。
栈提供了push和pop等接口,所有元素必须符合先进后出的规则
,
所以栈不提供走访功能,
也不提迭代器(iterator),不像set或者map提供迭代器iterator来遍历所有元素。
栈使用底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的,也就是说,
我们可以控制使用哪种容器来实现栈的功能。
所以STL中的栈往往不被归类为容器,而被归类为containeradapter(容器适配器)。那么STL中的栈是用什么容器实现的呢?
栈的底层实现可以是vector、deque、list,主要是数组和链表的底层实现
。
力扣题号:.用栈实现队列。
使用两个栈实现队列的功能:
pop():弹出队头元素。peek():获取队头元素。push():从队尾添加元素。empty():队列是否为空。
这是一道模拟题,不涉及具体算法,考查的就是对栈和队列的掌握程度。
使用栈模拟队列的行为,仅用一个栈是不行的,所以需要两个栈,一个是输入栈,另一个是输出栈,这里要注意输入栈和输出栈的关系。
在push数据的时候,只要将数据放进输入栈即可。
但在pop数据的时候,操作就复杂一些,如果输出栈为空,则把进栈数据全部导入输出栈。
1
如果输出栈不为空,则直接从输出栈中弹出数据即可。
如何判断队列为空呢?如果输入栈和输出栈都为空,则说明模拟的队列为空了。
pop()和peek()两个函数的功能类似,在代码实现上也是类似的,可以思考如何复用代码。
本题的实现代码如下:
classMyQueue{public:stackintstIn;stackintstOut;MyQueue(){}voidpush(intx){stIn.push(x);}intpop(){//只有当stOut为空的时候,才从stIn中导入数据(导入stIn全部数据)if(stOut.empty()){//从stIn中导入数据直到stIn为空while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}intresult=stOut.top();stOut.pop();returnresult;}//获取队列头部元素intpeek(){intres=this-pop();//直接使用已有的pop函数stOut.push(res);//因为pop函数弹出了元素res,所以再添加回去returnres;}boolempty(){returnstIn.empty()stOut.empty();}};
可以看出peek()的实现直接复用了pop()。
在工业级别的代码开发中,最忌讳的就是实现一个功能类似的函数(这个函数的功能在其他模块中出现过),在本模块中直接复制并使用该函数的代码。
一定要懂得复用,把功能相近的函数要抽象出来,而不是频繁地复制粘贴代码,否则很容易出问题。
在工作中如果发现某个功能使用频率较高,那么把这个功能抽象为一个易用的函数或者工具类,这样可以提高工作效率。