本文主要是介绍[九度1512 剑指offer7] 用两个栈实现队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。
- 输入：
-
每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。
- 输出：
-
对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。
- 样例输入：
-
3 PUSH 10 POP POP
- 样例输出：
-
10 -1
*思路1：s1、s2地位等同，需要由PUSH->POP 和POP->PUSH时来回倒一下栈，顺序就正确了。
*
* */
这样倒栈的次数多了，大大降低的了效率。在九度上，最后一个大集合不能通过。
/*思路二：不用来回倒栈*分别分析插入和删除两种情况*s1作为主，S2为辅助。* *分析删除，如果删除，s1中为逆序，s1导入s2;如果s2本身有数,说明上次导入s2的值可以依旧删除，先删S2*分析插入,不论s2是否有值，直接插入s1，没有任何问题。** 总结：删除，优先s2，没有从s1 导入。插入，直接插入s1** */#include<iostream>
#include<stack>
#include<string>using namespace std;
class popException{};template<typename T>
class Queue{
public://Queue(void);//~Queue(void);void push(const T& node);T pop();
private:stack<T> s1;stack<T> s2;
};template<typename T>
void Queue<T>::push(const T& e)
{s1.push(e);
}template<typename T>
T Queue<T>::pop(){T temp;if(s2.empty()){while(!s1.empty()){temp=s1.top();s1.pop();s2.push(temp);}}if(s2.empty())throw popException();T head=s2.top();s2.pop();return head;
}int main()
{Queue<int> Q;int val,n;string cmd;cin>>n;for(int i=0;i<n;i++){cin>>cmd;if(cmd=="PUSH"){cin>>val;Q.push(val);}if(cmd=="POP"){try{cout<<Q.pop()<<endl;}catch(popException){cout<<-1<<endl;}}}return 0;
}有一篇博客分析的不错：http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
这篇关于[九度1512 剑指offer7] 用两个栈实现队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
