import java.util.Stack;
/**
Queue implemented using two stacks in Java.
Concept:
- stackIn : receives new elements (enqueue)
- stackOut : serves elements in correct queue order (dequeue)
When stackOut is empty and we need to dequeue or peek:
- Move all elements from stackIn to stackOut
This reverses the order, making the oldest element accessible.
This design provides amortized O(1) operations and keeps the code simple.
*/
class QueueUsingStacks {
private final Stack<Integer> stackIn = new Stack<>();
private final Stack<Integer> stackOut = new Stack<>();
// Move elements from stackIn to stackOut when needed
private void transferIfNeeded() {
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
}
// Add an element to the queue
public void enqueue(int value) {
stackIn.push(value);
}
// Remove and return the front element
public int dequeue() {
transferIfNeeded();
if (stackOut.isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return stackOut.pop();
}
// Return the front element without removing it
public int front() {
transferIfNeeded();
if (stackOut.isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return stackOut.peek();
}
// Check if the queue is empty
public boolean isEmpty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
}
public class Main {
public static void main(String[] args) {
QueueUsingStacks q = new QueueUsingStacks();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
System.out.println("Front element: " + q.front()); // 10
System.out.println("Dequeued: " + q.dequeue()); // 10
System.out.println("Dequeued: " + q.dequeue()); // 20
q.enqueue(40);
System.out.println("Front element: " + q.front()); // 30
System.out.println("Dequeued: " + q.dequeue()); // 30
System.out.println("Dequeued: " + q.dequeue()); // 40
System.out.println("Queue empty: " + q.isEmpty());
}
}
/*
run:
Front element: 10
Dequeued: 10
Dequeued: 20
Front element: 30
Dequeued: 30
Dequeued: 40
Queue empty: true
*/
