剑指Offer09用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

用两个栈实现队列。

感觉有 O ( n ) O(n) O(n)但想了一会儿还是没想到，看了数据范围1e4，交了一发 O ( n 2 ) O(n^2) O(n2)的过了。

原来的想法是简单的来回倒。

题解思路

维护两个栈，一个维护插入，一个维护删除。需要删除时，可以将插入栈中的所有元素倒入删除栈中，请注意，只有删除栈是空的，它才会倒下，否则元素的顺序将被破坏。很巧妙。

class CQueue { 
             stack<int> st1, st2;  public:     CQueue()     { 
                 while (st1.size())             st1.pop();         while (st2.size())             st2.pop();     }     void appendTail(int value)     { 
                 st1.push(value);     }     int deleteHead()     { 
                 if (!st2.size()) ///只有空才能倒，顺序才能正确             while (st1.size())
            { 
        
                st2.push(st1.top());
                st1.pop();
            }
        if (!st2.size())
            return -1;
        int res = st2.top();
        st2.pop();
        return res;
    }
};