原题链接 用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
首先总结一下队列(queue)以及栈(stack)的特性，在总结之前给大家推荐一下不错的C++中文在线手册：英文版：cppreference.com ，如果读起来费劲可以去：中文翻译：cppreference.com
-
queue：std::queue类是容器适配器，它给予程序员队列的功能--尤其是FIFO(现先进先出)数据结构。queue在底层容器尾端推入元素，从首端弹出元素。要实现的两个操作：
- push向队列尾部插入元素；
- pop删除第一个元素（题主曾经吃过的亏啊。划重点：C++中pop()无返回值,题目要求是有返回值的。）
-
stack：std::stack类是容器适配器，它给与程序员栈的功能--特别是FILO(先进后出)数据结构。栈从被称作栈顶的容器尾部推弹元素。主要的成员函数：
- top():用来访问栈顶元素；
- empty():用来检查底层的容器是否为空；
- push:用来向栈顶插入元素；
- pop():用来删除栈顶的元素；
- size():用来返回容纳的元素数。
解题思路：堆栈的特性是先进后出，队列是的特性是先进先出。分别标记两个栈为S1和S2，push操作就是往S1的入栈操作，pop操作要返回S1栈底的元素，首先要判断S2是否为空，若为空，则要先将S1的元素从栈顶到栈底全部压入S2中，然后再返回S2的栈顶元素；若S2不为空，则直接返回S2的栈顶元素。（还有一个异常判断，当S1和S2都为空时，应抛出异常）
具体代码如下：
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
class Solution {
public:
void push(int Node) {
stack1.push(Node);
}
int pop() {
if(stack1.empty() && stack2.empty()) {
throw "INPUT Valid";
}
else if (stack2.empty()) {
while (!stack1.empty()) {
int tem = stack1.top();
stack1.pop();
stack2.push(tem);
}
}
int res = stack2.top();
stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
void main() {
Solution s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.pop();
s.push(5);
s.pop();
s.pop();
s.pop();
s.pop();
s.pop();
system("pause");
}
