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

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());
        }
    }
 
}