题解 | #用两个栈实现队列# 更新注释 时间复杂度是O()

class Solution
{
    // 熟悉 栈和队列的概念和性质
    // 常用的操作
public:
    void push(int node) {
        
        stack1.push(node); // 就直接进入第一个栈
        
        
    }

    int pop() {
        if(!stack2.empty()) // 若第二个栈非空 就弹出 返回
        {
            int ans = stack2.top();
            stack2.pop();
            return ans;
        }
        else // 否则 先把栈1插入的 转移到栈2  这样保证了顺序反过来 变成队列的先入先出
        {
            while(!stack1.empty())
            {
                int tmp = stack1.top();

                stack2.push(tmp);
                stack1.pop();
            }

            int ans = stack2.top();

            stack2.pop();

            return ans;
            // 对于删除操作，虽然看起来是 O(n)O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。

        }
        
    }

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