Stack <=> Queue Java solution with explanations


  • 0
    K
    class MyStack {
        // Push element x onto stack.
        Queue<Integer> q = new LinkedList<>();
        // the element is added to the tail of the queue
        // in order to simulate the stack where new element is added to the front
        // after the new element is added, move all the elements in front of it to its behind
        public void push(int x) {
            q.add(x);
            for(int i = 1; i < q.size(); i++){
                int temp = q.poll();
                q.add(temp);
            }
        }
    
        // Removes the element on top of the stack.
        public void pop() {
            q.remove();
        }
    
        // Get the top element.
        public int top() {
            return q.peek();
        }
    
        // Return whether the stack is empty.
        public boolean empty() {
            return q.isEmpty();
        }
    }
    
    class MyQueue {
        // Push element x to the back of queue.
        // use two stacks
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        // s1 is only used for storing elements
        // s2 is used for output
        // first, new element is pushed into s1
        public void push(int x) {
            s1.push(x);
        }
        // Removes the element from in front of queue.
        // since the element is layed on the top, we need to 
        // simulate the queue in which it is added to the tail
        // for example, the input sequence is 1,2,3,4, the ideal queue is 1,2,3,4
        // after pushing, the s1 shows like
        //      |  4  |
        //      |  3  |
        //      |  2  |
        //      |  1  |
        // pop the element one by one from s1 and push into s2, now s2 looks like
        //      |  1  |
        //      |  2  |
        //      |  3  |
        //      |  4  |
        // now pop from s2 we get 1, which gives the same result as poping from the queue 1,2,3,4
        public void pop() {
            if(s2.isEmpty()){
                while(!s1.isEmpty()){
                    s2.push(s1.pop());
                }
            }
            s2.pop();
        }
        // the peek is the same as pop
        // Get the front element.
        public int peek() {
            if(s2.isEmpty()){
                while(!s1.isEmpty()){
                    s2.push(s1.pop());
                }
            }
            return s2.peek(); 
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return (s1.isEmpty() && s2.isEmpty());
        }
    }

Log in to reply
 

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