Java solutions about three ways one of which utilizes one queue, and the others utilize two queues


  • 51
    A

    First, let's see the most easiest way: one queue.
    In this method, the point is that after you add one element to the queue, rotate the queue to make the tail be the head.

    class MyStack {
    
    //one Queue solution
    private Queue<Integer> q = new LinkedList<Integer>();
    
    // Push element x onto stack.
    public void push(int x) {
        q.add(x);
        for(int i = 1; i < q.size(); i ++) { //rotate the queue to make the tail be the head
            q.add(q.poll());
        }
    }
    
    // Removes the element on top of the stack.
    public void pop() {
        q.poll();
    }
    
    // Get the top element.
    public int top() {
        return q.peek();        
    }
    
    // Return whether the stack is empty.
    public boolean empty() {
        return q.isEmpty();
    }
    }
    

    Then, two queue ways.

    1 Push method is inefficient.

    when you push an element, choose one empty queue(whichever when both are empty) to add this element, and then push all elements of the other queue into the chosen queue. After that, the newest element is at the head of the chosen queue so that whenever you want to do pop() or top(), you always get the newest element.

    For example,

    push(1):

    [ , ,1] [ , , ]

    push(2):

    [ , , ] [ ,1,2]

    push(3):

    [ 1, 2,3 ] [ , , ]

    class MyStack {
    //using two queue. The push is inefficient.
    private Queue<Integer> q1 = new LinkedList<Integer>();
    private Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        if(q1.isEmpty()) {
            q1.add(x);
            for(int i = 0; i < q2.size(); i ++)
                q1.add(q2.poll());
        }else {
            q2.add(x);
            for(int i = 0; i < q1.size(); i++)
                q2.add(q1.poll());
        }
    }
    
    public void pop() {
        if(!q1.isEmpty()) 
            q1.poll();
        else
            q2.poll();
    }
    public int top() {
        return q1.isEmpty() ? q2.peek() : q1.peek();
    }
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    }
    

    2 pop() and top() are inefficient

    When you push elements, choose a queue which is not empty(whichever when both are empty).
    When you do pop() or top(), first pop all elements of the queue except the tail into another empty queue, and then pop the tail which is your want.

    For example:

    push(1):

    [ , , 1] [ , , ]

    push(2):

    [ ,2,1] [ , , ]

    top();

    [ , , 2] [ , ,1] -> [ , , ] [ ,2,1]

    pop():

    [ , , 1] [ , ,2] -> [ , ,1] [ , , ]

    push(3) :

    [ ,3,1] [ , , ]

    class MyStack{
    //using two queue. The pop and top are inefficient.
    private Queue<Integer> q1 = new LinkedList<Integer>();
    private Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        if(!q1.isEmpty()) 
            q1.add(x);
        else
            q2.add(x);
    }
    public void pop() {
        if(q1.isEmpty()) {
            int size = q2.size();
            for(int i = 1; i < size; i ++) {
                q1.add(q2.poll());
            }
            q2.poll();
        }else {
            int size = q1.size();
            for(int i = 1; i < size; i ++) {
                q2.add(q1.poll());
            }
            q1.poll();
        }
    }
    public int top() {
        int res;
        if(q1.isEmpty()) {
            int size = q2.size();
            for(int i = 1; i < size; i ++) {
                q1.add(q2.poll());
            }
            res = q2.poll();
            q1.add(res);
        }else {
            int size = q1.size();
            for(int i = 1; i < size; i ++) {
                q2.add(q1.poll());
            }
            res = q1.poll();
            q2.add(res);
        }
        return res;
    }
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    }

  • 0

    good summary


  • 0
    2

    Good answer with nice explanation.


  • 0
    A

    In your one stack solution, after we pop() shouldn't we rotate the queue again since the first element is removed.


  • 1
    A

    In the queue,these elements keep LIFO order so after you pop(), the current head is the second most recent inputted element. So we don't need to rotate the queue again.


  • 0
    2

    The queue is in LIFO state when it is reversed after pushing. When we pop from the queue, we merely remove the head of the queue, keeping the rest of the queue in LIFO order.
    Notice that the for loop to reverse the queue runs from 1 not 0 to size
    For example:

    push 3 ---> 3
    -> reverse: 3

    push 5 ---> 3,5
    ->reverse: 5,3

    push 2 ---> 5,3,2
    ->reverse: 2,5,3

    pop ---> 5,3

    Notice that just before and after pop, the queue is in LIFO state. So no need to reverse again after pop.


  • 0
    A

    My mistake, thought we did rotation only once before pop().


  • 0
    C
    This post is deleted!

  • 0
    C

    Nice summation.


  • 0
    X
    This post is deleted!

Log in to reply
 

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