232. Implement Queue using Stacks

刺骨的言语ヽ痛彻心扉 2023-07-03 07:06 1阅读 0赞

Implement the following operations of a queue using stacks.

*  push(x) -- Push element x to the back of queue.
 *  pop() -- Removes the element from in front of queue.
 *  peek() -- Get the front element.
 *  empty() -- Return whether the queue is empty.

**Example:**

MyQueue queue = new MyQueue();
    
    queue.push(1);
    queue.push(2);  
    queue.peek();  // returns 1
    queue.pop();   // returns 1
    queue.empty(); // returns false

**Notes:**

*  You must use *only* standard operations of a stack -- which means only `push to top`, `peek/pop from top`, `size`, and `is empty` operations are valid.
 *  Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
 *  You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

题意：用栈（先进后出）实现队列（先进先出）。

class MyQueue {
    public:
        /** Initialize your data structure here. */
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            _input.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            if(_output.empty())
            {
                while(!_input.empty())
                {
                    _output.push(_input.top());
                    _input.pop();
                }            
            }
            int temp = _output.top();
            _output.pop();
            return temp;
        }
        
        /** Get the front element. */
        int peek() {
            if(_output.empty())
            {
                while(!_input.empty())
                {
                    _output.push(_input.top());
                    _input.pop();
                }            
            }
            return _output.top();
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return _input.empty() && _output.empty();
        }
    private:    
        stack<int> _input;
        stack<int> _output;
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */