[剑指offer][05]用两个栈实现队列

题目描述：

· 用两个栈来实现一个队列，完成队列的入队（push）和出队（pop）操作。 队列中的元素为int类型。

解题思路：

· stack1用于存压入（push），stack2用于弹出（pop）。

入队（push）

· 直接stack1.push(node)就可以。

出队（pop）：

· 如果stack2为空，就将stack1里的元素依次压入stack2（这样就把最后入队【栈1的栈顶】的元素压在【栈2的栈底】，先入队的【栈1的栈底】的元素放在【栈2的栈顶】，先进先出），弹出stack2栈顶元素；如果stack2不为空，说明先入队的元素还没有全部出队，直接弹出stack2栈顶元素即可。

代码实现

思路1：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int top;
        //如果stack2为空，从stack1中所有元素依次弹出压入stack2
        if(!stack2.size()){
            while(stack1.size()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        //每次弹出stack2的最顶部元素
        top=stack2.top();
        stack2.pop();
        return top;            
    }

private:
    stack<int> stack1;    //用于push
    stack<int> stack2;    //用于pop
};