My c++ code with explanation


  • 0
    C
    class Stack {
    public:
    
        // loop invariant
        // two queues, suppose a is empty, b may be full(b.front is the last element, b.back is the first element)
        
        // push: push in a, then pop all of b in a ( the loop invariant is maintained )
        // pop: b.pop() ( the loop invariant is maintained )
        
        queue<int> a, b;
        
        void move(queue<int> &from, queue<int> &to)
        {
            while( !from.empty() )
            {
                to.push( from.front() );
                from.pop();
            }
        }
        
        // Push element x onto stack.
        void push(int x)
        {
            queue<int> &empty_queue = a.empty() ? a : b;
            queue<int> &nonempty_queue = a.empty() ? b : a;
            
            empty_queue.push(x);
            move(nonempty_queue, empty_queue);
        }
    
        // Removes the element on top of the stack.
        void pop() 
        {
            queue<int> &nonempty_queue = a.empty() ? b : a;
            if( !nonempty_queue.empty() )
                nonempty_queue.pop();
        }
    
        // Get the top element.
        int top() 
        {
            queue<int> &nonempty_queue = a.empty() ? b : a;
            return nonempty_queue.front();
        }
    
        // Return whether the stack is empty.
        bool empty() 
        {
            queue<int> &nonempty_queue = a.empty() ? b : a;
            return nonempty_queue.empty();
        }
    };

Log in to reply
 

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