剑指Offer -- 用两个栈实现队列（C++）

题目描述

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

首先了解一下两者的区别：

1. 栈先进后出，队列先进先出。
2. 对插入和删除操作的"限定"。栈是限定只能在表的一端进行插入和删除操作的线性表。队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

对于该题目，我们可以先将Push的数据放在栈1中。在利用两个栈实现队列的Pop操作时，假若此时要删除的是栈1的第一个数据（底部），应想办法将栈1的这个数据放至栈2的头部，再使用栈2的Top操作返回该数据，并用Pop操作删除该数据。
之后，如果要再次实现队列的Pop操作，先判断栈2是否为空，若不为空，那么此时直接将栈2的头部出栈即可，不用重复以上的复杂操作。

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
            int temp = stack2.top();
            stack2.pop();
            return temp;
        } else {
            int temp = stack2.top();
            stack2.pop();
            return temp;
        }
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

另外，利用同样的思维方式，也可用两个队列实现一个栈。