C++solution using two stack ,average O(1) time


  • 7
    Z

    every elements at most 4 operation type,push in the si stack ,pop from the si stack,push in the so stack,pop from the stack,for one elements,each operation at most once,so the average time of one operation for the queue is O(1)

    class Queue {
    public:
        // Push element x to the back of queue.
        stack<int> si;
        stack<int> so;
        int n;
        Queue(){
            n=0;
        }
        void push(int x) {
            n++;
            si.push(x);
        }
    
        // Removes the element from in front of queue.
        void pop(void) {
            n--;
            if(!so.empty()){
                so.pop();
            }
            else{
                int l=si.size();
                for(int i=0;i<l;i++){
                    so.push(si.top());
                    si.pop();
                }
                so.pop();
            }
        }
    
        // Get the front element.
        int peek(void) {
            if(!so.empty()){
                return so.top();
            }
            else{
                int l=si.size();
                for(int i=0;i<l;i++){
                    so.push(si.top());
                    si.pop();
                }
                return so.top();
            }
        }
    
        // Return whether the queue is empty.
        bool empty(void) {
            return(n==0);
        }
    };

  • 2
    R

    similar idea just make the code more easier to read.

    class Queue {
    public:
        // Push element x to the back of queue.
        void push(int x) {
    		m_stack_back.push(x);
        }
    
        // Removes the element from in front of queue.
        void pop(void) {
    		if(m_stack_front.empty())
    			this->move_back_2_front();
    		m_stack_front.pop();
        }
    
        // Get the front element.
        int peek(void) {
    		if(m_stack_front.empty())
    			this->move_back_2_front();
    
    		return m_stack_front.top();
        }
    
        // Return whether the queue is empty.
        bool empty(void) {
    		return m_stack_back.empty() && m_stack_front.empty();
        }
    private:
    	void move_back_2_front(){
    		while(!m_stack_back.empty()){
    			m_stack_front.push(m_stack_back.top());
    			m_stack_back.pop();
    		}
    	}
    private:
    	stack<int> m_stack_back;
    	stack<int> m_stack_front;
    };

Log in to reply
 

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