Queue via Stacks

Implement a MyQueue class which implements a queue using two stacks.

👉 Link here to the repo to solve the problem

👌 Tips

The major difference between a queue and a stack is the order of elements. A queue removes the oldest item and a stack removes the newest item. How could you remove the oldest item from a stack if you only had access to the newest item?

We can remove the oldest item from a stack by repeatedly removing the newest item (inserting those into the temporary stack) until we get down to one element. Then, after we've retrieved the newest item, putting all the elements back. The issue with this is that doing several pops in a row will require 0 (N) work each time. Can we optimize for scenarios where we might do several pops in a row?

👊 Solution 1

This solution uses a reference to an Active and passive stack. For the inserting side of things is fairly straight forward, we just want to push onto the active stack.

For the popping it becomes a bit more difficult, for this we have to shift all the values to the passive stack pop the value and then return all of them to the passive stack.

public class MyQueue <T> {
    Stack<T> activeStack = new Stack<>();
    Stack<T> passiveStack = new Stack<>();
    
    public void insert(T item) {
        activeStack.push(item);
    }

    public T peek() {
        while (!activeStack.isEmpty()) {
            T current = activeStack.pop();
            passiveStack.push(current);
        }
        return passiveStack.peek();
    }

    public T pop() {
        if (activeStack.isEmpty()) throw new EmptyStackException();
        while (!activeStack.isEmpty()) {
            T current = activeStack.pop();
            passiveStack.push(current);
        }
        T value = passiveStack.pop();

        while (!passiveStack.isEmpty()) {
            T current = passiveStack.pop();
            activeStack.push(current);
        }
        
        return value;
    }
}

---

Question borrowed from “Cracking the coding interview”