Definition
- Queue from two stacks – simulate FIFO with two LIFO stacks by pushing to an inbox and transferring to an outbox only when the outbox is empty, reversing the order so the oldest element is on top.
- Amortized O(1) – each element is pushed to inbox once, transferred to outbox once, and popped once, so the cost per element is constant over its lifetime.
- Stack from one queue – simulate LIFO by rotating the queue on every push so the newest element sits at the front, making push O(n) and pop O(1).
- Lazy transfer rule – transfer only when the outbox is empty; eager transfer on every operation breaks ordering and complexity.
- Practical relevance – the two-stack queue appears in functional data structures (Banker's queue) and constrained environments where only stacks are available.
Rajesh processes customer cheques at National Bank of India, but he only has two in-trays that behave like stacks. Customers must be served in arrival order. He drops every new cheque into the incoming tray. When he needs to serve the next customer, if the serving tray is empty he flips the whole incoming tray onto the serving tray one by one, which reverses the order so the oldest cheque is on top. He serves from the serving tray until it empties, then flips again only when needed.
Understanding the Concepts
What is the problem?
Implement a FIFO queue using only LIFO stacks. A stack reverses order on transfer, so moving everything from one stack to another flips LIFO into FIFO. The challenge is doing it efficiently, not on every operation.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class QueueFromStacks<T> {
private final Deque<T> inbox = new ArrayDeque<>();
private final Deque<T> outbox = new ArrayDeque<>();
public void enqueue(T item) {
inbox.push(item);
}
public T dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
public T peek() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.peek();
}
public boolean isEmpty() {
return inbox.isEmpty() && outbox.isEmpty();
}
public static void main(String[] args) {
QueueFromStacks<String> q = new QueueFromStacks<>();
q.enqueue("TXN-A");
q.enqueue("TXN-B");
q.enqueue("TXN-C");
System.out.println(q.dequeue()); // TXN-A (FIFO)
System.out.println(q.dequeue()); // TXN-B
q.enqueue("TXN-D");
System.out.println(q.dequeue()); // TXN-C
System.out.println(q.dequeue()); // TXN-D
}
}
TXN-A
TXN-B
TXN-C
TXN-D
Why does transferring between stacks reverse the order?
A stack is LIFO: the last element pushed is the first popped. When you pop from one stack and push to another, the bottom element of the first stack ends up on top of the second. That reversal turns LIFO into FIFO for the transferred batch.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class ReversalDemo {
public static void main(String[] args) {
Deque<String> inbox = new ArrayDeque<>();
inbox.push("First"); // bottom
inbox.push("Second");
inbox.push("Third"); // top
Deque<String> outbox = new ArrayDeque<>();
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
// Outbox now has First on top (reversed order)
System.out.println(outbox.pop()); // First
System.out.println(outbox.pop()); // Second
System.out.println(outbox.pop()); // Third
}
}
First
Second
Third
Why is lazy transfer important?
Transferring only when the outbox is empty is what gives amortized O(1). Each element moves from inbox to outbox exactly once in its lifetime: one push to inbox, one transfer pop and push to outbox, and one final pop from outbox. If you transferred eagerly on every dequeue, each element could move multiple times, destroying the amortized guarantee.
package com.bank.core;
public class LazyTransferAnalysis {
public static void main(String[] args) {
// Element lifecycle:
// 1. Push to inbox: O(1)
// 2. Transfer to outbox: O(1) (happens once)
// 3. Pop from outbox: O(1)
// Total per element: O(3) = O(1) amortized
System.out.println("Lazy transfer: each element moves at most once");
System.out.println("Amortized cost per operation: O(1)");
System.out.println("Eager transfer: element may move multiple times");
System.out.println("Eager cost per dequeue: O(n) worst case every time");
}
}
Lazy transfer: each element moves at most once
Amortized cost per operation: O(1)
Eager transfer: element may move multiple times
Eager cost per dequeue: O(n) worst case every time
How do you implement a stack using a queue?
With a single queue, make push the expensive operation. After adding the new element, rotate all earlier elements behind it by polling and re-offering them. This puts the newest element at the front, giving LIFO behavior on poll.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Queue;
public class StackFromQueue<T> {
private final Queue<T> queue = new ArrayDeque<>();
public void push(T item) {
int size = queue.size();
queue.offer(item);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll()); // rotate older elements behind
}
}
public T pop() { return queue.poll(); }
public T top() { return queue.peek(); }
public boolean isEmpty() { return queue.isEmpty(); }
public static void main(String[] args) {
StackFromQueue<String> s = new StackFromQueue<>();
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 are the complexity trade-offs?
For two-stack queue: enqueue is O(1), dequeue is amortized O(1) but worst-case O(n) for a single call that triggers a transfer. For single-queue stack: push is O(n) due to rotation, pop and top are O(1). The two-stack queue has the better amortized bound.
package com.bank.core;
public class ComplexityComparison {
public static void main(String[] args) {
System.out.println("Queue from 2 stacks:");
System.out.println(" enqueue: O(1)");
System.out.println(" dequeue: amortized O(1), worst O(n)");
System.out.println();
System.out.println("Stack from 1 queue:");
System.out.println(" push: O(n) (rotation)");
System.out.println(" pop: O(1)");
}
}
Queue from 2 stacks:
enqueue: O(1)
dequeue: amortized O(1), worst O(n)
Stack from 1 queue:
push: O(n) (rotation)
pop: O(1)
What are common mistakes?
The biggest mistake is transferring from inbox to outbox on every dequeue instead of only when the outbox is empty. This not only destroys the O(1) amortized bound but also breaks the FIFO ordering because newly enqueued elements get mixed into the transfer.
package com.bank.core;
public class EagerTransferBug {
public static void main(String[] args) {
// If we transfer on every dequeue:
// enqueue A, B, C
// dequeue: transfer [A,B,C] to outbox -> pop A (correct so far)
// enqueue D
// dequeue: transfer [D] to outbox (which still has B,C) -> WRONG
// The outbox already had older elements; adding D on top breaks order
System.out.println("Eager transfer mixes new elements with old ones");
System.out.println("Rule: transfer ONLY when outbox is empty");
}
}
Eager transfer mixes new elements with old ones
Rule: transfer ONLY when outbox is empty
How is this applied in banking?
At the National Bank of India, a legacy cheque-clearing module exposed only stack-based buffers, but cheques must be processed in arrival order. The two-stack queue gave FIFO semantics over stack primitives. The lazy transfer kept throughput high because clearing happens in bursts: a batch of cheques arrives, fills the inbox, and a single transfer empties them in correct order.
package com.bank.service;
public class ChequeClearingDemo {
public static void main(String[] args) {
QueueFromStacks<String> clearing = new QueueFromStacks<>();
// Batch arrival
clearing.enqueue("CHQ-001: Rajesh 50000");
clearing.enqueue("CHQ-002: Priya 25000");
clearing.enqueue("CHQ-003: Pankaj 75000");
// Process in arrival order
System.out.println("Clearing: " + clearing.dequeue());
System.out.println("Clearing: " + clearing.dequeue());
// New arrival while processing
clearing.enqueue("CHQ-004: Rajesh 30000");
System.out.println("Clearing: " + clearing.dequeue());
System.out.println("Clearing: " + clearing.dequeue());
}
}
Clearing: CHQ-001: Rajesh 50000
Clearing: CHQ-002: Priya 25000
Clearing: CHQ-003: Pankaj 75000
Clearing: CHQ-004: Rajesh 30000
What should a senior engineer know?
In normal Java, use ArrayDeque as a real queue. The two-stack construction earns its place when a stack is the only primitive available, such as implementing a queue over an immutable stack in functional code. It is the idea behind the Banker's queue in functional data structures, where two lists play the role of the two stacks. The key interview insight is explaining amortized analysis: worst-case O(n) for one call does not mean O(n) per operation on average.
package com.bank.core;
public class SeniorNotes {
public static void main(String[] args) {
System.out.println("Real Java code: use ArrayDeque as a queue directly");
System.out.println("Two-stack queue: useful when only stacks are available");
System.out.println("Functional programming: Banker's queue = two lists");
System.out.println("Interview key: explain amortized O(1) vs worst-case O(n)");
}
}
Real Java code: use ArrayDeque as a queue directly
Two-stack queue: useful when only stacks are available
Functional programming: Banker's queue = two lists
Interview key: explain amortized O(1) vs worst-case O(n)
Visual Overview
Two-Stack Queue Operation
─────────────────────────
enqueue(A), enqueue(B), enqueue(C):
Inbox Outbox
┌─────┐ ┌─────┐
│ C │ top │ │ empty
├─────┤ └─────┘
│ B │
├─────┤
│ A │
└─────┘
dequeue() → outbox empty, transfer:
Inbox Outbox
┌─────┐ ┌─────┐
│ │ empty │ A │ top ← oldest on top!
└─────┘ ├─────┤
│ B │
├─────┤
│ C │
└─────┘
pop outbox → returns A (FIFO order)
Key Takeaway
Implementing a queue with two stacks is a lesson in how reversing order with one structure gives you the behavior of its opposite. I keep an inbox stack and an outbox stack. Every enqueue pushes onto the inbox in O(1). Every dequeue serves from the outbox, and only when the outbox is empty do I pour the entire inbox into it, which reverses the order so the oldest element ends up on top.
The lazy transfer rule is what makes this efficient. Each element moves from inbox to outbox exactly once in its lifetime, so the amortized cost per operation is O(1) even though one particular dequeue that triggers a transfer can be O(n). Transferring on every dequeue would break both the ordering and the complexity guarantee.
The mirror problem of building a stack from a queue has no amortized constant-time solution for both operations. The common approach rotates a single queue on every push so the newest element sits at the front, making push O(n) and pop O(1). It is a fine interview exercise but far less practical than the two-stack queue.
In my project at the National Bank of India, I used this in a cheque-clearing module where the legacy buffers behaved like stacks but cheques had to be processed in arrival order. The inbox collected arrivals and the outbox served them in corrected order, and the lazy-flip rule kept throughput high during burst clearing.
Remember one sentence: push to inbox, pour into outbox only when it is empty, and each element moves at most once for amortized O(1).
---