DSA A Stack from Queues

The problem

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

A queue serves in arrival order. Its front is its oldest value. The contract has three operations: push adds a value on top, pop removes and returns the top value, and peek returns the top value without removing it.

script = [
    ("push", 10), ("push", 20), ("push", 30),
    ("peek", 30),
    ("pop", 30),
    ("push", 40),
    ("pop", 40), ("pop", 20), ("pop", 10),
]
for op, value in script:
    print(op, value)

Read the script top to bottom. The peek and the pops name the value each operation must return. The pops return 30, 40, 20, 10: newest first, every time.

Intuition: one plain queue serves the oldest first

The first idea is a single queue with no extra work. Push appends. Pop takes the front. That is a correct queue and a wrong stack.

from collections import deque

queue = deque()
for value in (10, 20, 30):
    queue.append(value)
print("front of the queue:", queue[0])
print("a stack pop must return: 30")

The front holds 10, the oldest value. A stack needs 30, the newest. Something has to move the newest value to the front, because the front is the only end a queue can serve from.

Brute force: rotate on every pop

A straightforward fix keeps pushes cheap and pays at pop time. The queue holds values in arrival order. A pop rotates the front values to the back until the newest value reaches the front, then takes it.

The order comes out right. The cost lands on every pop: a pop from n values rotates n - 1 of them, and a peek pays the same rotation to look at the top.

from collections import deque


class PopPayStack:
    def __init__(self):
        self.items = deque()
        self.rotations = 0

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

    def pop(self):
        for _ in range(len(self.items) - 1):
            self.items.append(self.items.popleft())
            self.rotations += 1
        return self.items.popleft()

stack = PopPayStack()
for value in (10, 20, 30):
    stack.push(value)
print("popped:", stack.pop())
print("popped:", stack.pop())
print("rotations:", stack.rotations)

Two pops cost three rotations. The count is correct but badly placed: reading the stack costs the most exactly when the stack is largest.

The optimal solution: rotate on push, serve the front

Move the rotation to push time: append the new value, then rotate every older value behind it, so the newest value always sits at the front. Pop and peek then read the front directly, with no rotation at all.

from collections import deque


class QueueStack:
    def __init__(self):
        self.items = deque()
        self.rotations = 0

    def push(self, value):
        self.items.append(value)
        for _ in range(len(self.items) - 1):
            self.items.append(self.items.popleft())
            self.rotations += 1

    def pop(self):
        return self.items.popleft()

    def peek(self):
        return self.items[0]

stack = QueueStack()
for value in (10, 20, 30):
    stack.push(value)
print("peek:", stack.peek())
print("pop:", stack.pop())
stack.push(40)
print("pop:", stack.pop())
print("pop:", stack.pop())
print("pop:", stack.pop())
print("rotations:", stack.rotations)

Every returned value matches the script. The deque ends empty. All the rotation cost sits in the pushes, where it is paid once per value instead of once per read.

Walkthrough: three pushes, step by step

Watch the deque after each push. The front of the printed list is the left end. The newest value must stand there when each push finishes.

from collections import deque


class QueueStack:
    def __init__(self):
        self.items = deque()
        self.rotations = 0

    def push(self, value):
        self.items.append(value)
        for _ in range(len(self.items) - 1):
            self.items.append(self.items.popleft())
            self.rotations += 1

    def pop(self):
        return self.items.popleft()

    def peek(self):
        return self.items[0]

stack = QueueStack()
for value in (10, 20, 30, 40):
    stack.push(value)
    print("after push", value, ":", list(stack.items), "rotations so far:", stack.rotations)

Pushing 40 appends it at the back, then rotates 10, 20 and 30 behind it. Four pushes cost zero, one, two and three rotations. The front is always the value a pop would return.

Complexity

Time is O(n) for a push onto n values and O(1) for pop and peek: the push rotates each older value once, and the reads never rotate.

Space is O(n) for n values: one deque holds them all, and the rotation uses no second structure.

from collections import deque


class QueueStack:
    def __init__(self):
        self.items = deque()
        self.rotations = 0

    def push(self, value):
        self.items.append(value)
        for _ in range(len(self.items) - 1):
            self.items.append(self.items.popleft())
            self.rotations += 1

    def pop(self):
        return self.items.popleft()

    def peek(self):
        return self.items[0]

for n in (4, 8, 16):
    stack = QueueStack()
    for value in range(n):
        stack.push(value)
    print("pushes:", n, "total rotations:", stack.rotations)

The totals are 6, 28 and 120. Each is n times n - 1, divided by two. The printed growth matches the formula: total push work grows with the square, spread one rotation row per push.

Edge cases and pitfalls

A stack of one value needs no rotation. The push appends it, the rotation loop runs zero times, and pop returns it.

Peek must not disturb the order. It reads index 0 and leaves the deque untouched, so a pop right after it returns the same value.

from collections import deque


class QueueStack:
    def __init__(self):
        self.items = deque()
        self.rotations = 0

    def push(self, value):
        self.items.append(value)
        for _ in range(len(self.items) - 1):
            self.items.append(self.items.popleft())
            self.rotations += 1

    def pop(self):
        return self.items.popleft()

    def peek(self):
        return self.items[0]

stack = QueueStack()
stack.push(5)
print("single pop:", stack.pop())
stack.push(5)
stack.push(9)
print("peek:", stack.peek())
print("pop after peek:", stack.pop())
print("rotations:", stack.rotations)

One pitfall is the rotation count. Rotating len times instead of len - 1 carries the new value back to the back. The stack then serves the oldest value, and every later answer is wrong.