Simulate stack using 2 queues for fun. C++ Solution.


  • 0
    class Stack {
    private:
        queue<int> ql, qr;//1. a empty queue + (a empty queue or nonempty queue)
    public:
        //2. pouring from maybe_non_empty_queue to the empty one except the last one.
        void pouring(queue<int>& q, queue<int>& maybe_non_empty_queue){
            while(maybe_non_empty_queue.size() > 1){
                q.push(maybe_non_empty_queue.front());
                maybe_non_empty_queue.pop();
            }
        }
        
        // Push element x onto stack.
        void push(int x) {
            if(!ql.empty()) ql.push(x);
            else qr.push(x);
        }
    
        // Removes the element on top of the stack.
        void pop() {
            if(!ql.empty()) swap( ql, qr);
            pouring( ql, qr);
            qr.pop();
        }
    
        // Get the top element.
        int top() {
            return ql.empty()?qr.back():ql.back();
        }
    
        // Return whether the stack is empty.
        bool empty() {
            return ql.empty() && qr.empty();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.