Java 2 solutions - push O(1), top/pop O(n) and push O(n), top/pop O(1)


  • 0
    M

    push O(1), top/pop O(n) :

    class MyStack {
        Queue<Integer> que1 = new ArrayDeque<>();
        Queue<Integer> que2 = new ArrayDeque<>();
        // Push element x onto stack.
        public void push(int x) {
            que1.add(x);
        }
    
        // Removes the element on top of the stack.
        public void pop() {
            Integer ele = move(), e2=0;
            while(!que2.isEmpty()){
                e2 = que2.poll();
                if(e2.equals(ele)) break;
                que1.add(e2);
            }
        }
        
        // Get the top element.
        public int top() {
           Integer ans = move(), e2=0;
            while(!que2.isEmpty()){
                e2 = que2.poll();
                que1.add(e2);
            }
            return ans;
        }
        
        private int move() {
            Integer ele = 0;
            while(!que1.isEmpty()){
                ele = que1.poll();
                que2.add(ele);
            }
            return ele;
        }
        
        // Return whether the stack is empty.
        public boolean empty() {
            return que1.isEmpty();
        }
    }
    

    push O(n), top/pop O(1) :

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

Log in to reply
 

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