C++ accepted solution with 2 queues.


  • 0
    Z

    This solution uses two queues: the input queue handles push with time complexity O(1) and the output queue handles pop and top with time complexity O(n). Simply speaking, an element is pushed into the input queue; when either pop or top is called, the elements in the input queue are appended to the output queue with their order being reversed and then they are swapped with the original elements in the output queue.

    class Stack 
    {
        // This input queue handles push().
        queue<int> m_inputQ;
        // This output queue handles pop() and top().
        queue<int> m_outputQ;
        
        // Recursively append elements in the input queue to the output 
        // queue with their order being reversed.
        void MoveInputToOutput(queue<int>& inputQ, queue<int>& outputQ)
        {
            if (inputQ.empty())
            {
                return;
            }
            else
            {
                int num = inputQ.front();
                inputQ.pop();
                MoveInputToOutput(inputQ, outputQ);
                outputQ.push(num);
            }
        }
        
    public:
        // Push element x onto stack.
        // Time complexity O(1).
        void push(int x) 
        {
            m_inputQ.push(x);
        }
    
        // Removes the element on top of the stack.
        // Time complexity O(n).
        void pop() 
        {
            // Move the elements in the input queue to the front of the 
            // output queue and also reverse their order.
            if (!m_inputQ.empty())
            {
                int currSize = m_outputQ.size();
                // Append the elements in the input queue to the output 
                // queue with their order being reversed.
                MoveInputToOutput(m_inputQ, m_outputQ);
                // Swap the elements in the original output queue with 
                // the elements from the input queue so that the elements 
                // from the input queue will appear at the beginning.
                for (int i = 0; i < currSize; i++)
                {
                    m_outputQ.push(m_outputQ.front());
                    m_outputQ.pop();
                }
            }
                
            m_outputQ.pop();
        }
    
        // Get the top element.
        // Time complexity O(n).
        int top() 
        {
            if (!m_inputQ.empty())
            {
                int currSize = m_outputQ.size();
                // Append the elements in the input queue to the output 
                // queue with their order being reversed.
                MoveInputToOutput(m_inputQ, m_outputQ);
                // Swap the elements in the original output queue with 
                // the elements from the input queue so that the elements 
                // from the input queue will appear at the beginning.
                for (int i = 0; i < currSize; i++)
                {
                    m_outputQ.push(m_outputQ.front());
                    m_outputQ.pop();
                }
            }
                
            return m_outputQ.front();
        }
    
        // Return whether the stack is empty.
        bool empty() 
        {
            return ((m_inputQ.empty()) && (m_outputQ.empty()));
        }
    };

Log in to reply
 

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