Build Stacks and QueuesStep 3 of 5

Queue from Two Stacks (FIFO)

12345

Step 3 - Queue from Two Stacks (FIFO)

A queue is First-In-First-Out (FIFO): items leave in arrival order, like a task buffer. A neat trick builds one from two stacks: an in-stack for arrivals and an out-stack for departures.

Implement dequeue: if the out-stack is empty, transfer every item from the in-stack into it (reversing order), then pop the out-stack. Return None when both are empty. This transfer gives amortized O(1) per operation.

Hints
Starter code
class Stack:
    def __init__(self):
        self._data = []

    def push(self, x):
        self._data.append(x)

    def pop(self):
        if not self._data:
            return None
        return self._data.pop()

    def peek(self):
        if not self._data:
            return None
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)


def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    openers = set(pairs.values())
    stack = Stack()
    for ch in s:
        if ch in openers:
            stack.push(ch)
        elif ch in pairs:
            if stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()


class Queue:
    def __init__(self):
        self._in = []
        self._out = []

    def enqueue(self, x):
        self._in.append(x)

    def dequeue(self):
        """Remove and return the front item (FIFO), or None if empty."""
        # TODO: if _out is empty, move all of _in into _out (reversed), then pop _out
        pass

    def is_empty(self):
        return not self._in and not self._out

    def size(self):
        return len(self._in) + len(self._out)
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step