DSA A Queue from Two Stacks

The problem

A queue serves values in arrival order. The first value in is the first value out. This design problem asks for a queue built from stacks only.

A stack serves in reverse order. Its last value in is its first value out. The contract has two operations: enqueue adds a value at the back, and dequeue removes and returns the front value.

script = [
    ("enqueue", 1), ("enqueue", 2), ("enqueue", 3),
    ("dequeue", 1),
    ("enqueue", 4),
    ("dequeue", 2), ("dequeue", 3), ("dequeue", 4),
]
for op, value in script:
    print(op, value)

Read the script top to bottom. Three values arrive, then one leaves. A fourth arrives while others still wait. The dequeues must return 1, 2, 3, 4 in that order.

Intuition: one stack serves backwards

The first idea is a single stack for everything. Enqueue pushes. Dequeue pops. The structure is simple, and it is a stack, so the order comes out reversed.

stack = []
for value in (1, 2, 3):
    stack.append(value)
served = []
while stack:
    served.append(stack.pop())
print("served:", served)
print("queue order wanted: [1, 2, 3]")

The pop order is 3, 2, 1. That is exactly backwards. The fix needs a second reversal somewhere, and reversing a reversal restores the original order.

Brute force: one list, pop from the front

A straightforward queue uses one plain list. Enqueue appends at the back. Dequeue takes index 0 with pop(0). The order is correct from the start.

The cost hides inside pop(0). Removing the front element shifts every remaining element one place left. A long queue pays that shift bill on every dequeue.

class ListQueue:
    def __init__(self):
        self.items = []
        self.shifts = 0

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        self.shifts += len(self.items) - 1
        return self.items.pop(0)

queue = ListQueue()
for value in (1, 2, 3, 4, 5):
    queue.enqueue(value)
served = [queue.dequeue() for _ in range(5)]
print("served:", served)
print("element shifts:", queue.shifts)

Five dequeues cost ten shifts. The count grows with the square of the queue length: each dequeue shifts almost the whole list. Correct order, expensive habit.

The optimal solution: an inbox and an outbox

Split the work between two stacks: enqueue always pushes onto the inbox, and dequeue always pops from the outbox, refilling the outbox from the inbox only when the outbox runs empty. The refill reverses the inbox, which puts the oldest value on top.

class StackQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.moves = 0

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1
        return self.outbox.pop()

queue = StackQueue()
served = []
for value in (1, 2, 3):
    queue.enqueue(value)
served.append(queue.dequeue())
queue.enqueue(4)
for _ in range(3):
    served.append(queue.dequeue())
print("served:", served)
print("stack moves:", queue.moves)

The served order matches the script: 1, 2, 3, 4. Four values needed four moves in total. No value ever moves twice, because a value crosses from inbox to outbox exactly once in its life.

Walkthrough: the first refill

Watch both stacks on a short run. The state prints after each operation. The first dequeue is the interesting one, because the outbox starts empty.

class StackQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.moves = 0

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1
        return self.outbox.pop()

queue = StackQueue()
for value in (1, 2, 3):
    queue.enqueue(value)
    print("enqueue", value, "-> inbox", queue.inbox, "outbox", queue.outbox)
print("dequeue ->", queue.dequeue(), "inbox", queue.inbox, "outbox", queue.outbox)
queue.enqueue(4)
print("enqueue 4 -> inbox", queue.inbox, "outbox", queue.outbox)
print("dequeue ->", queue.dequeue(), "inbox", queue.inbox, "outbox", queue.outbox)

The refill moves 3, then 2, then 1, so the outbox reads [3, 2] after 1 is served. The 4 waits in the inbox while the outbox still holds values. It crosses only when the outbox empties.

Complexity

Time is O(1) amortised per operation: most operations are a single push or pop, and the rare refill is paid for by the moves each value makes only once.

Space is O(n) for n waiting values: each value sits in exactly one of the two stacks at any moment.

class StackQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.moves = 0

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1
        return self.outbox.pop()

for n in (5, 10, 20):
    queue = StackQueue()
    for value in range(n):
        queue.enqueue(value)
    for _ in range(n):
        queue.dequeue()
    print("values:", n, "total moves:", queue.moves)

The move count equals the value count at every size. Doubling the workload doubles the moves, never more. Compare that with the shift counts of the one-list queue, which grow with the square.

Edge cases and pitfalls

A single value crosses and serves cleanly. Enqueue, then dequeue, returns that value, and both stacks end empty.

The refill condition is the pitfall. Refilling on every dequeue, instead of only when the outbox is empty, dumps new inbox values on top of waiting outbox values. The served order breaks at once.

class StackQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.moves = 0

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1
        return self.outbox.pop()

queue = StackQueue()
queue.enqueue(7)
print("single value:", queue.dequeue())
queue.enqueue(1)
queue.enqueue(2)
print("first out:", queue.dequeue())
queue.enqueue(3)
print("second out:", queue.dequeue())
print("third out:", queue.dequeue())
print("moves:", queue.moves)

Interleaving works because the inbox and outbox keep separate jobs. The 3 stays behind the 2 even though it arrived later and crossed later. Arrival order survives every mix of operations.