首页 > 代码库 > 【数据结构】两个栈实现一个队列
【数据结构】两个栈实现一个队列
今天面试的时候被问到了,如何用2个栈实现一个队列的功能。
那时候第一时间的想法是:
用2个栈实现,入队列时,可以直接push进其中的一个栈
出队列时,则需要把入队列的那个栈不断的pop到另一个栈中,以实现原先栈的顺序逆序,从而实现队列的先进先出。
可能文字比较拗口,具体的实现可通过下图表示:
注:图片转自http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
很明显,这是一个可行性挺高的方法。但是,出队列的最后一步倒回,是否真的需要?
经过研究,其实并不需要。也就是说:
入队时,将元素压入s1。(这样,入队的时间复杂度就为O(1))
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
注意:此时并不需要在出列完将s2的元素倒回s1.这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。
后面,我用C++的模板类实现了以下的源码,经测试可以使用:
#include <IOSTREAM> #include <STACK> using namespace std; template <typename T> class MyDeque { public: MyDeque(); virtual ~MyDeque(); void myPush(const T& data); T myPop(); private: stack<T> inStack; stack<T> outStack; }; template <typename T> MyDeque<T>::MyDeque(void) { }; template <typename T> MyDeque<T>::~MyDeque(void) { }; template <typename T> void MyDeque<T>::myPush(const T& data) { inStack.push(data); }; template <typename T> T MyDeque<T>::myPop(void) { if(outStack.size() <= 0) { while (inStack.size() > 0) { outStack.push(inStack.top()); inStack.pop(); } } if( outStack.size() == 0 ) { cout << "队列为空,无法出队列" << endl; } T data = http://www.mamicode.com/outStack.top();>
测试的结果为:
可见,测试结果表明该思路是符合题目要求的。
本文由Cout_Sev 原创,部分资料搜集整理自网络
转载注明出处
http://blog.csdn.net/cout_sev
谢谢!
【数据结构】两个栈实现一个队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。