Java easy understanding solution. Only push() takes O(n)


  • 3
    F

    The general idea is that we maintain the stack order in the queue.

    Assuming the queue "queue" already contains the stack order of previous push. Then the next push(x) operation could be divided into steps:

    1. We create a new queue "temp" and offer the value x to it.
    2. Then we offer the values in "queue" into "temp"
    3. We assign "queue" with "temp" (queue=temp)

    In this way, the queue maintains the stack order again.

    class MyStack {
    
    private Queue<Integer> queue = new ArrayDeque<>();
    
    // Push element x onto stack.
    public void push(int x) {
        Queue<Integer> temp = new ArrayDeque<>();
        temp.offer(x);
        for (int i : queue) temp.offer(i);
        queue = temp;
    }
    
    // Removes the element on top of the stack.
    public void pop() {
        queue.poll();
    }
    
    // Get the top element.
    public int top() {
        return queue.peek();
    }
    
    // Return whether the stack is empty.
    public boolean empty() {
        return queue.isEmpty();
    }
    

    }

    Hope this can help you guys!


Log in to reply
 

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