One Queue Java Solution


  • 19
    L
    class MyStack {
        Queue<Integer> q = new LinkedList<Integer>();
        
        // Push element x onto stack.
        public void push(int x) {
            q.add(x);
        }
    
        // Removes the element on top of the stack.
        public void pop() {
            int size = q.size();
            for(int i = 1; i < size; i++)
                q.add(q.remove());
            q.remove();
        }
    
        // Get the top element.
        public int top() {
            int size = q.size();
            for(int i = 1; i < size; i++)
                q.add(q.remove());
            int ret = q.remove();
            q.add(ret);
            return ret;
        }
    
        // Return whether the stack is empty.
        public boolean empty() {
            return q.isEmpty();        
        }
    }

  • 0
    W

    the complexity should be O(N^2) ?


  • 0
    J

    O(N) you can both insert and remove from the queue in O(1) time. So if you do that N times your total time complexity will be O(N)


  • 0
    W

    Still confused, for example:
    in pop(), every time it will do a for loop, e.g existing "1,2,3,4,5" in the queue,
    pop 5, need loop 4 times;
    pop 4, need loop 3 times, ...
    so totally need 4 + 3 + ... + 1 times, shouldn't be O(n^2)?


  • 0
    J

    Ahh, yes, if you are considering the client code that is inserting N times into the stack and them N times remove the values than yes such code is running in O(N^2) time.

    Although most of the times all you do is provide the running time of each individual method so those will be O(N) for top and pop and constant for remaining.


  • 1

  • 0
    S

    i think you can optimize this solution by caching the top value each time you pop. which will reduce the order of your top function to be O(1).


  • 0
    L

    If pop and top is not O(1), is it a Stack?


Log in to reply
 

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