Two Queue C++ solutions with explaination


  • 0
    R

    There are two solutions:

    1. push and top run in O(1), but pop() runs in O(n)
      The idea is to keep the top element always in one queue.
      After pop this element out, we need to pop out the element in the other queue until we find the last element.
    2. make pop() runs in O(1), and push in O(n), by making one queue has the order of "LIFO"

    solution 1:

    class Stack {
    public:
        Stack(): cur(0) {}
        // Push element x onto stack.
        void push(int x) {
           if (!q[cur].empty()) {
               q[1-cur].push(q[cur].front());
               q[cur].pop();
           }
           q[cur].push(x);
        }
    
        // Removes the element on top of the stack.
        void pop(void) {
            q[cur].pop();
            while(q[1-cur].size() > 1) {
                q[cur].push(q[1-cur].front());
                q[1-cur].pop();
            }
            cur = 1-cur; // thanks to "aweyiun" to improve this line
        }
        
        // Get the top element.
        int top(void) {
            return q[cur].front();
        }
        
        // Return whether the stack is empty.
        bool empty(void) {
           return q[cur].empty();
        }
    private:
        queue<int> q[2];
        int cur;
    };
    

    solution 2:

    class Stack {
    public:
        Stack(): cur(0) {}
        // Push element x onto stack.
        void push(int x) {
           q[1-cur].push(x);
           while(!q[cur].empty()) {
               q[1-cur].push(q[cur].front());
               q[cur].pop();
           }
           cur = 1-cur;
        }
    
        // Removes the element on top of the stack.
        void pop(void) {
            q[cur].pop();
        }
        
        // Get the top element.
        int top(void) {
            return q[cur].front();
        }
        
        // Return whether the stack is empty.
        bool empty(void) {
           return q[cur].empty();
        }
    private:
        queue<int> q[2];
        int cur;
    };

  • 0
    A
    This post is deleted!

Log in to reply
 

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