Queue Problems

Queue from 2 Stacks

This is a neat little problem that involves some fun gymnastics between LIFO and FIFO.

Breakdown

• Utilize two stacks, one for input and another for output.
• Since Stacks have a LIFO order of operations, when using two of them, it’s like we’re flipping it over which simulates FIFO. This is due to the transfer (popping and pushing) of elements between the stacks. There are some great and detailed explanations on this Stackoverflow thread.
• When popping, check if output stack is empty, if it is then transfer from input stack then pop.
• Same goes for peeking. Code:

import java.util.Stack;
 
public class QueueFrom2Stacks {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;
 
    public QueueFrom2Stacks() {
        this.inputStack = new Stack<>();
        this.outputStack = new Stack<>();
    }
 
    public void push(int x) {
        inputStack.push(x);
    }
 
    public int pop() {
        if (this.outputStack.isEmpty()) {
            transfer();
        }
        return this.outputStack.pop();
    }
 
    public int peek() {
        if (this.outputStack.isEmpty()) {
            transfer();
        }
        return outputStack.peek();
    }
 
    public boolean empty() {
        return this.outputStack.isEmpty() && this.inputStack.isEmpty();
    }
 
    private void transfer() {
        while (!inputStack.isEmpty()) {
            // reverses the elements order when moving
            outputStack.push(inputStack.pop());
        }
    }
 
}