温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

利用两个栈实现队列

发布时间:2020-07-20 19:16:40 来源:网络 阅读:285 作者:sunshine225 栏目:编程语言


方法一:

入队时,将元素压入s1

出队时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1


方法二:

入队时,先判断s1是否为空,如不为空,说明所有元素都在s1,此时将入队元素直接压入s1;如为空,要将s2的元素逐个“倒回”s1,再压入入队元素。

出队时,先判断s2是否为空,如不为空,直接弹出s2的顶元素并出队;如为空,将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。


最优解:

入队时,将元素压入s1

出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。


注意:考虑没有元素可供出队时的处理(2个栈都为空的时候,出队操作一定会引起异常)

代码实现

//test1.h
#include<iostream>
#include<stack>
using namespace std;
template<class T>
class queueWithTwoStack
{
public:
	queueWithTwoStack();
	~queueWithTwoStack();
	void addTail(const T& data);
	T deleteHead();
private:
	stack<T> s1;
	stack<T> s2;
};

//test1.cpp
#include "test1.h"
using namespace std;
template<class T>
queueWithTwoStack<T>::queueWithTwoStack()
{}
template<class T>
queueWithTwoStack<T>::~queueWithTwoStack()
{}
//加只加在S1中
template<class T>
void queueWithTwoStack<T>::addTail(const T& data)
{
	s1.push(data);
}
//删只删S2中的
template<class T>
T queueWithTwoStack<T>::deleteHead()
{
	if((s2.empty())&&(s1.empty()))
	{
		printf("is empty!\n");
		return -1;
	}
	//s2为空,把S1全倒在S2中后删
	if(s2.empty())
	{
		while(!s1.empty())
		{
			T top=s1.top();
			s1.pop();
			s2.push(top);
		}
	}
	//s2不为空直接删
	T head=s2.top();
	s2.pop();
	return head;	
}
void test1()
{
	queueWithTwoStack<int> qw;
	qw.addTail(1);
	qw.addTail(2);
	qw.addTail(3);
	cout<<qw.deleteHead()<<endl;

	cout<<qw.deleteHead()<<endl;
	cout<<qw.deleteHead()<<endl;

	//cout<<qw.deleteHead()<<endl;
}
void test2()
{
	queueWithTwoStack<int> qw;
	qw.addTail(1);
	qw.addTail(2);
	qw.addTail(3);
	cout<<qw.deleteHead()<<endl;

	qw.addTail(4);
	cout<<qw.deleteHead()<<endl;
	cout<<qw.deleteHead()<<endl;
	cout<<qw.deleteHead()<<endl;
}
int main()
{
	//test1();
	test2();
	system("pause");
	return 0;
}


参考:《剑指offer》面试题7

    http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html



向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI