Java Solution with O(1) push


  • 0
    Y

    I used 2 queues and one boolean variable bottom to store which queue contains the bottom of the queue, and this bottom correspond to the top of the stack.

    public class MyStack {
        Queue <Integer>q1=new PriorityQueue<Integer>();
        Queue <Integer>q2=new PriorityQueue<Integer>();
        boolean bottom=true;
        /** Initialize your data structure here. */
        public MyStack() {
            
        }
        
        /** Push element x onto stack. */
        public void push(int x) {
            if(bottom)
                q1.offer(x);
            else
                q2.offer(x);
        }
        
        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            //call top() to expose the top element of the stack
            this.top();
            if(bottom)
            {   
                bottom=false;
                return q1.poll();
            }
            else
            {
                bottom=true;
                return q2.poll();
            }
        }
        
        /** Get the top element. */
        public int top() {
            if(bottom)
            {
                while(q1.size()!=1)
                q2.offer(q1.poll());
                return q1.peek();
            }
            else 
            {
                while(q2.size()!=1)
                q1.offer(q2.poll());
                return q2.peek();
            }
        }
        
        /** Returns whether the stack is empty. */
        public boolean empty() {
            return(q1.isEmpty()&&q2.isEmpty());
        }
    

    }


Log in to reply
 

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