数据结构论坛

首页 » 分类 » 问答 » 数据结构中的栈与队列
TUhjnbcbe - 2024/10/26 15:54:00
郑华国 http://www.ykhongye.com/

定义:队列是先进先出,栈是先进后出。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()。

在工业级别的代码开发中,最忌讳的就是实现一个功能类似的函数(这个函数的功能在其他模块中出现过),在本模块中直接复制并使用该函数的代码。

一定要懂得复用,把功能相近的函数要抽象出来,而不是频繁地复制粘贴代码,否则很容易出问题。

在工作中如果发现某个功能使用频率较高,那么把这个功能抽象为一个易用的函数或者工具类,这样可以提高工作效率。

1
查看完整版本: 数据结构中的栈与队列