Implement a Queue Using Two Stacks | Coding Problems: DSA

Q: What should a senior engineer know?

In production Java use ArrayDeque directly. The twostack queue matters when the only primitive is a stack, such as implementing a queue over an immutable stack in functional code. It underpins the Banker's queue in functional data structures where two lists replace the two stacks. The amortized anal

Definition

Push to an inbox stack, pour into an outbox stack only when the outbox is empty, and each element moves once for amortized constant time.

Two-stack queue – simulate FIFO using two LIFO stacks: an inbox for enqueue and an outbox for dequeue.
Lazy transfer – pour the inbox into the outbox only when the outbox is empty, which reverses the order so the oldest element ends up on top.
Amortized O(1) – each element is pushed to inbox once, moved to outbox once, and popped once over its lifetime.
Eager transfer – transferring on every dequeue breaks both ordering and complexity.
Banker's queue – the functional data structures equivalent uses two lists in place of two stacks.
Production – in real Java, use ArrayDeque as a queue; the two-stack construction is for stack-only environments.

Picture two spikes at the National Bank of India teller window. New request slips go onto the incoming spike. When the teller wants to serve the next customer in fairness order, she checks the serving spike. If it is empty she flips the whole incoming pile onto it, reversing the order so the earliest arrival is on top. She serves from the serving spike until it empties, then flips again only when needed.

Understanding the Concepts

What is the problem?

Build a FIFO queue using only two LIFO stacks. Enqueue adds to the back; dequeue removes from the front. The challenge is doing this efficiently, not naively reversing on every operation.

JAVA

package com.bank.service;

import java.util.ArrayDeque;
import java.util.Deque;

public class TwoStackQueue<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) {
        TwoStackQueue<String> q = new TwoStackQueue<>();
        q.enqueue("TXN-A"); q.enqueue("TXN-B"); q.enqueue("TXN-C");
        System.out.println(q.dequeue()); // TXN-A
        q.enqueue("TXN-D");
        System.out.println(q.dequeue()); // TXN-B
        System.out.println(q.dequeue()); // TXN-C
        System.out.println(q.dequeue()); // TXN-D
    }
}

TEXT

TXN-A
TXN-B
TXN-C
TXN-D

Why does transferring reverse the order?

Popping from one stack and pushing to another reverses the element order. The bottom of the first stack ends up on top of the second. This turns LIFO into FIFO for that batch.

JAVA

package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class ReverseDemo {
    public static void main(String[] args) {
        Deque<String> in = new ArrayDeque<>();
        in.push("First"); in.push("Second"); in.push("Third");

        Deque<String> out = new ArrayDeque<>();
        while (!in.isEmpty()) out.push(in.pop());

        System.out.println(out.pop()); // First (oldest)
        System.out.println(out.pop()); // Second
        System.out.println(out.pop()); // Third
    }
}

TEXT

First
Second
Third

What is the amortized analysis?

Each element goes through three moves: push to inbox (O(1)), transfer to outbox (O(1)), pop from outbox (O(1)). Total per element is O(3) = O(1). A single dequeue that triggers a transfer can be O(n), but spread across all operations the average is O(1).

JAVA

package com.bank.core;

public class AmortizedCost {
    public static void main(String[] args) {
        System.out.println("Per element:");
        System.out.println("  1. Push to inbox: O(1)");
        System.out.println("  2. Move to outbox: O(1) (once in lifetime)");
        System.out.println("  3. Pop from outbox: O(1)");
        System.out.println("Total per element: O(1) amortized");
        System.out.println("Single worst-case dequeue: O(n) but rare");
    }
}

TEXT

Per element:
  1. Push to inbox: O(1)
  2. Move to outbox: O(1) (once in lifetime)
  3. Pop from outbox: O(1)
Total per element: O(1) amortized
Single worst-case dequeue: O(n) but rare

Why is lazy transfer critical?

Transferring only when the outbox is empty ensures each element moves exactly once. If you transfer eagerly on every dequeue, newly enqueued elements get mixed with older ones in the outbox, breaking both FIFO order and the amortized guarantee.

JAVA

package com.bank.core;

public class LazyVsEager {
    public static void main(String[] args) {
        System.out.println("Lazy: transfer only when outbox empty");
        System.out.println("  Element moves inbox->outbox exactly once");
        System.out.println("  FIFO preserved, amortized O(1)");
        System.out.println();
        System.out.println("Eager: transfer on every dequeue");
        System.out.println("  Newly enqueued items mixed into outbox");
        System.out.println("  FIFO broken, no amortized guarantee");
    }
}

TEXT

Lazy: transfer only when outbox empty
  Element moves inbox->outbox exactly once
  FIFO preserved, amortized O(1)

Eager: transfer on every dequeue
  Newly enqueued items mixed into outbox
  FIFO broken, no amortized guarantee

What are common mistakes?

The biggest mistake is eager transfer. Another is forgetting to check both stacks in isEmpty(). A third is using this in production Java instead of simply using ArrayDeque as a queue.

JAVA

