225. Implement Stack using Queues

Problem¶

Implement a LIFO stack using only queue operations: enqueue at back, peek/dequeue at front, size, and emptiness. Support push, pop, top, and empty using at most two queues; the follow-up allows only one.

Calls to pop and top are guaranteed valid.

Operation   Return   Stack (top first)
push(1)     None     [1]
push(2)     None     [2, 1]
top()       2        [2, 1]
pop()       2        [1]
empty()     False    [1]

class MyStack:
    def __init__(self):
        pass

    def push(self, x: int) -> None:
        pass

    def pop(self) -> int:
        pass

    def top(self) -> int:
        pass

    def empty(self) -> bool:
        pass

Key trick¶

After enqueueing a new value, move every older value from front to back; the newest value becomes the front.

push(3): [2, 1] -> [2, 1, 3] -> [1, 3, 2] -> [3, 2, 1]

Trap¶

Rotate exactly the previous queue size, not the size after insertion.
Do not use deque.pop() or access the back: those are not permitted queue operations.
Front access through q[0] is valid as a queue peek.

Why is it interesting?¶

It demonstrates how maintaining an invariant converts FIFO behavior into LIFO behavior, trading slower pushes for constant-time reads and removals.

Python solution¶

from collections import deque


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

    def push(self, x: int) -> None:
        self.q.append(x)
        # Keep the stack top at the queue 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

Time: push takes \(O(n)\); pop, top, and empty take \(O(1)\).

Space: \(O(n)\) total storage, with \(O(1)\) auxiliary space per operation.

Comment on my solution¶

Both implementations are correct and maintain the newest element at the queue front.
Both have \(O(n)\) pushes and \(O(1)\) other operations.
The one-queue version is preferable: it avoids allocating a replacement queue on each push.
Replace False if len(self.queue) else True with not self.queue.

from collections import deque

# Ideas:
# a = [1]
# [1,2]  [[1], 2]
#
# . -> . -> . -> .
#
# [1]
# ---
# [ ] pop 1
# [2] append 2
# [2,1] append 1 again
# ---
# [ ] pop 2, pop 1 [2, 1]
# [3] append 3
# [3, 2] append 2
# [3, 2, 1] append 1
# ------
# [1]
# ---
# [1,2] append 2
# [2,1] pop + append 1
# ---
# [2,1,3] append 3
# [1,3,2] pop + append 2
# [3,2,1] pop + append 1

# WORKS
# using 2 queues
class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        q = deque([x])
        for _ in range(len(self.queue)):
            q.append(self.queue.popleft())
        self.queue = q

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

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

    def empty(self) -> bool:
        return False if len(self.queue) else True

# WORKS
# using 1 queue
class MyStack:
    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

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

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

    def empty(self) -> bool:
        return False if len(self.queue) else True