An optimized Java solution use one queue (can be O(1) in all operation in some case).


  • 1
    P

    I use the 'popSize' to record the pop() so it's always O(1). Test if need to do 'compact' in every push or top call which can get O(1) in push or top in constantly push or top. It's an optimized to reduce constantly call However it performed not so good in LeetCode's test case :(

    class MyStack {
        // Push element x onto stack.
        private LinkedList<Integer> list = new LinkedList<Integer>();
        private Integer TOP;
        private int popSize;
        public void push(int x) {
            if (popSize > 0) {
                compact();
            }
    
            TOP = new Integer(x);
            list.offer(TOP);
        }
    
        // Removes the element on top of the stack.
        public void pop() {
            //no need to do sanity check
            popSize++;
            TOP = Integer.MIN_VALUE; //make it invalid.
        }
    
        // Get the top element.
        public int top() {
            if (TOP == Integer.MIN_VALUE) {
                compact();
            }
    
            return TOP;
        }
    
        private void compact() {
            Integer tmp = null;
            int sz = list.size();
            for (int i = 0; i < sz; i++) {
                tmp = list.poll();
                if (i < sz - popSize) {
                    list.offer(tmp);
                    TOP = tmp;
                }
            }
            popSize = 0;
        }
    
        // Return whether the stack is empty.
        public boolean empty() {
            return list.size() == popSize;
        }
    }

Log in to reply
 

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