Java: Implement Queue using Stacks

Thought Process

To implement a queue using stacks, we use two stacks: st1 and st2. The 'push' operation directly adds elements to st1. For 'pop' and 'peek', we transfer all elements from st1 to st2 to reverse their order, allowing us to access the front of the queue. After performing the operation, we transfer elements back to st1 to maintain the correct order for future operations. The 'empty' operation simply checks if st1 is empty. 

class MyQueue {

    Stack<Integer> st1;
    Stack<Integer> st2;
    public MyQueue() {
        
        st1 = new Stack<>();
        st2 = new Stack<>();
    }
    
    public void push(int x) {
        st1.push(x);
    }
    
    public int pop() {
        
        while(!st1.isEmpty()){
            st2.push(st1.pop());
        }
        int ans = st2.pop();
        while(!st2.isEmpty()){
            st1.push(st2.pop());
        }
        return ans;
    }
    
    public int peek() {
        while(!st1.isEmpty()){
            st2.push(st1.pop());
        }
        int ans = st2.peek();
        while(!st2.isEmpty()){
            st1.push(st2.pop());
        }
        return ans;
    }
    
    public boolean empty() {
        return st1.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Code Complexity

Time Complexity: O(n)

The pop and peek operations involve transferring elements between two stacks, making them linear in time complexity.

Space Complexity: O(n)

The two stacks together store up to 'n' elements, where 'n' is the number of elements in the queue.

Code copied!