方法一：
入队时，将元素压入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
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
