Skip to content
Hello Python
Data Structure1 Practice9 Interview

Queue

First-in-first-out structure for breadth-first traversal, scheduling, and ordered processing. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Queue when the prompt's constraints and required operations match this shape: First-in-first-out structure for breadth-first traversal, scheduling, and ordered processing.

Pybit studies a professional Queue interview workspace with precise technical objects.
On this page · Mental Model

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Queue Code Labs

Mental Model

A queue preserves arrival order: the oldest pending item leaves first. That FIFO rule separates a queue from a stack and makes it the natural frontier for breadth-first exploration, scheduling, and stream processing. At every moment, queued items are discovered but not yet processed.

FIFO State with deque

Use collections.deque: append enqueues on the right and popleft dequeues from the left, both in O(1) time. A Python list’s pop(0) shifts every remaining reference and costs O(n). The deque documentation(opens in a new tab) also provides two-ended operations, but a queue deliberately uses only one input and one output end.

Process One Breadth Layer

In breadth-first work, mark an item seen when enqueuing it, not when later removing it. Then each reachable item enters once. To preserve layers, capture the queue length before processing the current batch; newly discovered items belong to the next layer.

Collect Breadth-First Layers

Reference
from collections import deque

def breadth_layers(adjacency, start):
    queue = deque([start])
    seen = {start}
    layers = []
    while queue:
        layer = []
        for _ in range(len(queue)):
            node = queue.popleft()
            layer.append(node)
            for neighbor in adjacency[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
        layers.append(layer)
    return layers
Practice

Implement breadth_layers(adjacency, start). Return reachable nodes grouped by unweighted distance, marking each node seen when it is enqueued.

Public tests

  • Verify FIFO breadth layers

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Implement a Circular Buffer

A fixed-capacity queue can reuse an array with head, tail, and size. Enqueue writes at tail and advances modulo capacity; dequeue reads at head and advances the same way. When head equals tail, size distinguishes empty from full. Every accepted operation remains O(1).

Advance a Circular Buffer

Reference
def simulate_circular_buffer(capacity, actions):
    storage = [None] * capacity
    head = tail = size = 0
    output = []
    for action in actions:
        if action[0] == 'put':
            if size < capacity:
                storage[tail] = action[1]
                tail = (tail + 1) % capacity
                size += 1
        elif size == 0:
            output.append(None)
        else:
            output.append(storage[head])
            head = (head + 1) % capacity
            size -= 1
    return output
Practice

Implement simulate_circular_buffer(capacity, actions). Accept puts while space remains and return values or None for each get in FIFO order.

Public tests

  • Verify FIFO wraparound behavior

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Queue or Another Frontier

Use a queue when arrival or graph distance determines processing order. Use a stack for nested or depth-first work, a priority queue when the smallest key must leave first, and a deque when both ends are meaningful. Sorting all pending work repeatedly is not a substitute for a priority queue.

Common Pitfalls

  • Using list.pop(0) hides O(n) shifting inside every dequeue.
  • Marking nodes seen at removal allows multiple parents to enqueue duplicates.
  • Iterating directly over a growing queue blurs the current and next breadth layers.
  • A circular buffer with only head and tail cannot distinguish full from empty without another rule.

Explain It in an Interview

Define what one queued item represents and why FIFO order matches the problem’s guarantee. State when items become seen, what is true before a dequeue, and whether the maximum frontier controls space. For a circular buffer, explain the meaning of all three counters before writing modulo arithmetic.

Advance a Circular Buffer(opens in a new tab) isolates wraparound state. Design Circular Queue(opens in a new tab) adds the full public API and persistent empty/full semantics.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Queue workflowO(a)O(a)A bounded FIFO can reuse fixed storage when head, tail, and size make full and empty states explicit. head identifies the oldest live value, tail identifies the next write slot, and size stays between zero and capacity.

Space

O(capacity) for the demonstrated Queue workflow.

Assumptions

  • The bound assumes deque or list-end operations; removing from the front of a Python list is O(n).
  • The bound counts the operations in Advance a Circular Buffer and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Queue invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. A bounded FIFO can reuse fixed storage when head, tail, and size make full and empty states explicit. This remains true after every accepted operation.
  3. head identifies the oldest live value, tail identifies the next write slot, and size stays between zero and capacity. This remains true after every accepted operation.

When To Use Or Avoid Queue

Use It When

  • Use Queue when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Queue invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def simulate_circular_buffer(capacity, actions):
    pass

Use instead

def simulate_circular_buffer(capacity, actions):
    storage = [None] * capacity
    head = tail = size = 0
    output = []
    for action in actions:
        if action[0] == 'put':
            if size < capacity:
                storage[tail] = action[1]
                tail = (tail + 1) % capacity
                size += 1
        else:
            if size == 0:
                output.append(None)
            else:
                output.append(storage[head])
                head = (head + 1) % capacity
                size -= 1
    return output

Where you will hit this: Advance a Circular Buffer(opens in a new tab)

Breaking the central invariant

Evicts the oldest live value when full instead of ignoring the rejected put operation.

Prevent it: Keep this invariant visible while editing: State the precise Queue invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def simulate_circular_buffer(capacity, actions):
    storage = []
    output = []
    for action in actions:
        if action[0] == 'put':
            storage.append(action[1])
            if len(storage) > capacity:
                storage.pop(0)
        else:
            output.append(storage.pop(0) if storage else None)
    return output

Use instead

def simulate_circular_buffer(capacity, actions):
    storage = [None] * capacity
    head = tail = size = 0
    output = []
    for action in actions:
        if action[0] == 'put':
            if size < capacity:
                storage[tail] = action[1]
                tail = (tail + 1) % capacity
                size += 1
        else:
            if size == 0:
                output.append(None)
            else:
                output.append(storage[head])
                head = (head + 1) % capacity
                size -= 1
    return output

Where you will hit this: Advance a Circular Buffer(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(a).

Avoid

def simulate_circular_buffer(capacity, actions):
    storage = []
    output = []
    for action in actions:
        if action[0] == 'put':
            storage.append(action[1])
            if len(storage) > capacity:
                storage.pop(0)
        else:
            output.append(storage.pop(0) if storage else None)
    return output

Use instead

def simulate_circular_buffer(capacity, actions):
    storage = [None] * capacity
    head = tail = size = 0
    output = []
    for action in actions:
        if action[0] == 'put':
            if size < capacity:
                storage[tail] = action[1]
                tail = (tail + 1) % capacity
                size += 1
        else:
            if size == 0:
                output.append(None)
            else:
                output.append(storage[head])
                head = (head + 1) % capacity
                size -= 1
    return output

Where you will hit this: Design Circular Queue(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.