Implement by using two stacks (Java)


  • 0
    I

    The queue can be seen as two part, in stack and out stack. During the run time, data was flowed between these two stacks

    . when out is empty then clean up in and transfer all its element into out.

    class MyQueue {
    // Push element x to the back of queue.
    
      Stack<Integer> in = new Stack<Integer>();
      Stack<Integer> out = new Stack<Integer>();
    
    
    public void push(int x) {
       in.push(x);
    }
    
    // Removes the element from in front of queue.
    public void pop() {
        if(this.empty() )
        return;
    
        if(out.isEmpty()){
            // when in has value and out is empty, transfer all elements from in to out
            this.inToOut();
        }
        out.pop();
    }
    
    // Get the front element.
    public int peek() {
        if(this.empty() )
        return -1;
        
        if(out.isEmpty()){
         // when in has value and out is empty, transfer all elements from in to out
            this.inToOut();
        }
        return out.peek();
    }
    
    private void inToOut(){
        // when in is not empty and out is empty, the transfer all elements from in to out
        if(!in.isEmpty() && out.isEmpty() ){
            while(!in.isEmpty()){
                out.push(in.pop() );
            }
        }
    }
    
    // Return whether the queue is empty.
    public boolean empty() {
    
        if(in.isEmpty() && out.isEmpty() ){
            return true;
        }else{
            return false;
        }
        
    }
    }

Log in to reply
 

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