Module 09 · Queues, Heaps, and Streaming Frontiers

082. Stack Using One Queue

Foundation · Download this solution · All solutions and shared helpers

Problem

Implement a LIFO stack using one FIFO queue, supporting push(value), pop(), top() and empty(). push returns None; pop returns the most recently pushed value. Empty pop and top raise IndexError. Queue operations are append at the back and remove at the front.

Examples

Example 1

run_operations(OneQueueStack, [("push",1),("push",2),("top",),("pop",),("pop",)])
=> [None, None, 2, 2, 1]

The most recent insertion is at the queue front.

Example 2

run_operations(OneQueueStack, [("empty",)])
=> [True]

A fresh queue is an empty stack.

Example 3

run_operations(OneQueueStack, [("push",7),("pop",),("empty",)])
=> [None, 7, True]

Removing the only value restores emptiness.

Reveal the worked solution and reasoning

Why this mechanism works

Make push expensive so pop stays simple. After enqueuing a new value, rotate all older values behind it. The newest element becomes the front, and the older stack order is preserved behind that front.

State and boundaries

queue order from front to back equals stack order from top to bottom.

Protocol

Enqueue the new value.
Rotate exactly the previous queue size from front to back.
Pop or inspect the front for stack operations.
Test queue emptiness.

Visualization

existing top-to-bottom [2,1]
append 3 -> [2,1,3]
rotate twice -> [3,2,1]

Python implementation

from collections import deque
from structures import run_operations

class OneQueueStack:
    def __init__(self):
        self.queue = deque()

    def push(self, value):
        old_size = len(self.queue)
        self.queue.append(value)
        for _ in range(old_size):
            self.queue.append(self.queue.popleft())

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

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

run_operations(OneQueueStack, [("push",1),("push",2),("top",),("pop",),("pop",)])

L6 __init__: self.queue = deque()
self=OneQueueStack{'queue':deque([])}

L9 push: old_size = len(self.queue)
self=OneQueueStack{'queue':deque([])}; value=1; old_size=0

L10 push: self.queue.append(value)
self=OneQueueStack{'queue':deque([...])}; value=1; old_size=0

L9 push: old_size = len(self.queue)
self=OneQueueStack{'queue':deque([...])}; value=2; old_size=1

L10 push: self.queue.append(value)
self=OneQueueStack{'queue':deque([..., ...])}; value=2; old_size=1

L11 push: for _ in range(old_size):
self=OneQueueStack{'queue':deque([..., ...])}; value=2; old_size=1; _=0

L18 top: return self.queue[0]
self=OneQueueStack{'queue':deque([..., ...])}

L15 pop: return self.queue.popleft()
self=OneQueueStack{'queue':deque([...])}

L15 pop: return self.queue.popleft()
self=OneQueueStack{'queue':deque([])}

Result: [None, None, 2, 2, 1]. The most recent insertion is at the queue front.

run_operations(OneQueueStack, [("empty",)])

L6 __init__: self.queue = deque()
self=OneQueueStack{'queue':deque([])}

L21 empty: return not self.queue
self=OneQueueStack{'queue':deque([])}

Result: [True]. A fresh queue is an empty stack.

Why the solution is correct

Before a push, the queue already represents top-to-bottom order. Moving all older elements behind the new one creates exactly the new stack order without changing the older relative order. Front removal therefore implements LIFO.

Time and space

O(n) time for push with n existing elements; O(1) pop, top and empty; O(n) storage.

Common mistakes

Rotating the new queue length rather than the old length returns the queue to its original order. Using a second queue violates this kata's constraint.

Reasoning card

State: queue order from front to back equals stack order from top to bottom.

Invariant: Queue front is always the stack top.

Decision to rehearse: Rotate older elements behind the newest on push.

Finish: Test queue emptiness

Transfer exercise

Choose cheap push and expensive pop instead; specify the queue representation and the tradeoff per operation.