题解 | #用两个栈实现队列#

//这题比较容易就能想到利用栈的先进后出的特性，来在入队时放进栈1，出队时弹到栈2里，将“后出”通过栈的先进后出的特性给逆序成“先出”。
//唯一的问题在于什么时候弹。这个我自己想的时候没考虑好。看了题解说“栈2里还有东西时就pop栈2，没东西时才把栈1里的挨个弹到栈2里”。而且分析下来，每个元素最多进栈2出栈2一次，所以看起来是每个元素出队时都需要遍历栈1中其他元素，好像是O(n)的时间复杂度，而实际上平均下来只有O(1)。
#include <climits>
class Solution {
  public:
    void push(int node) {
        stack1.push(node);
    }

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

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