Stack / Queue Emulation

Implementing a Queue with Two Stacks

LeetCode 232 presents a classic design challenge: a stack gives you LIFO, last in, first out. A queue needs FIFO, first in, first out. At first glance these feel incompatible, but two stacks together can simulate a queue perfectly, and the key insight is a technique called lazy transfer.

The Core Idea

Keep two stacks: an input stack and an output stack. Every push goes onto the input stack. Every pop or peek reads from the output stack. The trick is that the output stack holds elements in reversed order, which is exactly the order a queue wants to serve them.

When you need to pop or peek but the output stack is empty, you drain the entire input stack into the output stack. Because a stack reverses order, pouring input into output un-reverses the elements back to arrival order.

Walked Example

Start with an empty queue. Push 1, 2, 3 in that order.

After push(1): inp=[1]       out=[]
After push(2): inp=[1,2]     out=[]
After push(3): inp=[1,2,3]   out=[]

Now call pop(). The output stack is empty, so we transfer: pop everything from inp and push onto out.

Transfer:      inp=[]        out=[3,2,1]
pop() returns: inp=[]        out=[3,2]    → 1

Push 4, then pop twice more.

After push(4): inp=[4]       out=[3,2]
pop() returns: inp=[4]       out=[3]      → 2
pop() returns: inp=[4]       out=[]       → 3

Now out is empty again. Next pop triggers another transfer: inp drains into out.

Transfer:      inp=[]        out=[4]
pop() returns: inp=[]        out=[]       → 4

Every element was served in the order 1, 2, 3, 4, exactly FIFO.

The Implementation

class MyQueue:
    def __init__(self):
        self.inp = []   # new elements land here
        self.out = []   # elements leave from here

    def push(self, x: int) -> None:
        self.inp.append(x)

    def pop(self) -> int:
        self.peek()          # ensure out is populated
        return self.out.pop()

    def peek(self) -> int:
        if not self.out:     # lazy transfer only when needed
            while self.inp:
                self.out.append(self.inp.pop())
        return self.out[-1]

    def empty(self) -> bool:
        return not self.inp and not self.out

Amortized $O(1)$ Analysis

Each element is moved at most twice: once when it's pushed onto inp, and once when it's transferred to out. After that it just gets popped off out and is gone. Averaged over n operations, the transfer cost is $O(1)$ per element. Individual pops may be $O(n)$ in the worst case (when a large transfer happens), but the total work over any sequence of operations is $O(n)$, giving $O(1)$ amortized per operation.

This is a classic example of amortized analysis: you pay a small cost repeatedly to avoid a large accumulated debt.

Stack from Queues

With LeetCode 225, going the other direction is more expensive. Queues only expose their front, so to get LIFO behavior you have to rearrange elements on every operation.

The typical approach makes push expensive. When you push a new element, enqueue it into a temporary queue, then drain the main queue into it behind the new element. Now the new element is at the front, which is where you want it for a pop.

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # rotate so new element is at the front
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

Every push costs $O(n)$ because it rotates the whole queue. There is no way to achieve amortized $O(1)$ for both push and pop when using only queues. The asymmetry is fundamental.

Min Stack

LeetCode 155 poses a closely related design question: support push, pop, top, and get_min all in $O(1)$. The standard solution pairs each element with the minimum seen so far.

class MinStack:
    def __init__(self):
        self.stack = []   # (value, current_min) pairs

    def push(self, val: int) -> None:
        current_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

By recording the running minimum at every level, each element carries enough information to restore the minimum after it's popped. This is $O(1)$ for every operation at the cost of doubling storage.

Design Circular Queue

LeetCode 622 asks you to build a fixed-capacity queue using an array with wrap-around indexing. Instead of shifting elements on every dequeue (which costs $O(n)$), you maintain a head pointer, a count, and compute the tail position as (head + count) % capacity. Enqueue writes at the tail; dequeue advances the head. Both are $O(1)$.

class MyCircularQueue:
    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0
        self.count = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.count == self.capacity:
            return False
        tail = (self.head + self.count) % self.capacity
        self.data[tail] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True

    def Front(self) -> int:
        return -1 if self.count == 0 else self.data[self.head]

    def Rear(self) -> int:
        if self.count == 0:
            return -1
        tail = (self.head + self.count - 1) % self.capacity
        return self.data[tail]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

Using count rather than separate head/tail pointers avoids the classic ambiguity where head == tail could mean either full or empty. All operations are $O(1)$ worst case, and the fixed array means $O(k)$ space with no dynamic allocation.

Complexity Summary

For the two-stack queue: each operation is $O(1)$ amortized and $O(n)$ worst case; space is $O(n)$. For the stack-from-queues: push is $O(n)$, pop is $O(1)$, space is $O(n)$. For min stack: all operations $O(1)$, space $O(n)$. For circular queue: all operations $O(1)$ worst case, space $O(k)$.

Recognizing this pattern

You're probably looking at stack/queue emulation when:

• The problem says "implement a queue using only stacks" or "implement a stack using only queues."
• You need to expose FIFO behavior but the only primitive available is LIFO (or vice versa).
• The problem asks for amortized O(1) operations when the obvious approach is O(n) per call.
• You're designing a bounded ring buffer with O(1) enqueue/dequeue from both ends.

Common templates:

• Two-stack queue: in stack for pushes, out stack for pops; transfer lazily when out is empty. Example: Implement Queue using Stacks.
• Two-queue stack: make push expensive by rotating, or make pop expensive by rotating; pick which side to pay on. Example: Implement Stack using Queues.
• Circular buffer queue/deque: fixed-size array with head and tail indices, modular wraparound. Example: Design Circular Queue.
• Augmented stack with extra invariant: a parallel stack tracks an aggregate like min or sum. Example: Min Stack.