用两个栈实现队列

原题链接 用两个栈实现队列

题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

首先总结一下队列(queue)以及栈(stack)的特性，在总结之前给大家推荐一下不错的C++中文在线手册：英文版：cppreference.com ，如果读起来费劲可以去：中文翻译：cppreference.com

• queue：std::queue类是容器适配器，它给予程序员队列的功能--尤其是FIFO(现先进先出)数据结构。queue在底层容器尾端推入元素，从首端弹出元素。要实现的两个操作：
  1. push向队列尾部插入元素；
  2. pop删除第一个元素（题主曾经吃过的亏啊。划重点：C++中pop()无返回值,题目要求是有返回值的。）

• stack：std::stack类是容器适配器，它给与程序员栈的功能--特别是FILO(先进后出)数据结构。栈从被称作栈顶的容器尾部推弹元素。主要的成员函数：
  1. top():用来访问栈顶元素；
  2. empty():用来检查底层的容器是否为空；
  3. push:用来向栈顶插入元素；
  4. pop():用来删除栈顶的元素；
  5. 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");
}