package com.bank.core;

public class TwoStackMistakes {
    public static void main(String[] args) {
        System.out.println("Mistake 1: eager transfer -> breaks order and complexity");
        System.out.println("Mistake 2: isEmpty checks only inbox or only outbox");
        System.out.println("Mistake 3: using this in production instead of ArrayDeque");
    }
}

TEXT

Mistake 1: eager transfer -> breaks order and complexity
Mistake 2: isEmpty checks only inbox or only outbox
Mistake 3: using this in production instead of ArrayDeque

What are the edge cases?

Dequeue on an empty queue should throw or return null. Multiple enqueues followed by multiple dequeues should return in FIFO order. Interleaved enqueues and dequeues should still maintain order because the outbox holds older elements.

JAVA

package com.bank.service;

public class TwoStackEdgeCases {
    public static void main(String[] args) {
        TwoStackQueue<String> q = new TwoStackQueue<>();
        // Interleaved operations
        q.enqueue("A"); q.enqueue("B");
        System.out.println(q.dequeue()); // A
        q.enqueue("C");
        System.out.println(q.dequeue()); // B (from outbox, before C)
        System.out.println(q.dequeue()); // C
        System.out.println("Empty: " + q.isEmpty()); // true
    }
}

TEXT

A
B
C
Empty: true

How is this applied in banking?

At the National Bank of India, a legacy component exposed only stack primitives, but the system needed strict oldest-first fairness for customer service requests. The two-stack queue gave FIFO semantics over stack primitives, and the lazy transfer kept throughput high during burst processing.

JAVA

package com.bank.service;

public class ServiceRequestQueue {
    public static void main(String[] args) {
        TwoStackQueue<String> requests = new TwoStackQueue<>();
        requests.enqueue("REQ-001: Rajesh account inquiry");
        requests.enqueue("REQ-002: Priya loan status");
        requests.enqueue("REQ-003: Pankaj balance check");

        System.out.println("Serving: " + requests.dequeue());
        System.out.println("Serving: " + requests.dequeue());
        requests.enqueue("REQ-004: Rajesh card block");
        System.out.println("Serving: " + requests.dequeue());
        System.out.println("Serving: " + requests.dequeue());
    }
}

TEXT

Serving: REQ-001: Rajesh account inquiry
Serving: REQ-002: Priya loan status
Serving: REQ-003: Pankaj balance check
Serving: REQ-004: Rajesh card block

What should a senior engineer know?

In production Java use ArrayDeque directly. The two-stack queue matters when the only primitive is a stack, such as implementing a queue over an immutable stack in functional code. It underpins the Banker's queue in functional data structures where two lists replace the two stacks. The amortized analysis is what interviewers really test.

JAVA

package com.bank.core;

public class SeniorTwoStackNotes {
    public static void main(String[] args) {
        System.out.println("Production: use ArrayDeque as a queue");
        System.out.println("This pattern: when only stacks available");
        System.out.println("Functional: Banker's queue with two lists");
        System.out.println("Interview key: explain amortized O(1)");
    }
}

TEXT

Production: use ArrayDeque as a queue
This pattern: when only stacks available
Functional: Banker's queue with two lists
Interview key: explain amortized O(1)

Visual Overview

DIAGRAM

  Two-Stack Queue
  ───────────────

  enqueue(A), enqueue(B), enqueue(C):

  Inbox          Outbox
  ┌─────┐        ┌─────┐
  │  C  │ top    │     │ empty
  ├─────┤        └─────┘
  │  B  │
  ├─────┤
  │  A  │
  └─────┘

  dequeue() → outbox empty → transfer:

  Inbox          Outbox
  ┌─────┐        ┌─────┐
  │     │ empty  │  A  │ top  (oldest!)
  └─────┘        ├─────┤
                 │  B  │
                 ├─────┤
                 │  C  │
                 └─────┘

  outbox.pop() → A (FIFO)

Key Takeaway

A queue from two stacks works by pushing to an inbox and serving from an outbox. When the outbox is empty, I pour the entire inbox into it, reversing the order so the oldest element is on top. Each element moves between stacks at most once in its lifetime, giving amortized O(1) per operation.

The lazy transfer rule is what makes this efficient. Transferring only when the outbox is empty ensures each element moves exactly once. Eager transfer on every dequeue breaks both the FIFO ordering and the amortized guarantee, because newly enqueued elements get mixed with older ones.

Explaining the amortized analysis, that worst-case O(n) for one call does not mean O(n) per operation on average, is the real point of this interview question. Each element pays a constant total cost across its lifetime: one push to inbox, one move to outbox, one pop from outbox.

In my project at the National Bank of India, a legacy component exposed only stack primitives, but customer service requests needed strict oldest-first fairness. The two-stack queue gave FIFO semantics, and the lazy transfer kept throughput high during burst processing. In production Java I would use ArrayDeque directly, but the two-stack construction is exactly the Banker's queue from functional data structures.

Remember one sentence: push to inbox, pour into outbox only when empty, and each element moves at most once for amortized O(1).

---