Accepted Java solution: Implement stack with only one queue


  • -5
    M

    This solution adopting only one queue to store data and caching the top element to make method top time complexity constant.

    Time complexity for each method.
    push O(1)
    pop O(n)
    top O(1)
    empty O(1)

    private Queue<Integer> queue = new ArrayDeque<>();
    private Integer topElement = null; 
    
    // Push element x onto stack.
    public void push(int x) {
    	topElement = x;
        queue.offer(x);
    }
    
    // Removes the element on top of the stack.
    public void pop() {
    	Integer element = null;
        for (int i = 0, size = queue.size() - 1; i < size; i++) {
        	element = queue.poll();
        	queue.offer(element);
        }
        
        topElement = element;
        queue.poll();
    }
    
    // Get the top element.
    public int top() {
        return topElement;
    }
    
    // Return whether the stack is empty.
    public boolean empty() {
        return queue.isEmpty();
    }

  • 0
    S

    If you didn't change topElement in pop(), your top() may return incorrect number


  • 1
    W

    public void pop() {
    int size = Q.size()-1;
    for(int i=0; i<size; i++){
    topElement = Q.poll();
    Q.add(topElement);
    }
    Q.poll();
    }


  • 0
    P

    Did your solution pass the online judgement? Cause my code had the issue of cannot find top(), so I just copy your code. And the same problem was there


  • 0
    M

    Thanks to point it out. Corrected! :)


  • 0
    M

    The Online Judgement has bug for java. We have to wait until it is fixed.


  • 0
    P

    I guess so. Thanks!


  • 0

    @mikeyi: I have just fixed this issue. Please rename your class name to MyStack and submit again. It should work.


  • 0
    M

    Thanks @1337c0d3r, it worked:)


  • 0
    M
    This post is deleted!

Log in to reply
 

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