Definition
- Queue from two stacks – push to an input stack; dequeue from an output stack, transferring only when the output is empty, for amortized O(1).
- Stack from one queue – on push, add the element then rotate all earlier elements behind it, making push O(n) and pop/top O(1).
- Lazy transfer – transfer only when the output stack is empty; eager transfer breaks ordering and complexity.
- Inter-convertibility – stacks and queues can simulate each other, proving neither is strictly more powerful.
- Practical use – the two-stack queue appears as the Banker's queue in functional data structures.
At the National Bank of India token counter, a queue is first-come-first-served, but the clerk only has two trays (stacks). When the serving tray is empty, she flips the intake tray into the serving tray, reversing order so the oldest is on top. For the reverse problem, she has a waiting line (queue) and fakes LIFO by rotating the line on every new arrival so the newest is always at the front.
Understanding the Concepts
How do you build a queue from two stacks?
Keep an input stack and an output stack. Enqueue pushes to input. Dequeue checks output; if empty, pour input into output (reversing order), then pop output.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class QueueViaStacks<T> {
private final Deque<T> in = new ArrayDeque<>();
private final Deque<T> out = new ArrayDeque<>();
public void enqueue(T item) { in.push(item); }
public T dequeue() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
return out.pop();
}
public boolean isEmpty() { return in.isEmpty() && out.isEmpty(); }
public static void main(String[] args) {
QueueViaStacks<String> q = new QueueViaStacks<>();
q.enqueue("A"); q.enqueue("B"); q.enqueue("C");
System.out.println(q.dequeue()); // A
System.out.println(q.dequeue()); // B
q.enqueue("D");
System.out.println(q.dequeue()); // C
System.out.println(q.dequeue()); // D
}
}
A
B
C
D
How do you build a stack from one queue?
On push, add the element to the queue, then rotate by polling and re-offering all earlier elements. The newest element ends up at the front, so poll gives LIFO order.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Queue;
public class StackViaQueue<T> {
private final Queue<T> q = new ArrayDeque<>();
public void push(T item) {
int size = q.size();
q.offer(item);
for (int i = 0; i < size; i++) q.offer(q.poll());
}
public T pop() { return q.poll(); }
public T top() { return q.peek(); }
public boolean isEmpty() { return q.isEmpty(); }
public static void main(String[] args) {
StackViaQueue<String> s = new StackViaQueue<>();
s.push("Bottom"); s.push("Middle"); s.push("Top");
System.out.println(s.pop()); // Top (LIFO)
System.out.println(s.pop()); // Middle
}
}
Top
Middle
What is the amortized analysis for the two-stack queue?
Each element: 1 push to input (O(1)), 1 transfer to output (O(1) amortized), 1 pop from output (O(1)). Total per element = O(1). One dequeue may trigger an O(n) transfer, but it happens at most once per element.
package com.bank.core;
public class AmortizedExplanation {
public static void main(String[] args) {
System.out.println("Per element: push(1) + transfer(1) + pop(1) = O(1)");
System.out.println("One dequeue may cost O(n), but rare and amortized out");
}
}
Per element: push(1) + transfer(1) + pop(1) = O(1)
One dequeue may cost O(n), but rare and amortized out
What are the complexity comparisons?
The two-stack queue has amortized O(1) for both operations. The queue-based stack has O(n) push and O(1) pop. There is no way to get both operations constant for the queue-to-stack direction.
package com.bank.core;
public class ComplexityTable {
public static void main(String[] args) {
System.out.println("Queue from 2 stacks:");
System.out.println(" enqueue: O(1), dequeue: amortized O(1)");
System.out.println("Stack from 1 queue:");
System.out.println(" push: O(n), pop: O(1)");
}
}
Queue from 2 stacks:
enqueue: O(1), dequeue: amortized O(1)
Stack from 1 queue:
push: O(n), pop: O(1)
Why is lazy transfer critical?
Transferring only when the output stack is empty ensures elements move once. Eager transfer mixes newly enqueued items with older ones already in the output stack, breaking FIFO order.
package com.bank.core;
public class LazyTransferRule {
public static void main(String[] args) {
System.out.println("Lazy: transfer only when output empty");
System.out.println(" Each element moves exactly once -> amortized O(1)");
System.out.println("Eager: transfer on every dequeue");
System.out.println(" New items mixed with old -> FIFO broken, O(n) every time");
}
}
Lazy: transfer only when output empty
Each element moves exactly once -> amortized O(1)
Eager: transfer on every dequeue
New items mixed with old -> FIFO broken, O(n) every time
What are common mistakes?
Eager transfer is the primary bug. Checking only one stack in isEmpty() is another. Using these constructions in production Java when ArrayDeque is available is a third.
package com.bank.core;
public class InterconvertMistakes {
public static void main(String[] args) {
System.out.println("Mistake 1: eager transfer -> breaks order");
System.out.println("Mistake 2: isEmpty checks only one stack");
System.out.println("Mistake 3: using this in production instead of ArrayDeque");
}
}
Mistake 1: eager transfer -> breaks order
Mistake 2: isEmpty checks only one stack
Mistake 3: using this in production instead of ArrayDeque
How is this applied in banking?
At the National Bank of India, a constrained teller component exposed only stack primitives. Customer service requests needed oldest-first fairness. The two-stack queue gave FIFO semantics with amortized O(1) serving, so a single occasional bulk transfer never hurt throughput.
package com.bank.service;
public class TellerDemo {
public static void main(String[] args) {
QueueViaStacks<String> teller = new QueueViaStacks<>();
teller.enqueue("Rajesh: balance inquiry");
teller.enqueue("Priya: loan application");
teller.enqueue("Pankaj: card replacement");
System.out.println("Serving: " + teller.dequeue());
System.out.println("Serving: " + teller.dequeue());
System.out.println("Serving: " + teller.dequeue());
}
}
Serving: Rajesh: balance inquiry
Serving: Priya: loan application
Serving: Pankaj: card replacement
What should a senior engineer know?
The two-stack queue is the Banker's queue in functional data structures, where two lists serve as the two stacks. The key interview insight is amortized analysis: worst-case O(n) per call does not mean O(n) average. Stacks and queues are inter-convertible, proving neither is strictly more powerful.
package com.bank.core;
public class SeniorInterconvert {
public static void main(String[] args) {
System.out.println("Functional: Banker's queue = two lists");
System.out.println("Key: amortized O(1) despite worst-case O(n)");
System.out.println("Result: stacks and queues are inter-convertible");
System.out.println("Production: just use ArrayDeque");
}
}
Functional: Banker's queue = two lists
Key: amortized O(1) despite worst-case O(n)
Result: stacks and queues are inter-convertible
Production: just use ArrayDeque
Visual Overview
Queue from Two Stacks ───────────────────── enqueue A, B, C: Input: [C,B,A] Output: [] dequeue → output empty → transfer: Input: [] Output: [A,B,C] pop A (FIFO) Stack from One Queue ───────────────────── push A: queue=[A] push B: queue=[B,A] (rotated) push C: queue=[C,B,A] (rotated) pop → C (LIFO)
Key Takeaway
Two stacks make a queue by lazy transfer: push to an inbox, pour into an outbox only when the outbox is empty, and the reversal gives FIFO order. Each element moves between stacks at most once, giving amortized O(1). One queue makes a stack by rotating all earlier elements behind each new arrival, making push O(n) and pop O(1).
The lazy transfer rule is what makes the two-stack queue efficient. Eager transfer on every dequeue breaks both the ordering and the amortized guarantee. The distinction between worst-case O(n) for one call and amortized O(1) over all operations is the real point interviewers test.
The two-stack queue is practically useful and appears as the Banker's queue in functional data structures. The queue-based stack is mostly an interview exercise because one operation is always linear. Together they prove stacks and queues are inter-convertible.
In my project at the National Bank of India, a constrained teller component used only stack primitives, but customer requests needed FIFO fairness. The two-stack queue delivered correct ordering with amortized O(1) throughput.
Remember one sentence: two stacks make a queue with lazy transfer for amortized O(1), and a queue makes a stack by rotating the newest to the front for O(n) push.
---