利用两个栈实现队列-创新互联

方法一：

入队时，将元素压入s1。

出队时，将s1的元素逐个“倒入”（弹出并压入）s2，将s2的顶元素弹出作为出队元素，之后再将s2剩下的元素逐个“倒回”s1。

方法二：

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

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

最优解：

入队时，将元素压入s1。

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

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

代码实现

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

//test1.cpp
#include "test1.h"
using namespace std;
template
queueWithTwoStack::queueWithTwoStack()
{}
template
queueWithTwoStack::~queueWithTwoStack()
{}
//加只加在S1中
template
void queueWithTwoStack::addTail(const T& data)
{
	s1.push(data);
}
//删只删S2中的
template
T queueWithTwoStack::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 qw;
	qw.addTail(1);
	qw.addTail(2);
	qw.addTail(3);
	cout< qw;
	qw.addTail(1);
	qw.addTail(2);
	qw.addTail(3);
	cout<
参考：《剑指offer》面试题7
  http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
            

            网站名称：利用两个栈实现队列-创新互联            

            网站路径：http://cqcxhl.com/article/dghhdd.html