首页 > 代码库 > 【数据结构】两个栈实现一个队列

【数据结构】两个栈实现一个队列

今天面试的时候被问到了,如何用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

谢谢!



【数据结构】两个栈实现一个队列