C++ 0ms solution


  • 0
    D

    In this implementation, I only have one stack variable which represents the queue but in reverse order. This means that the bottom of the stack represents the front of the queue and vice-versa. Therefore, a pop operation requires emptying the entire stack while saving all its values except the bottom element which is the one we want to remove. The other values are saved in another stack and after popping the front of the queue, they're-inserted back into the original stack. The peek operation is similar but this time all values must be saved and re-inserted back.

    #include <stack>
    
    class Queue {
    public:
        
        std::stack<int> _stack;
        
        // Push element x to the back of queue.
        void push(int x) {
            
            _stack.push(x);
        }
        
    
        // Removes the element at the bottom of the stack
        void pop(void) {
            
            int front;
            queueFront(1, front);
            
        }
    
        // Get the front element.
        int peek(void) {
            
            int front;
            queueFront(0, front);
            return front;
        }
        
        // Pops or just peeks front of queue, indicated
        // by the pop flag. On pop, we want to remove front
        // of the queue or bottom of the stack so that the latter 
        // doesn't get pushed into the queue to then get 
        // re-inserted into the stack
        void queueFront(bool pop, int& front){
            
            std::stack<int> queue;
            
             // Empty stack into queue
            while(!_stack.empty()){
                
                front = _stack.top();
                _stack.pop();
                
                if(_stack.empty() && pop) break;
                
                queue.push(front);
            }
            
            // Re-insert queue values into stack
            while(!queue.empty()){
                
                _stack.push(queue.top());
                queue.pop();
            }
        }
    
        // Return whether the queue is empty.
        bool empty(void) {
            return _stack.empty();
        }
    };

Log in to reply
 

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