Skip to content
Data Structures & Algorithms

Queues interview questions and answers

55 questions, 38 with code. About 4 h 41 min to read them all.

By TestLab · Updated

Plan for an interview
55 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a queue data structure?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle: the first element added is the first one removed. It supports two primary operations: enqueue (add to the rear) and dequeue (remove from the front).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition

  • FIFO order: elements leave in the same order they arrive.

  • Front (head): where elements are removed.

  • Rear (tail): where elements are inserted.

  • Empty queue: no elements; dequeue/peek typically raise an error or return a sentinel.

Core Operations

  • enqueue(item): add item to rear. O(1).

  • dequeue(): remove and return front item. O(1).

  • peek() / front(): return front item without removing. O(1).

  • is_empty(): check if queue has no elements. O(1).

  • size() / len(): number of elements. O(1).

Time and Space Complexity

Operation Best Average Worst Notes
enqueue O(1) O(1) O(1) Amortized O(1) for dynamic array; O(1) for linked list or circular buffer
dequeue O(1) O(1) O(1) Same as above
peek O(1) O(1) O(1)
space O(n) O(n) O(n) n elements stored; input not counted

Common Variants

  • Simple FIFO queue: standard queue, often implemented with a linked list or a dynamic array (collections.deque in Python).

  • Circular queue (ring buffer): fixed-size array with head/tail indices modulo capacity; overwrites oldest when full or blocks.

  • Double-ended queue (deque): allows insertion and removal at both ends; Python’s collections.deque is an O(1) implementation (not thread-safe; use queue.Queue for thread-safe queues).

  • Priority queue: elements dequeued by priority (typically a heap); not FIFO. Python’s heapq provides a min-heap.

Typical Use Cases

  • Breadth-First Search (BFS): explores graph level by level.

  • Task scheduling: print queues, CPU scheduling (round-robin).

  • Rate limiting / buffering: fixed-size buffer between producer and consumer.

  • Sliding window problems: monotonic deque for maximum/minimum in O(n).

Common Pitfalls / Interview Tips

  • Using list.pop(0) in Python: O(n) per operation; always use collections.deque for queues.

  • Forgetting empty-check: dequeuing from an empty queue raises IndexError; handle explicitly.

  • Confusing queue with stack: stack is LIFO; queue is FIFO.

  • Circular queue full/empty ambiguity: when head == tail, distinguish with a size counter or a wasted slot.

  • Follow-up: implement a queue using two stacks (amortized O(1) enqueue/dequeue), or design a circular queue with fixed array.

2

What does FIFO mean in a queue?

A FIFO queue follows the First In, First Out policy: the element inserted earliest is the first one removed. This ordering makes queues useful for processing work in the same order it arrives.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How FIFO Works

A queue supports three primary operations:

  • Enqueue: Add an element to the rear of the queue.

  • Dequeue: Remove and return the element at the front of the queue.

  • Peek: Inspect the front element without removing it.

For example, if A, B, and C are enqueued in that order, three dequeues return A, then B, then C. An empty queue cannot be dequeued; the exception depends on the implementation. For example, Python’s collections.deque.popleft() raises IndexError, while queue.Queue.get() raises queue.Empty.

FIFO differs from a stack, which uses Last In, First Out (LIFO). It also differs from a priority queue, where the next element is determined by priority rather than arrival time.

Complexity

The complexity depends on the underlying implementation:

Operation Typical implementation Time complexity Reason
Enqueue Fixed-capacity circular array Best, average, and worst: O(1) Elements are written directly at the rear index.
Dequeue Fixed-capacity circular array Best, average, and worst: O(1) The front index advances without shifting elements.
Peek Fixed-capacity circular array Best, average, and worst: O(1) The front element is accessed directly.
Enqueue or dequeue Python collections.deque Best, average, and worst: O(1) Its internal structure supports constant-time insertion and removal at both ends.
Enqueue Dynamically growing array Amortized O(1); worst single operation: O(n) Occasional resizing copies all existing elements.

A queue storing n elements with proportional storage uses O(n) total space. Counting the stored elements, total space is O(n); excluding them, auxiliary space is O(1). The elements already held by the queue are counted as its storage, and no additional input copy or recursion stack is required.

Common Queue Variants

  • Simple FIFO queue: Maintains strict arrival order. This is the standard interpretation of a queue.

  • Circular queue: Uses a fixed-size array with front and rear indices calculated modulo the capacity. It reuses vacated positions and performs enqueue and dequeue in O(1) time.

  • Double-ended queue: Supports insertion and removal at both ends. Python’s collections.deque implements this structure, although removing from the rear no longer follows strict FIFO ordering.

  • Priority queue: Removes the highest-priority element rather than the oldest one. Python’s heapq implements a min-heap; values are negated when a max-heap is required.

  • Thread-safe queue: Python’s queue.Queue provides locking and condition variables for producer-consumer systems using multiple threads. Separate processes should use a process-safe queue such as multiprocessing.Queue.

Example Walkthrough

Starting with an empty queue:

Operation Queue front to rear Result
Enqueue A A —
Enqueue B A, B —
Enqueue C A, B, C —
Dequeue B, C Returns A
Peek B, C Returns B
Dequeue C Returns B

The order remains A, B, C because each element leaves in its insertion order.

Common Pitfalls and Interview Tips

  • Using a Python list with pop(0): This shifts every remaining element and costs O(n) per dequeue. Use collections.deque and popleft().

  • Confusing FIFO with priority ordering: A priority queue may remove a newer, higher-priority item before an older one.

  • Ignoring capacity semantics: A circular queue must distinguish clearly between empty and full states, often by reserving one slot or tracking a separate count.

  • Assuming thread safety: collections.deque is efficient but does not provide the coordination features of queue.Queue for producer-consumer workloads.

  • Typical follow-up: Interviewers may ask you to implement a queue with two stacks, where each enqueue and dequeue takes amortized O(1) time.

3

What are the main types of queues?

A queue is a FIFO data structure by default: elements are inserted at the rear and removed from the front. Several variants change that behavior to support different scheduling, buffering, and traversal requirements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Common Queue Types

Type Behavior Typical uses
Simple FIFO queue Preserves insertion order Task scheduling, buffering, breadth-first search
Circular queue Reuses a fixed-size array by wrapping indices with modulo Embedded systems, audio buffers, bounded producer-consumer workloads
Double-ended queue Inserts and removes elements at both ends Sliding windows, work-stealing, reversible processing
Priority queue Removes the highest-priority element rather than the oldest Scheduling, Dijkstra’s algorithm, event processing
Monotonic deque Maintains elements in sorted order while removing dominated entries Sliding-window maximum or minimum
Blocking or thread-safe queue Supports waiting and optional synchronization between threads Producer-consumer systems and worker pools

A bounded queue is a capacity policy that can be applied to several of these variants. It rejects or blocks new elements when full rather than growing indefinitely.

How the Variants Work

  • Simple FIFO: Use collections.deque in Python. append adds to the rear, while popleft removes from the front.

  • Circular queue: Store elements in a fixed array and maintain head and tail indices. Each index advances using modulo capacity, allowing freed positions to be reused.

  • Double-ended queue: A deque supports append, appendleft, popleft, and popleft.

  • Priority queue: Python’s heapq implements a min-heap. Negate values when a max-heap is required.

  • Monotonic deque: Before adding an element, remove smaller elements from the back for a maximum or larger elements for a minimum. The front then contains the current extreme.

A circular queue can trace its states as follows:

Operation Queue state
Enqueue 10 [10]
Enqueue 20 [10, 20]
Dequeue [20], returning 10
Enqueue 30 [20, 30], reusing the freed slot
Dequeue [30], returning 20

Complexity

All space figures exclude the original input unless stated otherwise. These implementations use no recursion stack.

Structure or operation Time complexity Space complexity
FIFO deque append or popleft O(1) average and worst case O(n) for stored elements
Circular queue enqueue, dequeue, or peek O(1) average and worst case O(capacity)
Double-ended insertion or removal O(1) average and worst case O(n)
Heap insertion O(1) best case; O(log n) average and worst case O(n)
Heap minimum extraction O(log n) best, average, and worst case; O(1) for one element O(n)
Heap peek O(1) best, average, and worst case No additional space
Sliding-window monotonic deque O(n) total because each element is inserted and removed at most once O(k), where k is the window size

For a sliding-window maximum, each index enters the deque once and is removed from either end at most once. Therefore, processing all n elements takes O(n) total time.

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, value) in loops because both are O(n). Use deque.

  • A circular queue needs a reliable full-versus-empty check, commonly a separate size counter as in the example.

  • A priority queue is not FIFO: equal-priority elements may not preserve insertion order unless additional tie-breaking is used.

  • heapq.heapify modifies the supplied list in place. Copy it first if the original must remain unchanged.

  • queue.Queue is preferable to deque when multiple threads need blocking or synchronized producer-consumer behavior.

  • The implementations correctly handle empty queues, one element, duplicates, and negative values. Sorting order, graph connectivity, and cycles do not affect these queue operations.

4

How does a priority queue differ from a FIFO queue?

A priority queue removes elements according to a priority key rather than arrival order, while a standard FIFO queue always removes the element that has waited longest. Priority queues are commonly implemented with a binary heap, whereas FIFO queues commonly use collections.deque.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Behavior

A FIFO queue follows First In, First Out:

  • enqueue adds an element to the rear.

  • dequeue removes an element from the front.

  • The earliest inserted element is always removed first.

A priority queue follows a priority ordering:

  • The next element is selected using a priority key.

  • A min-priority queue selects the smallest key.

  • A max-priority queue selects the largest key.

  • Whether smaller or larger keys represent greater urgency depends on the application.

  • Equal-priority elements may be ordered FIFO, LIFO, or by another policy, depending on the implementation.

For example, consider the tasks email(2), deploy(1), and alert(3) in a min-priority queue:

Step Operation Heap contents by ascending key
1 Insert email(2) email(2)
2 Insert deploy(1) deploy(1), email(2)
3 Insert alert(3) deploy(1), email(2), alert(3)
4 Remove smallest key email(2), alert(3)
5 Remove smallest key alert(3)

Queue Variants and Use Cases

Variant Ordering Typical Python implementation Typical use
Simple FIFO queue Insertion order collections.deque Task processing and buffering
Circular queue FIFO with fixed capacity Fixed array and modulo-based head/tail indices Bounded buffers and embedded systems
Double-ended queue Insertion or removal at either end collections.deque Sliding windows and work-stealing
Priority queue Priority key, with an implementation-defined tie policy Binary heap; heapq provides a min-heap Scheduling, event processing, and Dijkstra’s algorithm

collections.deque.append() and collections.deque.popleft() are O(1), unlike list.pop(0), which shifts the remaining elements and takes O(n).

Use queue.Queue for a thread-safe producer-consumer queue. Use a process-safe queue such as multiprocessing.Queue when communicating between processes.

Complexity

The following heap complexities assume a binary-heap implementation:

Operation Best case Average case Worst case Reason
FIFO enqueue O(1) O(1) O(1) deque adds to an available end
FIFO dequeue O(1) O(1) O(1) deque removes from an available end
Priority-queue peek O(1) O(1) O(1) The heap root contains the next element
Binary-heap insertion O(1) O(log n) O(log n) The new element may sift toward the root
Binary-heap removal O(1) O(log n) O(log n) The replacement element may sift downward
Circular-queue enqueue/dequeue O(1) O(1) O(1) Modulo-based index arithmetic updates the fixed array directly

Space usage depends on the variant:

  • FIFO queue using deque: O(n) total space for n stored elements, including the stored elements, plus O(1) auxiliary working space.

  • Binary-heap priority queue: O(n) total space for n stored elements, including the stored elements, plus O(1) temporary working space per operation.

  • Fixed-capacity circular queue: O(capacity) total space, including unused array slots, plus O(1) auxiliary working space.

These bounds count the queue’s stored elements but not a separate source collection retained by the caller. None of these core operations requires a recursion stack.

Common Pitfalls

  • Choosing the wrong priority direction: heapq is a min-heap; the application must define which key direction represents greater urgency.

  • Ignoring equal priorities: Decide explicitly whether ties should be FIFO, LIFO, or ordered by another field. heapq is not inherently stable for equal priority keys.

  • Using a list as a FIFO queue: list.pop(0) is O(n); use collections.deque.popleft().

  • Using the wrong synchronization primitive: heapq is not a thread-safe producer-consumer queue.

  • Off-by-one errors: A circular queue must represent full and empty states unambiguously when using modulo-based indices.

  • Integer overflow in other languages: Negating a priority to emulate a max-heap can overflow a fixed-width integer; use a safe comparator instead.

  • Mutating input and missing visits: Document whether an operation consumes or modifies supplied data, and mark graph vertices visited when enqueuing them to prevent duplicate processing.

  • Likely follow-up: Interviewers commonly ask about tie-breaking, complexity, bounded capacity, and thread safety.

5

When to Use a Stack or Queue Instead of a List?

A stack provides last-in, first-out (LIFO) removal, while a queue provides first-in, first-out (FIFO) removal. Use either when processing order is part of the requirement; use an ordinary list when direct indexed access or updates are the main operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Distinction

A list is a general-purpose collection, while a stack and queue define access policies:

  • Stack: The most recently added element is removed first, as with undo history, expression evaluation, and backtracking.

  • Queue: The earliest added element is removed first, as with customer lines, task schedulers, and printers.

  • Priority queue: The most important element is removed first according to a comparison key, rather than insertion order.

The underlying storage may be an array, linked list, or deque. The key decision is which ordering guarantee the application needs.

Choosing a Structure

Requirement Recommended structure Reason
Undo, backtracking, or call-frame management Stack Reverses the order of recent work
Process tasks in arrival order Queue Preserves FIFO ordering
Process by urgency, cost, or another priority Priority queue Orders elements by a comparison key
Access or update elements by index List Indexed access and assignment are O(1)
Search for a value in a collection Usually list or set List search is O(n); a set lookup is O(1) average
Perform frequent removals from the front in Python collections.deque Avoids the O(n) cost of list.pop(0)
Enforce a fixed capacity Circular queue Reuses bounded storage without shifting elements
Maintain sliding-window candidates Monotonic deque Removes dominated candidates efficiently

Useful Variants

  • Simple FIFO queue: Use collections.deque; append() and popleft() are O(1).

  • Double-ended queue: collections.deque supports insertion and removal at both ends. Operations such as append(), appendleft(), pop(), and popleft() are O(1).

  • Stack in Python: Use list.append() and list.pop() to manipulate the end of a list efficiently.

  • Two-stack queue: Enqueue into one stack and transfer elements to the other during dequeuing. Each element is transferred at most once, giving amortized O(1) operations.

  • Circular queue: Store elements in a fixed-size buffer and advance head and tail modulo the capacity. A size counter distinguishes a full queue from an empty one.

  • Priority queue: Use heapq, which implements a min-heap. For a max-heap with numeric priorities, negate the priority values.

  • Monotonic deque: Remove dominated candidates from the back and expired candidates from the front. Every element is inserted and removed at most once, so total work is O(n).

For a FIFO trace with ["A", "B", "C"], the queue progresses from [] to ["A"], ["A", "B"], and ["A", "B", "C"], then back to [] as elements are dequeued.

Complexity

Space convention: total storage includes elements retained by the structure. Auxiliary space excludes the caller’s input unless the algorithm copies it. These operations are iterative, so the recursion stack is O(1).

Structure Time Space Reason
List as stack O(1) best; amortized O(1) per operation; O(n) worst when an operation triggers resizing O(n) total; O(1) auxiliary Only the final element is removed
deque as FIFO queue O(1) O(n) total; O(1) auxiliary Operations affect only an endpoint
Two-stack queue O(1) enqueue; amortized O(1) dequeue, with O(n) worst during a transfer O(n) total; O(1) auxiliary Each element moves between stacks at most once
Circular queue O(1) enqueue and dequeue O(capacity) total; O(1) auxiliary Head and tail use modulo indexing
heapq priority queue O(log n) insert/remove; O(1) minimum lookup O(n) total; O(1) auxiliary Maintains the heap property
Monotonic deque O(n) total O(k) auxiliary, where k is the window size Each candidate enters and leaves once

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, value) in loops; both are O(n).

  • Do not mutate the caller’s input unexpectedly; copy it only when independent state is required.

  • Define behavior for empty and one-element inputs, including whether an empty dequeue raises an exception or returns a sentinel.

  • Duplicates and negative values are valid unless the problem assigns special priorities or deduplication rules. Sorted input does not change queue complexity.

  • For BFS, mark a vertex when it is enqueued to prevent cycles and repeated visits. Start another BFS from an unvisited vertex if every disconnected component must be processed.

  • Interviewers commonly ask why deque is preferred for FIFO queues, how a circular queue distinguishes full from empty, and how a priority queue differs from ordinary FIFO ordering.

6

How do you reverse a FIFO queue?

A FIFO queue can be reversed using a stack: dequeue every element, push it onto a stack, and then pop the elements back into the queue. Since a stack is LIFO, the elements re-enter the queue in reverse order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Approach

  1. Remove elements from the queue’s front and push them onto a stack.

  2. Pop each element from the stack and enqueue it.

For a queue containing A, B, C:

Operation Queue, front to rear Stack, top on right
Initial state A, B, C []
Dequeue A B, C [A]
Dequeue B C [A, B]
Dequeue C [] [A, B, C]
Pop C [C] [A, B]
Pop B [C, B] [A]
Pop A [C, B, A] []

This works with any FIFO queue whose dequeue and enqueue operations take O(1) time.

Queue Variants

  • Simple FIFO queue: The stack-transfer method is the standard queue-interface solution.

  • collections.deque: Use popleft() and append(), both O(1). Its reverse() method is an O(n), in-place alternative.

  • Circular queue: The stack-transfer method needs O(n) auxiliary space. An array-backed implementation can instead swap logical positions using (head + offset) % capacity, taking O(n) time and O(1) auxiliary space.

  • Double-ended queue: deque.reverse() reverses a deque in place in O(n) time.

  • Priority queue: heapq implements a min-heap; negate values for a max-heap. A priority queue is not FIFO, and reversing its heap array followed by heapify() does not reverse its extraction order. Record the extraction order separately if that exact sequence must be preserved.

  • Monotonic deque: Reversing it may invalidate its monotonic invariant; recompute it if later sliding-window operations depend on that property.

  • queue.Queue: Use it for thread-safe producer/consumer code. Its individual operations are synchronized, but an entire reversal must be protected by one lock so producers and consumers cannot interleave with it.

Complexity

Approach Best time Average time Worst time Auxiliary space
Stack transfer O(n) O(n) O(n) O(n)
deque.reverse() O(n) O(n) O(n) O(1)
Circular-array swaps O(n) O(n) O(n) O(1)
  • Stack-transfer time: O(n). List append() and pop() are amortized O(1), so the complete transfer remains O(n) in total.

  • Auxiliary space: O(n) for the stack, excluding the input queue; O(n) including it.

  • Recursion stack: None because the implementation is iterative.

Code Example

from collections import deque
from typing import Generic, TypeVar, cast

T = TypeVar("T")


def reverse_queue(queue: deque[T]) -> None:
    """Reverse a deque in place by transferring its elements through a stack."""
    stack: list[T] = []

    while queue:
        stack.append(queue.popleft())

    while stack:
        queue.append(stack.pop())


class CircularQueue(Generic[T]):
    """Fixed-capacity FIFO queue backed by an array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._items: list[T | None] = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, value: T) -> None:
        """Add an element at the logical rear."""
        if self._size == self._capacity:
            raise OverflowError("queue is full")
        self._items[self._tail] = value
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self) -> T:
        """Remove and return the element at the logical front."""
        if self._size == 0:
            raise IndexError("queue is empty")
        value = cast(T, self._items[self._head])
        self._items[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def reverse_in_place(self) -> None:
        """Reverse the logical order without changing head or tail."""
        for offset in range(self._size // 2):
            left = (self._head + offset) % self._capacity
            right = (self._head + self._size - 1 - offset) % self._capacity
            self._items[left], self._items[right] = (
                self._items[right],
                self._items[left],
            )


values = deque(["A", "B", "C"])
reverse_queue(values)
print(list(values))  # ['C', 'B', 'A']

circular = CircularQueue[str](3)
circular.enqueue("A")
circular.enqueue("B")
circular.enqueue("C")
circular.reverse_in_place()
print(circular.dequeue())  # C
print(circular.dequeue())  # B
print(circular.dequeue())  # A

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, value) for queue operations because both shift O(n) elements.

  • The reversal functions mutate the original queue; return a new queue if the caller requires the input to remain unchanged.

  • Empty and one-element queues remain valid, while duplicates and negative values require no special handling.

  • In a circular queue, test full versus empty using the element count, not head == tail; incorrect offsets cause off-by-one errors.

  • In languages with fixed-width integers, ensure capacity and index arithmetic cannot overflow.

  • A visited set is irrelevant to queue reversal but required for graph traversal; an outer traversal loop is also needed for disconnected graphs.

  • Interviewers commonly follow up with a circular queue, queue implemented using two stacks, BFS, or thread-safe producer-consumer design.

7

Can a queue be implemented with a static array?

A static queue can be implemented using a fixed-size array, usually arranged as a circular queue. This provides constant-time insertion and removal while preventing wasted space at the front of the array, but the queue has a fixed capacity and cannot grow when it becomes full.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A circular queue stores elements in an array and uses two indices:

  • front: the position of the next element to remove.

  • size: the number of elements currently stored.

  • The next insertion position is calculated as (front + size) % capacity.

When the front or insertion index reaches the end of the array, the modulo operation wraps it back to the beginning. A separate size counter distinguishes an empty queue from a full queue.

For example, with capacity 3:

Operation Array state Queue contents
Initially [None, None, None] Empty
Enqueue 10 [10, None, None] [10]
Enqueue 20 [10, 20, None] [10, 20]
Enqueue 30 [10, 20, 30] [10, 20, 30]
Dequeue 10 [None, 20, 30] [20, 30]
Enqueue 40 [40, 20, 30] [20, 30, 40]

Limitations

  • Fixed capacity: The queue cannot store more than the allocated capacity.

  • Overflow: An enqueue operation fails when the queue is full unless the implementation resizes the backing array.

  • Underflow: A dequeue operation fails when the queue is empty.

  • Memory allocation choice: A capacity that is too small causes rejected operations; a capacity that is too large wastes memory.

  • Not dynamically resizable: A truly static implementation cannot automatically grow, unlike collections.deque or a dynamically allocated array.

  • Synchronization: A static array queue is not automatically safe for concurrent access. For thread-safe producer-consumer code, use queue.Queue.

A non-circular static array can also represent a FIFO queue, but removing the front element usually requires shifting the remaining elements, making each dequeue operation O(n). A circular array avoids that shifting.

Queue Variants

  • Simple FIFO queue: Elements are inserted at the rear and removed from the front. collections.deque is the usual dynamic Python implementation.

  • Circular queue: Uses a fixed array with wrapped indices, allowing all array positions to be used.

  • Double-ended queue: Allows insertion and removal at both ends. collections.deque supports this directly.

  • Priority queue: Removes the highest- or lowest-priority element rather than strictly following FIFO order. Python’s heapq implements a min-heap.

Complexity

For a circular queue with capacity C:

Operation Best case Average case Worst case Reason
enqueue O(1) O(1) O(1) Direct index calculation and assignment
dequeue O(1) O(1) O(1) Direct index calculation and assignment
peek O(1) O(1) O(1) Direct access to the front element
Construction O(C) O(C) O(C) The fixed backing array is initialized
  • Space complexity: O(C) for the backing array, with O(1) additional metadata.

  • The input is not counted separately; the queue’s stored elements are the data structure’s storage.

  • A naive array implementation that shifts elements has O(n) dequeue time, while collections.deque has amortized O(1) append and popleft operations.

Code Example

class StaticQueue:
    """Fixed-capacity FIFO queue implemented with a circular array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be greater than zero")

        self._capacity = capacity
        self._items: list[int | None] = [None] * capacity
        self._front = 0
        self._size = 0

    def enqueue(self, value: int) -> bool:
        """Add an item if the queue has capacity; otherwise return False."""
        if self._size == self._capacity:
            return False

        rear = (self._front + self._size) % self._capacity
        self._items[rear] = value
        self._size += 1
        return True

    def dequeue(self) -> int | None:
        """Remove and return the front item, or None if the queue is empty."""
        if self._size == 0:
            return None

        value = self._items[self._front]
        self._items[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return value

    def peek(self) -> int | None:
        """Return the front item without removing it."""
        if self._size == 0:
            return None
        return self._items[self._front]

    def is_empty(self) -> bool:
        """Return whether the queue contains no items."""
        return self._size == 0

    def is_full(self) -> bool:
        """Return whether the queue has reached its fixed capacity."""
        return self._size == self._capacity


queue = StaticQueue(capacity=3)

print(queue.enqueue(10))    # True
print(queue.enqueue(20))    # True
print(queue.enqueue(30))    # True
print(queue.enqueue(40))    # False
print(queue.dequeue())      # 10
print(queue.enqueue(40))    # True
print(queue.dequeue())      # 20
print(queue.dequeue())      # 30
print(queue.dequeue())      # 40
print(queue.dequeue())      # None

Common Pitfalls

  • Confusing full and empty: Without a size counter, a circular array can make these states look identical. Using a count, as in the example, avoids that problem.

  • Using list.pop(0): It removes the first element by shifting the remaining elements and takes O(n) time.

  • Failing to clear removed slots: Clearing the slot after dequeuing prevents stale references from unnecessarily retaining objects.

  • Ignoring capacity planning: A fixed queue must either reject overflow, reserve extra capacity, or be replaced with a dynamically growing structure.

  • Forgetting thread safety: A basic array queue is not suitable for concurrent producers and consumers without synchronization.

8

How do you enqueue and dequeue items in a FIFO queue?

A FIFO queue stores items in first-in, first-out order: enqueue adds an item at the back, while dequeue removes the oldest item from the front. In Python, collections.deque implements both operations efficiently without shifting the remaining elements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Operations

  • Enqueue: Add an item to the back of the queue using append(item).

  • Dequeue: Remove and return the item at the front using popleft().

  • Ordering: If A, then B, are enqueued, the first dequeue returns A, and the next returns B.

  • Common uses: Breadth-first search, task scheduling, buffering, and rate limiting.

Unlike a Python list, deque.popleft() does not shift every remaining element, so it avoids the O(n) cost of list.pop(0).

Complexity

Let n be the number of items currently stored in the queue.

Operation Best Average Worst Reason
Enqueue with append O(1) O(1) O(1) Items are added at the back; deque uses a block-linked list so no resizing copies
Dequeue with popleft O(1) O(1) O(1) The front item is removed directly without shifting other elements
  • Total space: O(n), counting the items stored in the queue as input.

  • Auxiliary space per operation: O(1).

  • Recursion stack: O(1) because the implementation is not recursive.

Across a sequence of m enqueue operations, the total time is O(m).

Queue Variants

  • Circular queue: Uses a fixed-size array with head and tail indices calculated modulo capacity. It avoids moving elements but must track fullness and emptiness carefully.

  • Double-ended queue: collections.deque also supports insertion and removal at both ends in O(1) time.

  • Priority queue: heapq implements a min-heap. Insertion and removal take O(log n) time and require O(n) space.

  • Monotonic deque: Used for sliding-window maximums. Each element is pushed and popped at most once, giving O(n) total time and O(n) space.

  • Thread-safe queue: Use queue.Queue for producer-consumer or multithreaded code; it is unnecessary for a single-threaded FIFO queue.

Example Walkthrough

  1. Start with an empty queue: []

  2. Enqueue 10: [10]

  3. Enqueue -5: [10, -5]

  4. Enqueue 10: [10, -5, 10]

  5. Dequeue and print the result: 10; the queue becomes [-5, 10]

Duplicates and negative numbers are retained unchanged, and already sorted input is not reordered.

Code Example

from collections import deque


def enqueue(queue: deque[int], item: int) -> None:
    """Add an item to the back of the FIFO queue."""
    queue.append(item)


def dequeue(queue: deque[int]) -> int:
    """Remove and return the oldest item from the FIFO queue."""
    if not queue:
        raise IndexError("dequeue from empty queue")
    return queue.popleft()


def run_queue_example() -> None:
    """Demonstrate FIFO enqueue and dequeue behavior."""
    queue: deque[int] = deque()
    enqueue(queue, 10)
    enqueue(queue, -5)
    enqueue(queue, 10)

    print(dequeue(queue))
    print(dequeue(queue))
    print(dequeue(queue))


if __name__ == "__main__":
    run_queue_example()
    # Output:
    # 10
    # -5
    # 10

Common Pitfalls

  • Empty queue: Calling popleft() directly raises IndexError; check if not queue when the empty case is possible.

  • Using a list: list.pop(0) and list.insert(0, item) are O(n) because they shift elements.

  • Mutating state unexpectedly: Dequeue removes an item permanently; do not clear or reuse the queue unless that is intended.

  • Circular-buffer boundaries: Off-by-one errors can incorrectly report a full queue as empty. Track a count or reserve one slot.

  • BFS with cycles: Always maintain a visited set to avoid repeatedly processing cyclic paths. For disconnected graphs, start BFS from every unvisited vertex.

  • Integer overflow: In fixed-capacity implementations in languages such as Java or C++, ensure index calculations cannot overflow.

9

How to build a FIFO queue with O(1) enqueue and O(n) dequeue?

A shifting-array queue stores elements in a preallocated array. Enqueue writes directly at the next available position, while dequeue removes the first element and shifts every remaining element one position toward the front.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Design

  • Enqueue: Place the new element at index size, then increment size.

  • Dequeue: Read index 0, shift the remaining size - 1 elements left, and decrement size.

  • Capacity: The array has a fixed capacity, preventing resizing and ensuring strict O(1) enqueue.

  • Ordering: The structure behaves as a FIFO queue because elements are removed in insertion order.

This deliberately trades dequeue performance for strict enqueue performance. In production, collections.deque is normally preferable because both append() and popleft() are O(1).

Complexity

Let n be the number of elements currently queued and C the array capacity.

Operation Best Average Worst Reason
enqueue O(1) O(1) O(1) Writes into an existing array slot without resizing
dequeue O(n) O(n) O(n) Shifts up to n - 1 elements
Total storage O(C) O(C) O(C) The fixed-capacity array is retained
Auxiliary space O(1) O(1) O(1) No recursion or additional collections

The queue’s own storage is included in O(C). There is no recursion stack, and no separate input array is used.

Code Example

from typing import Generic, TypeVar, cast

T = TypeVar("T")


class ShiftingArrayQueue(Generic[T]):
    """A bounded FIFO queue whose dequeue shifts remaining elements."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self._items: list[object] = [None] * capacity
        self._capacity = capacity
        self._size = 0

    def enqueue(self, value: T) -> None:
        """Add an element to the back of the queue."""
        if self._size == self._capacity:
            raise OverflowError("queue is full")

        self._items[self._size] = value
        self._size += 1

    def dequeue(self) -> T:
        """Remove and return the element at the front of the queue."""
        if self._size == 0:
            raise IndexError("queue is empty")

        value = self._items[0]

        # Shift remaining elements one position toward the front.
        for index in range(self._size - 1):
            self._items[index] = self._items[index + 1]

        self._items[self._size - 1] = None
        self._size -= 1
        return cast(T, value)

    def __len__(self) -> int:
        return self._size


def run_queue_demo() -> None:
    queue = ShiftingArrayQueue[str](capacity=3)
    queue.enqueue("first")
    queue.enqueue("second")
    queue.enqueue("third")

    print(queue.dequeue())
    print(queue.dequeue())


if __name__ == "__main__":
    run_queue_demo()

# Expected output:
# first
# second

Example Walkthrough

Starting with an empty capacity-three queue:

  1. Enqueue "first" produces ["first", None, None].

  2. Enqueue "second" produces ["first", "second", None].

  3. Enqueue "third" produces ["first", "second", "third"].

  4. Dequeue returns "first" and shifts the queue to ["second", "third", None].

  5. Dequeue returns "second" and shifts it to ["third", None, None].

Common Pitfalls

  • Empty queue: Calling dequeue() raises IndexError; check the size first when the input is untrusted.

  • One element: Dequeue succeeds in O(1) because there are no elements to shift.

  • Full queue: The implementation raises OverflowError instead of resizing.

  • Duplicates and negative values: Both are stored normally without affecting FIFO behavior.

  • Ordering: Already sorted or unsorted input values remain in insertion order; the queue does not reorder them.

  • Alternative designs: A dynamic Python list has amortized O(1) enqueue but occasional O(n) resizing. A circular queue and collections.deque provide O(1) enqueue and dequeue.

  • Thread safety: Use queue.Queue for thread-safe producer-consumer systems; this array implementation is not synchronized.

  • Interview follow-up: Interviewers may ask how to implement the same behavior with two stacks, where operations can achieve amortized O(1) time.

10

When should dequeue complexity take priority over enqueue in a queue?

Dequeue complexity takes priority when front removals are frequent, latency-sensitive, and contribute more to total runtime than insertions. The relevant trade-off is the number of operations multiplied by each operation’s cost; dequeue optimization deserves priority when that product is larger for dequeueing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Dequeue Takes Priority

  • BFS traversal: Vertices are removed from the front while new vertices are added at the back. Efficient removal prevents queue operations from dominating the traversal.

  • Task processing: Workers repeatedly remove the next job while producers add work at the tail.

  • Rate limiting: A FIFO queue can preserve request order while controlling how quickly requests are admitted.

  • Streaming buffers: Low head-of-line latency can matter more than occasional or batched insertions.

  • Removal-sensitive workloads: If dequeue latency is on the critical path, optimizing it may be more valuable than optimizing a less frequent enqueue operation.

A FIFO queue must preserve insertion order, so it cannot solve a dequeue bottleneck by simply removing items from the tail.

Complexity Trade-offs

Implementation Enqueue Dequeue Queue space Reason
Python list with pop(0) O(1) amortized O(n) worst O(n) pop(0) shifts the remaining elements
collections.deque O(1) best/average/worst O(1) best/average/worst O(n) Supports constant-time operations at both ends
Linked list with head and tail O(1) best/average/worst O(1) best/average/worst O(n) Updates pointers and stores one node per item
Fixed circular array O(1) best/average/worst O(1) best/average/worst O(k) Updates head and tail indices modulo capacity

For a Python list, pop(0) is O(n) on average and in the worst case, except for trivial one-element lists. List insertion is O(1) amortized but can take O(n) during a resize. The other listed queue operations are constant-time in all three cases.

These space bounds count stored queue elements and exclude the original input. Complete BFS requires O(V) auxiliary space for the queue and visited set; including the returned order, total extra memory remains O(V). The graph input is not counted, and an iterative BFS has no recursion stack.

Queue Variants

  • Simple FIFO queue: Use collections.deque with append() and popleft() for constant-time insertion and removal.

  • Circular queue: Store elements in a fixed array and maintain head and tail indices modulo capacity, plus a size counter to distinguish full from empty. Space is O(k).

  • Double-ended queue: collections.deque also supports appendleft() and popleft() in O(1) time.

  • Priority queue: Use heapq; insertion and removal take O(log n) because the heap is reordered, and space is O(n). Negate numeric values to emulate a max-heap.

  • Monotonic deque: Maintain candidate values in decreasing order for sliding-window maximum. Expired elements are removed from the front and dominated elements from the back; every element is pushed and popped at most once, giving O(n) total time and O(k) space for a window of size k.

  • Thread-safe queue: Use queue.Queue for producer-consumer applications requiring locking and synchronization.

BFS Walkthrough

For A -> [B, C], B -> [D], and C -> [D, B]:

  1. Enqueue A: queue is [A].

  2. Dequeue A, then enqueue B and C: queue is [B, C].

  3. Dequeue B, then enqueue D: queue is [C, D].

  4. Dequeue C; D and B are already visited: queue is [D].

  5. Dequeue D: queue is empty.

Using a list with pop(0) can make the traversal O(V² + E) in the worst case, whereas collections.deque.popleft() keeps it O(V + E).

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, value) in loops because each operation can shift O(n) elements.

  • A circular queue must distinguish empty from full, commonly with a separate size counter.

  • Dequeueing from an empty queue should raise a clear exception.

  • With one element, dequeuing returns that item and leaves the queue empty; another dequeue must fail.

  • Duplicate payloads are valid and retain FIFO order; negative numeric values require no special handling.

  • FIFO preserves input order, so already sorted input remains sorted.

  • In BFS, mark vertices visited when enqueuing them to prevent duplicate entries in cycles.

  • Use an outer traversal for disconnected graphs so every component is visited.

11

How do you track minimum and maximum elements in a queue?

A monotonic deque efficiently maintains the minimum or maximum of a FIFO queue while supporting insertions and removals. It keeps only candidate elements that could still become the minimum or maximum, so queries take constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Use two collections.deque instances alongside the queue:

  • The minimum deque stores values in increasing order.

  • The maximum deque stores values in decreasing order.

  • Each deque stores an element’s index and value so expired elements can be removed when they leave the front of the queue.

When a new value is enqueued:

  • Remove values from the back of the minimum deque that are greater than or equal to the new value.

  • Remove values from the back of the maximum deque that are less than or equal to the new value.

  • Append the new value to both deques.

The removed elements are no longer needed: the new element is at least as useful as the minimum candidate and will remain in the queue longer. The same reasoning applies symmetrically to the maximum.

When the queue’s front element is dequeued, remove it from a candidate deque only if it is still present there. The front of each candidate deque then gives the current minimum or maximum.

For example, with values 5, 3, 8, 2, the minimum candidates become 2 and the maximum candidates become 8. After removing 5, the answers remain 2 and 8.

Complexity

Operation Best Average Worst Reason
enqueue O(1) O(1) amortized O(n) One insertion may remove many dominated candidates from the back
dequeue O(1) O(1) O(1) At most the expired candidate is removed from each deque
minimum / maximum O(1) O(1) O(1) The answer is at the front of a candidate deque
Total for n operations O(n) O(n) amortized O(n) Each candidate is pushed and popped at most once

The implementation uses O(n) total space, counting the stored queue values. Candidate metadata also uses O(n) space in the worst case. There is no recursion stack.

A simpler implementation that scans the queue for every query takes O(n) per query:

Approach Query time Enqueue time Space When to use
Scan the queue O(n) O(1) O(n) Small queues or infrequent queries
Running minimum/maximum O(1) O(1) O(1) extra Only additions; removals are not supported
Monotonic deque O(1) O(1) amortized O(n) Dynamic FIFO queues needing frequent queries

Code Example

from collections import deque
from typing import Generic, TypeVar

T = TypeVar("T")


class MinMaxQueue(Generic[T]):
    """FIFO queue that supports efficient minimum and maximum queries."""

    def __init__(self) -> None:
        self._items: deque[T] = deque()
        self._min_candidates: deque[tuple[int, T]] = deque()
        self._max_candidates: deque[tuple[int, T]] = deque()
        self._front_index = 0
        self._next_index = 0

    def enqueue(self, value: T) -> None:
        index = self._next_index
        self._next_index += 1
        self._items.append(value)

        # Older values dominated by the new value cannot be future minima.
        while self._min_candidates and self._min_candidates[-1][1] >= value:
            self._min_candidates.pop()
        self._min_candidates.append((index, value))

        # Older values dominated by the new value cannot be future maxima.
        while self._max_candidates and self._max_candidates[-1][1] <= value:
            self._max_candidates.pop()
        self._max_candidates.append((index, value))

    def dequeue(self) -> T:
        if not self._items:
            raise IndexError("dequeue from empty queue")

        value = self._items.popleft()
        expired_index = self._front_index
        self._front_index += 1

        if self._min_candidates and self._min_candidates[0][0] == expired_index:
            self._min_candidates.popleft()

        if self._max_candidates and self._max_candidates[0][0] == expired_index:
            self._max_candidates.popleft()

        return value

    def minimum(self) -> T:
        if not self._items:
            raise IndexError("minimum of empty queue")
        return self._min_candidates[0][1]

    def maximum(self) -> T:
        if not self._items:
            raise IndexError("maximum of empty queue")
        return self._max_candidates[0][1]

    def __len__(self) -> int:
        return len(self._items)


if __name__ == "__main__":
    queue = MinMaxQueue[int]()
    queue.enqueue(5)
    queue.enqueue(3)
    queue.enqueue(8)
    queue.enqueue(2)

    print(queue.minimum(), queue.maximum())  # 2 8
    print(queue.dequeue())                  # 5
    print(queue.minimum(), queue.maximum())  # 2 8

Queue Variants

  • Simple FIFO queue: collections.deque provides O(1) append and popleft; finding a minimum or maximum by scanning takes O(n).

  • Circular queue: A fixed-size array with head and tail indices modulo capacity supports O(1) operations, but requires careful handling of the full and empty states.

  • Double-ended queue: collections.deque also supports appendleft, pop, and popleft, each in O(1).

  • Priority queue: heapq is a min-heap with O(log n) insertion and removal and O(1) minimum lookup. For a maximum heap, negate the values.

  • Thread-safe queue: Use queue.Queue for producer-consumer systems; use collections.deque for ordinary single-threaded queue operations.

Common Pitfalls

  • Do not use list.pop(0) or list.insert(0, value) in a loop; both are O(n).

  • Removing equal values from the candidate deques is safe because the newer equal value survives longer.

  • Check for an empty queue before calling dequeue, minimum, or maximum.

  • The monotonic-deque implementation assumes values support comparison operators.

  • Edge cases require no special algorithm: an empty queue raises IndexError; a one-element queue returns that element for both extrema; duplicate values are supported; negative values work with ordinary comparisons; and already sorted input follows the same rules.

  • For sliding-window maximum problems, use a monotonic deque so each element is pushed and popped at most once, giving O(n) total time.

  • Interviewers may ask how the algorithm changes for a sliding window, a deque, or a queue with priorities.

12

How do you merge multiple queues with efficient dequeuing?

Use a round-robin merge that repeatedly dequeues one element from each non-empty source queue and appends it to the destination queue. This preserves the original order within every source while ensuring each dequeue from the merged queue takes O(1) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Merge Strategy

Maintain an auxiliary deque containing the source queues that still have elements:

  1. Remove the first active source from the auxiliary deque.

  2. Dequeue its front element and append it to the merged queue.

  3. If that source still contains elements, put it at the back of the auxiliary deque.

  4. Repeat until all sources are empty.

The active-queue deque follows a FIFO rotation. Empty sources are skipped initially and removed permanently once exhausted.

Step-by-Step Example

Given A = [1, 2, 4], B = [3, 5, 6], and C = [7, 8]:

Step Source used Element appended Merged result
1 A 1 [1]
2 B 3 [1, 3]
3 C 7 [1, 3, 7]
4 A 2 [1, 3, 7, 2]
5 B 5 [1, 3, 7, 2, 5]
6 C 8 [1, 3, 7, 2, 5, 8]
7 A 4 [1, 3, 7, 2, 5, 8, 4]
8 B 6 [1, 3, 7, 2, 5, 8, 4, 6]

Each source’s internal order remains unchanged.

Merge Policies and Queue Variants

Requirement Appropriate approach Trade-off
Preserve each source’s order with interleaving Round-robin merge Does not guarantee global arrival order
Keep source queues in contiguous blocks Concatenate queues Does not interleave elements
Produce global timestamp order Min-heap containing the front of each queue O(N log k) total time
Bounded fixed-capacity storage Circular queue Uses fixed array and modulo-based head/tail indices
Producer-consumer communication queue.Queue Provides locking, but is unnecessary for single-threaded merging

collections.deque is the standard Python FIFO implementation because append() and popleft() are O(1). It also supports double-ended operations. A priority queue uses heapq and orders by priority rather than arrival time. A monotonic deque is specialized for problems such as sliding-window maximum, where every element is pushed and popped once in O(n), but is not an appropriate structure for merging independent queues.

Complexity

Let N be the total number of elements and k the number of source queues.

  • Per dequeue from merged queue: O(1) best, average and worst case because deque.popleft() removes an endpoint directly.

  • Complete merge: O(N + k) best, average and worst case. Every element is moved once, and each source is added to the active deque once.

  • Auxiliary space: O(k), excluding input and output, because the active deque stores one reference per non-empty source.

  • Output space: O(N) for the merged queue.

  • Total space: O(N + k) when output and auxiliary storage are counted; O(N + k) overall when the input queues are also counted.

If the merged elements are consumed immediately rather than collected, the algorithm can stream them with O(k) auxiliary space.

Code Example

from collections import deque
from typing import TypeVar

T = TypeVar("T")


def merge_queues_round_robin(*queues: deque[T]) -> deque[T]:
    """Merge queues round-robin, consuming the source queues."""
    if len(queues) < 2:
        raise ValueError("At least two queues are required")

    active: deque[deque[T]] = deque(
        source_queue for source_queue in queues if source_queue
    )
    merged: deque[T] = deque()

    while active:
        source_queue = active.popleft()
        merged.append(source_queue.popleft())

        # Reinsert only queues that still contain elements.
        if source_queue:
            active.append(source_queue)

    return merged


first = deque([1, 2, 4])
second = deque([3, 5, 6])
third = deque([7, 8])

result = merge_queues_round_robin(first, second, third)
print(result)  # deque([1, 3, 7, 2, 5, 8, 4, 6])

The function handles empty queues, single-element queues, duplicates and negative values. It consumes the source queues; preserving them requires copying them first, which adds O(N) time and space.

Common Pitfalls

  • Using list.pop(0): Removing the first list element is O(n); use collections.deque instead.

  • Assuming global FIFO order: Round-robin merging does not reconstruct arrival order across queues. Use timestamps and a heap when global ordering is required.

  • Reinserting exhausted queues: Check if source_queue before appending it back to the active deque.

  • Ignoring mutation: The implementation empties the source queues. Document this behavior or copy the inputs when non-destructive merging is required.

  • Confusing circular-queue state: A fixed-array circular queue should track occupancy separately from head and tail, which are advanced using (index + 1) % capacity.

Common interview follow-ups include preserving source queues, merging by timestamp, enforcing bounded capacity, adding backpressure, and making the producer-consumer implementation thread-safe with queue.Queue.

13

What are common queue implementations and their efficiency?

Common queue implementations trade FIFO ordering, operation cost, and memory usage. A FIFO queue preserves insertion order, while circular queues, deques, priority queues, and two-stack queues optimize different access patterns.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Common Implementations

  • List-based FIFO: Appending to the end is O(1) amortized, but list.pop(0) is O(n) because the remaining elements must shift. Reading the front is O(1). Space is O(n) total for the stored elements, including O(1) auxiliary space beyond them. This is unsuitable for frequent dequeues.

  • Linked-list queue: Maintains front and rear nodes. Enqueue, dequeue, and front access are O(1) in the best, average, and worst cases. Space is O(n) total, including O(1) auxiliary space beyond the stored elements.

  • Circular queue: Uses a fixed array, a head index for removal, a tail index for insertion, and a count to distinguish empty from full. Both indices advance modulo capacity, so enqueue, dequeue, and front access are O(1) in all cases. Space is O(capacity) total with O(1) auxiliary bookkeeping.

  • Double-ended queue: Python’s collections.deque supports append, appendleft, popleft, and popleft. These are O(1) best-case and amortized on average; an operation that triggers an internal resize can take O(n) in the worst case. Space is O(n) total.

  • Priority queue: heapq implements a min-heap. For numeric values, negation supports a max-heap. Push and pop are O(log n) upper bounds, while peeking is O(1). Space is O(n) total with O(1) auxiliary space.

  • Two-stack FIFO queue: Uses an incoming stack and an outgoing stack. Enqueue is O(1). Dequeue and peek are O(1) best-case, O(1) amortized on average, and O(n) in the worst case when all elements must be transferred. Space is O(n) total.

  • Thread-safe queue: queue.Queue provides locking and blocking for producer-consumer code. Its queue bookkeeping is O(1) in the best, average, and worst cases once a lock is acquired; contention and blocking add environment-dependent waiting time. Space is O(q) for q queued elements plus O(1) auxiliary state.

  • Monotonic deque: For sliding-window maximum, candidate indices are stored in non-increasing value order. Each index is inserted and removed at most once, so the complete algorithm takes O(n) time in all cases. Auxiliary space is O(k) for a window of size k, excluding the input array; O(n) total if the input is counted.

Typical uses include BFS, task scheduling, request buffering, rate limiting, and producer-consumer communication.

Efficiency Comparison

Implementation Best time Average time Worst time Space
List-based FIFO O(1) enqueue; O(1) peek O(1) amortized enqueue; O(n) dequeue O(n) enqueue resize or dequeue O(n) total
collections.deque O(1) O(1) amortized O(n) rare resize O(n) total
Fixed circular queue O(1) O(1) O(1) O(capacity) total
Linked-list queue O(1) O(1) O(1) O(n) total
heapq priority queue O(log n) push/pop; O(1) peek O(log n) push/pop; O(1) peek O(log n) push/pop O(n) total
Two-stack FIFO O(1) O(1) amortized O(n) transfer O(n) total
Monotonic-deque algorithm O(n) total O(n) total O(n) total O(k) auxiliary

Total-space figures include stored queue elements; auxiliary space excludes them. No implementation uses recursion, so the recursion-stack space is O(1).

Circular Queue Walkthrough

For capacity 3, head identifies the next removal, tail identifies the next insertion, and both advance modulo capacity:

Operation Head Tail Size Array Queue order
Initial 0 0 0 [None, None, None] Empty
Enqueue A 0 1 1 [A, None, None] A
Enqueue B 0 2 2 [A, B, None] A, B
Dequeue A 1 2 1 [None, B, None] B
Enqueue C 1 0 2 [None, B, C] B, C

The size is necessary because the head and tail indices alone may be identical in both the empty and full states.

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, item) in loops; each is O(n) per operation.

  • Circular queues must handle empty, one-element, full, and wrapped-index states correctly.

  • FIFO queues preserve duplicates; dequeueing the only element leaves the queue empty.

  • heapq is a min-heap. Numeric negation also works with negative values, but equal-priority entries do not have guaranteed insertion-order stability.

  • Monotonic deques must remove expired indices and dominated values; equal values require an explicit tie-breaking policy.

  • queue.Queue adds synchronization and potentially blocking behavior; it is not a faster replacement for deque.

  • Common follow-up questions cover thread safety, fixed versus growable capacity, priority ordering, two-stack queues, and sliding-window maximum.

14

How does an array-based Queue work, and what are its disadvantages?

An array-based Queue stores FIFO elements in contiguous array slots and tracks the positions from which elements are removed and added. A circular implementation wraps indices back to the beginning, avoiding the expensive array shifting required by a basic linear implementation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A circular queue maintains three values:

  • head: Index of the next element to remove.

  • tail: Index where the next element will be inserted.

  • size: Number of elements currently stored.

Indices are calculated using modulo arithmetic, such as (tail + 1) % capacity. This allows the queue to reuse positions at the beginning after elements at the end have been removed.

For example, with capacity 3:

  1. Enqueue 10, 20, and 30; the queue becomes full.

  2. Dequeue 10; head advances to index 1.

  3. Enqueue 40; it is placed at index 0 because tail wraps around.

  4. The FIFO order is now 20, 30, 40.

A non-circular array queue can also shift all remaining elements forward after each dequeue. That approach is simpler but makes dequeue an O(n) operation.

Complexity

Operation Best Average Worst Reason
enqueue O(1) O(1) O(1) Writes directly to the calculated tail index.
dequeue O(1) O(1) O(1) Reads from head and advances it without shifting.
is_empty / is_full O(1) O(1) O(1) Checks the stored size.
Initialization O(capacity) O(capacity) O(capacity) Allocates and initializes the backing array.
  • Total space: O(capacity) for the backing array.

  • Auxiliary space: O(1) beyond that array.

  • Recursion stack: O(1), because no recursion is used.

  • The queue’s own stored elements are counted in its total space; there is no separate input array.

Code Example

class QueueEmptyError(Exception):
    """Raised when removing from an empty queue."""


class QueueFullError(Exception):
    """Raised when adding to a full queue."""


class ArrayQueue:
    """Fixed-capacity FIFO queue backed by a circular array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be greater than zero")

        self._items: list[int] = [0] * capacity
        self._capacity: int = capacity
        self._head: int = 0
        self._tail: int = 0
        self._size: int = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

    def enqueue(self, value: int) -> None:
        """Add a value to the back of the queue."""
        if self.is_full():
            raise QueueFullError("cannot enqueue into a full queue")

        self._items[self._tail] = value
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self) -> int:
        """Remove and return the value at the front of the queue."""
        if self.is_empty():
            raise QueueEmptyError("cannot dequeue from an empty queue")

        value = self._items[self._head]
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value


def run_queue_example() -> None:
    """Demonstrate FIFO ordering and circular reuse."""
    queue = ArrayQueue(capacity=3)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)

    print(queue.dequeue())  # 10
    queue.enqueue(40)

    print(queue.dequeue())  # 20


run_queue_example()

Advantages and Disadvantages

Advantages

  • Constant-time operations: Circular enqueue and dequeue both run in O(1).

  • Predictable memory use: The maximum allocated storage is known in advance.

  • No shifting overhead: Wrapping indices avoids moving elements after removals.

  • Simple implementation: The structure is suitable for embedded systems, buffers, and fixed-size producer-consumer queues.

Disadvantages

  • Fixed capacity: The queue must reject enqueue operations when full unless it is resized or redesigned.

  • Overflow and underflow: Callers must handle full and empty states explicitly.

  • Memory preallocation: All slots are allocated even if the queue never reaches its capacity.

  • More complex than a linear array queue: Correct modulo arithmetic and state management are required.

  • Less convenient than collections.deque: Python’s deque supports O(1) appends and removals from both ends without a fixed-capacity limit.

  • Not automatically thread-safe: For producer-consumer code requiring synchronization, use queue.Queue instead.

Common Pitfalls and Interview Tips

  • Confusing full and empty states can happen if size is omitted. Reserving one slot is another solution, but it reduces usable capacity.

  • Updating head or tail without applying modulo causes incorrect behavior once the queue wraps.

  • Never use list.pop(0) for dequeue; it shifts every remaining element and costs O(n).

  • Keep the queue FIFO: insert at the back and remove from the front.

  • Mention both variants in interviews: a linear array queue may require O(n) shifting, while a circular queue keeps enqueue and dequeue at O(1).

15

How do singly and doubly linked lists differ for queues?

A queue built with a doubly linked list supports constant-time FIFO operations and also allows efficient removal from the rear when a node reference is available. For basic queue behavior, however, a singly linked list is equally efficient if it maintains both head and tail pointers.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

FIFO Behavior and Main Benefit

Both implementations can provide:

  • Enqueue at the rear: O(1) with a tail pointer.

  • Dequeue from the front: O(1) with a head pointer.

  • FIFO ordering: the first inserted element is the first removed.

The doubly linked list adds a backward pointer to each node, enabling:

  • Dequeue from the rear: O(1), unlike O(n) for a singly linked list.

  • Bidirectional traversal: useful for backward iteration or finding a predecessor.

  • Faster node removal: if the node is already known, deleting it can be O(1) after updating its neighbors.

  • Deque-style behavior: supporting operations at both ends.

A singly linked list is not inherently slower for a normal FIFO queue. Its limitation appears when reverse traversal or rear deletion is required.

Operation Complexity

Operation Singly Linked List Doubly Linked List
Enqueue at rear O(1) best, average, worst O(1) best, average, worst
Dequeue from front O(1) best, average, worst O(1) best, average, worst
Dequeue from rear O(n) worst; O(1) for one element O(1) best, average, worst
Find a node’s predecessor O(n) O(1) if the node is known
Reverse traversal O(n) O(n)
Space O(n) O(n), with extra prev pointers

Linked-list pointer updates are O(1) in the best, average, and worst cases. Singly linked rear deletion requires traversing from the head, so it is O(n) for a queue containing more than one element.

The queue requires O(n) total storage. Auxiliary space beyond the stored elements is O(1), and the recursion stack is O(1) because these implementations are iterative. If the input collection is counted, total memory remains O(n).

Practical Trade-offs

  • Singly linked list: less memory per node and sufficient for ordinary FIFO behavior.

  • Doubly linked list: additional pointer and update complexity, but supports reverse operations efficiently.

  • Production code: use collections.deque for an in-memory FIFO because append() and popleft() are O(1).

  • Thread safety: use queue.Queue for producer-consumer systems requiring synchronization.

Common Pitfalls

  • Forgetting to maintain the tail pointer, which can make rear insertion O(n).

  • Failing to update both head and tail when removing the final element.

  • Leaving stale next or prev references on removed nodes.

  • Assuming a singly linked list must make dequeue O(n): storing a tail pointer prevents this.

  • Using a custom linked queue in production when collections.deque already provides the required FIFO behavior.

16

How does a circular queue manage FIFO storage and implementation risks?

A circular queue is a fixed-capacity FIFO queue that reuses array positions by wrapping its indices back to the beginning. It avoids the cost of shifting elements and distinguishes full and empty states by tracking the number of stored items.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Given an array with capacity C, the queue maintains:

  • head: index of the next item to remove.

  • tail: index where the next item will be inserted.

  • size: number of items currently stored.

  • capacity: maximum number of items the queue can hold.

The core operations are:

  1. Enqueue

  2. Reject the operation if the queue is full.

  3. Store the value at tail.

  4. Advance tail using (tail + 1) % capacity.

  5. Increment size.

  6. Dequeue

  7. Reject the operation if the queue is empty.

  8. Retrieve the value at head.

  9. Clear that slot to release object references.

  10. Advance head using (head + 1) % capacity.

  11. Decrement size.

  12. Peek

  13. Return the value at head without removing it.

  14. Raise an error when the queue is empty.

The modulo operation makes the indices wrap around. For example, in a queue of capacity 3, advancing index 2 produces (2 + 1) % 3 == 0.

Variants and Alternatives

Approach Main operation Space When to use
collections.deque append and popleft: O(1) O(n) General-purpose FIFO queues
Fixed circular queue Enqueue/dequeue: O(1) O(capacity) Bounded buffers and embedded systems
heapq priority queue Insert: O(log n) O(n) Processing items by priority
queue.Queue Put/get: O(1) average O(n) Thread-safe producer-consumer systems

A monotonic deque is another deque variant used for sliding-window maximums. Each element is appended once and removed at most once, so the entire traversal takes O(n).

Example Walkthrough

For a circular queue with capacity 3:

Operation Buffer head tail Size
Initially [None, None, None] 0 0 0
Enqueue 10 [10, None, None] 0 1 1
Enqueue 20 [10, 20, None] 0 2 2
Enqueue 30 [10, 20, 30] 0 0 3
Dequeue 10 [None, 20, 30] 1 0 2
Enqueue 40 [40, 20, 30] 1 1 3

Complexity

  • Best, average, and worst-case time: O(1) for enqueue, dequeue, peek, and full/empty checks because each uses direct indexing and constant-time arithmetic.

  • Total space: O©, where C is the fixed capacity, for the stored queue elements.

  • Input accounting: This O© figure covers the queue’s own storage and excludes any separately supplied input collection. Including an input collection of n elements gives O(n + C) total storage, although the queue stores references to those elements rather than copying them.

  • Auxiliary space: O(1) for metadata.

  • Recursion stack: O(1), since the implementation is iterative.

Code Example

class CircularQueue:
    """Fixed-capacity FIFO queue backed by an array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self._buffer: list[int | None] = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, value: int) -> None:
        if self.is_full():
            raise OverflowError("circular queue is full")

        self._buffer[self._tail] = value
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("circular queue is empty")

        value = self._buffer[self._head]
        if value is None:
            raise RuntimeError("invalid internal queue state")

        self._buffer[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("circular queue is empty")

        value = self._buffer[self._head]
        if value is None:
            raise RuntimeError("invalid internal queue state")
        return value

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

    def __len__(self) -> int:
        return self._size


def circular_queue_demo() -> None:
    """Demonstrate FIFO behavior and wrap-around."""
    queue = CircularQueue(3)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)

    print(queue.dequeue())
    queue.enqueue(40)
    print(queue.peek())
    print(len(queue))
    print(queue.is_full())


circular_queue_demo()

# Expected output:
# 10
# 20
# 2
# True

Common Pitfalls

  • Empty versus full ambiguity: Using only head and tail makes those states indistinguishable after a complete cycle. A separate size counter avoids this.

  • Off-by-one errors: Define whether tail points to the next insertion position or the last inserted element, and use that convention consistently.

  • Overflow and underflow: Decide whether full queues reject, overwrite, or block new items. Silent overwriting loses data.

  • Thread safety: This implementation is not thread-safe. Use queue.Queue or queue.SimpleQueue for concurrent producers and consumers.

  • Edge cases: Test an empty queue, one-element queue, full queue, duplicate values, and negative values. A zero or negative capacity should be rejected.

17

How should a full circular queue event be handled?

A full circular queue event occurs when an insertion is attempted while every slot contains an unread item. A circular queue should detect this condition explicitly and either reject the item, apply backpressure, or deliberately overwrite the oldest item according to the application’s requirements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A circular queue stores elements in a fixed-size array and uses modular arithmetic to wrap the indices:

  • head identifies the oldest element.

  • tail identifies the next available position.

  • size records the number of occupied slots.

  • The next insertion position is tail.

  • The next removal position is head.

After each operation, the relevant index wraps with the expression next_position = (current_position + 1) % capacity. Using an explicit size allows all array slots to hold data while still distinguishing between an empty queue and a full queue.

Handling a Full Queue

Policy Behavior Appropriate use
Reject enqueue returns False or raises an exception Data loss must be prevented
Backpressure Producer waits or retries later A bounded producer-consumer system
Overwrite Remove the oldest item and insert the new one Telemetry where newest data matters most
Resize Allocate a larger queue Flexible capacity requirements

A fixed circular queue is not thread-safe. For thread-safe producer-consumer code, use queue.Queue(maxsize=N). Its blocking put method waits when the queue is full, while put_nowait raises queue.Full if no slot is immediately available. queue.Queue provides synchronization but is not a fixed circular array.

Complexity

Operation Best Average Worst Extra space
Enqueue O(1) O(1) O(1) O(1)
Dequeue O(1) O(1) O(1) O(1)
Check full or empty O(1) O(1) O(1) O(1)

The queue uses O(capacity) total space because it allocates one slot per possible element. This includes occupied and empty slots; any separate caller-owned input collection is not counted. No recursion stack is used. These bounds do not differ between cases because index updates and capacity checks take constant time.

Code Example

from typing import Generic, TypeVar, cast

T = TypeVar("T")


class CircularQueue(Generic[T]):
    """A bounded FIFO queue backed by a fixed-size circular array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self._items: list[T | None] = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def __len__(self) -> int:
        return self._size

    def is_full(self) -> bool:
        return self._size == self._capacity

    def is_empty(self) -> bool:
        return self._size == 0

    def enqueue(self, item: T) -> bool:
        """Insert an item, returning False when the queue is full."""
        if self.is_full():
            return False

        self._items[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1
        return True

    def dequeue(self) -> T:
        """Remove and return the oldest item."""
        if self.is_empty():
            raise IndexError("dequeue from an empty circular queue")

        item = cast(T, self._items[self._head])
        self._items[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return item


def main() -> None:
    """Demonstrate rejection and acceptance around a full queue."""
    queue = CircularQueue[str](3)

    print(queue.enqueue("A"))
    print(queue.enqueue("B"))
    print(queue.enqueue("C"))
    print(queue.enqueue("D"))
    print(queue.dequeue())
    print(queue.enqueue("D"))


if __name__ == "__main__":
    main()
    # Expected output:
    # True
    # True
    # True
    # False
    # A
    # True

Example Walkthrough

For a queue with capacity 3:

  1. Enqueue A: size = 1, and tail advances to 1.

  2. Enqueue B: size = 2, and tail advances to 2.

  3. Enqueue C: size = 3, and tail wraps to 0.

  4. Enqueue D: the queue is full, so the event is rejected.

  5. Dequeue A: head advances to 1, and size becomes 2.

  6. Enqueue D: it occupies index 0, and tail advances to 1.

Common Pitfalls

  • Confusing full and empty: (tail + 1) % capacity == head can mean either condition unless one slot is intentionally reserved. An explicit count avoids that ambiguity.

  • Missing modulo arithmetic: Incrementing an index without wrapping eventually causes an out-of-range error.

  • Changing head incorrectly: Removing an element must advance head and decrease size.

  • Overwriting silently: Dropping the oldest event is valid only when that data-loss policy is intentional.

  • Ignoring thread safety: Use queue.Queue rather than this class when multiple threads access the queue.

  • Edge cases: Dequeueing an empty queue raises IndexError; capacity 1 works correctly; duplicate and negative values are stored normally. Already-sorted input, disconnected graphs, and cycles are not applicable to a queue.

18

How do you implement a FIFO queue using two stacks?

A two-stack queue uses one stack for enqueueing and another for dequeuing. Items are transferred to the outgoing stack only when needed, giving amortized O(1) time for each queue operation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The implementation uses two list-backed stacks:

  • Incoming stack: New items are pushed here by enqueue.

  • Outgoing stack: Items are transferred here before dequeue or peek.

  • The top of the outgoing stack is then the oldest queued item, preserving FIFO order.

  • Each item moves from the incoming stack to the outgoing stack at most once, which is why operations are amortized O(1).

The queue does not use recursion, so it has no recursion-stack overhead.

Queue Variants and Use Cases

Variant Typical implementation Main characteristic
Simple FIFO queue collections.deque O(1) append and popleft
Two-stack queue One incoming and one outgoing stack Amortized O(1) FIFO operations
Circular queue Fixed-size array with head and tail indices modulo capacity Bounded capacity and O(1) operations
Double-ended queue collections.deque Insert and remove at either end
Priority queue heapq Min-heap; negate values for a max-heap
Thread-safe queue queue.Queue Supports producer-consumer workloads
Monotonic deque collections.deque Sliding-window maximum in O(n) total time

For a monotonic deque, each element is appended and removed at most once, so its overall time complexity is O(n).

Common queue uses include:

  • BFS: Visiting graph or tree nodes level by level.

  • Task scheduling: Processing queued work in submission order.

  • Rate limiting: Tracking requests within a time window.

  • Buffering: Temporarily storing incoming data.

Typical interview problems include implementing this two-stack FIFO queue, designing a fixed-capacity circular queue, finding a sliding-window maximum with a monotonic deque, and solving the rotting oranges problem with BFS.

Complexity

Operation Best Average Worst
enqueue O(1) O(1) amortized O(n) if the Python list reallocates
dequeue O(1) O(1) amortized O(n) when transferring all items
peek O(1) O(1) amortized O(n) when transferring all items
is_empty O(1) O(1) O(1)
  • Space: O(n) for the stored queue items, excluding any separate input collection supplied by the caller.

  • Transfer cost: Each item crosses from the incoming stack to the outgoing stack once, so a sequence of n successful queue operations costs O(n) overall.

Walkthrough

The end of each stack list represents its top.

Operation Incoming stack Outgoing stack Result
enqueue(10) [10] [] Queue contains 10
enqueue(20) [10, 20] [] Queue contains 10, 20
enqueue(30) [10, 20, 30] [] Queue contains 10, 20, 30
First dequeue() [] [30, 20, 10] Returns 10
Second dequeue() [] [30, 20] Returns 20

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class TwoStackQueue(Generic[T]):
    """Implement a FIFO queue using two list-backed stacks."""

    def __init__(self) -> None:
        self._incoming: list[T] = []
        self._outgoing: list[T] = []
        self._size = 0

    def enqueue(self, value: T) -> None:
        """Add an item to the back of the queue."""
        self._incoming.append(value)
        self._size += 1

    def _prepare_outgoing(self) -> None:
        """Reverse the incoming stack when the outgoing stack is empty."""
        if not self._outgoing:
            while self._incoming:
                self._outgoing.append(self._incoming.pop())

    def dequeue(self) -> T:
        """Remove and return the oldest item."""
        self._prepare_outgoing()

        if not self._outgoing:
            raise IndexError("dequeue from empty queue")

        self._size -= 1
        return self._outgoing.pop()

    def peek(self) -> T:
        """Return the oldest item without removing it."""
        self._prepare_outgoing()

        if not self._outgoing:
            raise IndexError("peek from empty queue")

        return self._outgoing[-1]

    def is_empty(self) -> bool:
        """Return whether the queue contains no items."""
        return self._size == 0

    def __len__(self) -> int:
        return self._size


queue = TwoStackQueue[int]()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())  # 10

Common Pitfalls and Interview Tips

  • Transfer items only when the outgoing stack is empty; transferring earlier can violate FIFO order.

  • Never implement dequeueing with list.pop(0), because removing the first element is O(n).

  • Maintain a separate size counter if an O(1) queue-size operation is required.

  • Empty dequeue and peek calls raise IndexError in this implementation.

  • One-element queues, duplicate values, and negative values behave normally because no comparisons or value assumptions are made.

  • Sorted input, disconnected graphs, and cycles have no special meaning for a FIFO queue.

  • Use queue.Queue instead of this class when multiple threads need blocking producer-consumer synchronization.

  • Common follow-up questions cover queue.Queue, circular queues, priority queues, and why the amortized cost of dequeue is O(1).

19

Implement a FIFO queue using only one stack

A queue follows FIFO ordering: the earliest inserted item is removed first. With a single stack, this requires placing new elements at the bottom of the stack, so enqueue takes O(n), while removing the top element with dequeue takes O(1).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Design and Trade-off

The implementation uses one linked stack whose top represents the queue’s front:

  • enqueue: Traverse to the stack’s bottom and attach the new element there.

  • dequeue: Remove and return the stack’s top.

  • peek: Return the top without removing it.

  • Empty queue: Raise an exception rather than return None.

An ordinary stack exposes only its top. With no second stack or other storage, efficiently accessing the oldest element requires either inserting at the bottom or removing from the bottom, both O(n) operations. The common solution with amortized O(1) enqueue and dequeue uses two stacks, not one.

Complexity

Operation Best Average Worst Reason
enqueue O(1) O(n) O(n) Traverses all existing nodes to reach the bottom
dequeue O(1) O(1) O(1) Removes the node referenced by the top pointer
peek O(1) O(1) O(1) Reads the top node
len O(1) O(1) O(1) Maintains a size counter
  • Total space: O(n), including the O(n) stored elements and nodes.

  • Auxiliary space: O(1), excluding the stored queue elements.

  • Recursion stack: None; all operations are iterative.

Edge Cases

  • Empty queue: dequeue and peek raise QueueEmptyError.

  • One element: dequeue returns it and leaves the queue empty.

  • Duplicates and negative numbers: Stored and returned unchanged.

  • Already sorted values: FIFO preserves their insertion order.

  • Disconnected graphs and cycles: Not applicable; the queue can contain arbitrary values, including graph-related objects.

Walkthrough

Enqueue 10, -5, and 10. The stack is shown from top to bottom:

  1. Enqueue 10: [10]

  2. Enqueue -5: [10, -5]

  3. Enqueue 10: [10, -5, 10]

  4. dequeue removes the top and returns 10: [-5, 10]

The values are therefore returned in FIFO order: 10, -5, 10.

Code Example

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


class QueueEmptyError(IndexError):
    """Raised when an operation requires an item from an empty queue."""


@dataclass(slots=True)
class _StackNode(Generic[T]):
    value: T
    next: _StackNode[T] | None = None


class QueueWithOneStack(Generic[T]):
    """Implement a FIFO queue using one linked stack."""

    def __init__(self) -> None:
        # The top of the stack is also the front of the queue.
        self._top: _StackNode[T] | None = None
        self._size = 0

    def enqueue(self, value: T) -> None:
        """Add a value to the back of the queue."""
        new_node = _StackNode(value=value)

        if self._top is None:
            self._top = new_node
        else:
            bottom = self._top
            while bottom.next is not None:
                bottom = bottom.next
            bottom.next = new_node

        self._size += 1

    def dequeue(self) -> T:
        """Remove and return the value at the front of the queue."""
        if self._top is None:
            raise QueueEmptyError("Cannot dequeue from an empty queue")

        node = self._top
        self._top = node.next
        self._size -= 1
        return node.value

    def peek(self) -> T:
        """Return the front value without removing it."""
        if self._top is None:
            raise QueueEmptyError("Cannot peek into an empty queue")

        return self._top.value

    def __len__(self) -> int:
        return self._size


if __name__ == "__main__":
    queue = QueueWithOneStack[int]()
    queue.enqueue(10)
    queue.enqueue(-5)
    queue.enqueue(10)

    print(queue.dequeue())  # 10

Interview Tips

  • Explain the trade-off explicitly: a strict one-stack queue has an O(n) operation; two stacks provide amortized O(1) enqueue and dequeue.

  • Never use list.pop(0) as an implementation shortcut because it shifts every remaining element and takes O(n).

  • For ordinary application code, prefer collections.deque, whose append and popleft are both O(1).

  • Use queue.Queue when producers and consumers need a thread-safe blocking queue rather than a simple in-process FIFO.

20

Implement a Stack with Two Queues and O(1) Push

A stack can be implemented with two FIFO queues by keeping all elements in a primary queue and using a secondary queue to expose the most recently pushed element for O(1) push and O(n) pop.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Use two queues (here collections.deque restricted to append and popleft):

  • Primary queue (q1): Holds the stack elements in FIFO order (oldest at front).

  • Secondary queue (q2): Acts as a buffer during pop and peek.

Push simply enqueues to q1 – constant time.

Pop works as follows: 1. If q1 is empty, raise an error. 2. While q1 has more than one element, dequeue from q1 and enqueue to q2. 3. The last element remaining in q1 is the top of the stack; dequeue and return it. 4. Swap q1 and q2 so that q1 again holds the remaining elements and q2 is empty.

Peek uses the same transfer logic but re-enqueues the last element to q2 before swapping, so the element stays in the stack.

This design makes push O(1) and pop/peek O(n) in the worst case (when the stack has many elements). There is no amortized O(1) guarantee because an element can be moved between queues many times across a sequence of pops.

Complexity

Operation Best case Average case Worst case Reason
push O(1) O(1) O(1) Single append to q1
pop O(1) O(n) O(n) May move all but one element
peek O(1) O(n) O(n) Same transfer as pop
len O(1) O(1) O(1) Sum of both queue lengths
Space O(n) O(n) O(n) Stores all stack elements

Auxiliary space beyond the stored elements is O(1). No recursion is used.

Code Example

from collections import deque


class StackUsingTwoQueues:
    """Implement a LIFO stack using two FIFO queues with O(1) push."""

    def __init__(self) -> None:
        self._q1: deque[int] = deque()
        self._q2: deque[int] = deque()

    def push(self, value: int) -> None:
        """Add a value to the top of the stack."""
        self._q1.append(value)

    def pop(self) -> int:
        """Remove and return the newest element."""
        if not self._q1:
            raise IndexError("pop from empty stack")

        # Move all but the last element to q2
        while len(self._q1) > 1:
            self._q2.append(self._q1.popleft())

        # The last element in q1 is the stack top
        top = self._q1.popleft()

        # Swap the queues so q1 holds the remaining elements
        self._q1, self._q2 = self._q2, self._q1
        return top

    def peek(self) -> int:
        """Return the newest element without removing it."""
        if not self._q1:
            raise IndexError("peek from empty stack")

        # Move all but the last element to q2
        while len(self._q1) > 1:
            self._q2.append(self._q1.popleft())

        # The last element is the top; keep it by moving to q2 as well
        top = self._q1.popleft()
        self._q2.append(top)

        # Swap queues
        self._q1, self._q2 = self._q2, self._q1
        return top

    def is_empty(self) -> bool:
        """Return whether the stack contains no elements."""
        return not self._q1

    def __len__(self) -> int:
        return len(self._q1)


stack = StackUsingTwoQueues()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack.pop())   # 2
print(stack.pop())   # 1
print(stack.is_empty())  # True

Example Walkthrough

Starting with an empty stack:

Operation q1 (primary) q2 (secondary) Result
push(1) [1] [] —
push(2) [1, 2] [] —
push(3) [1, 2, 3] [] —
pop() [1, 2] → move to q2 → [] [1, 2] → after swap q1=[1,2] Returns 3
pop() [1, 2] → move 1 to q2 → [2] [1] → after swap q1=[1] Returns 2
pop() [1] → no move needed [] Returns 1

Common Pitfalls

  • Using list.pop(0): Removing the first element from a Python list is O(n). Use deque.popleft().

  • Forgetting to swap queues: After moving elements, the roles of q1 and q2 must be exchanged.

  • Empty-stack behavior: pop() and peek() should raise IndexError when no elements exist.

  • Choosing the wrong trade-off: This design prioritizes efficient push. The alternative (transfer on every push) provides efficient pop but makes push O(n).

  • Thread safety: For producer-consumer scenarios, use queue.Queue instead of this implementation.

21

How do you implement and use a Double-Ended Queue in Python?

A double-ended queue (deque) supports efficient insertion and removal from both its front and rear. Python provides the optimized collections.deque, which is preferable to a list for FIFO processing because operations such as popleft() take constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • append(item) adds an element to the rear.

  • appendleft(item) adds an element to the front.

  • popleft() removes the front element.

  • pop() removes the rear element.

  • deque[0] and deque[-1] access the two ends in constant time.

  • deque[i] accesses an arbitrary element in linear time.

A deque can implement several queue-like behaviors:

  • FIFO queue: use append() and popleft().

  • LIFO stack: use append() and pop().

  • Double-ended processing: combine all four operations.

Complexity

Operation Best Average Worst Reason
append() O(1) O(1) O(1) Direct insertion at the rear
appendleft() O(1) O(1) O(1) Direct insertion at the front
popleft() O(1) O(1) O(1) Direct removal from the front
pop() O(1) O(1) O(1) Direct removal from the rear
deque[0] or deque[-1] O(1) O(1) O(1) Direct end access
deque[i] O(n) O(n) O(n) Elements must be traversed
Iteration O(n) O(n) O(n) Every element is visited

The deque requires O(n) space for its stored elements. A single end operation uses O(1) auxiliary space excluding the input and retained queue. No recursion stack is involved.

Queue Variants

Variant Core implementation Time Space
FIFO queue collections.deque O(1) per enqueue/dequeue O(n)
Circular queue Fixed array with modulo indices O(1) per operation O(capacity)
Priority queue heapq min-heap O(log n) per push/pop; O(1) to peek O(n)
Monotonic deque collections.deque O(n) total O(k), where k is retained elements

A circular queue tracks head and tail using (index + 1) % capacity, avoiding costly array shifts. For priority queues, heapq is a min-heap; negate numeric values when a max-heap is required. In a sliding-window algorithm, a monotonic deque pushes and pops each element at most once, giving O(n) total time.

Use queue.Queue instead when multiple threads require a thread-safe producer-consumer queue.

Code Example

from collections import deque


class CircularQueue:
    """Fixed-capacity FIFO queue implemented with modular indices."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self._capacity = capacity
        self._items: list[str | None] = [None] * capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item: str) -> None:
        if self._size == self._capacity:
            raise OverflowError("circular queue is full")

        self._items[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self) -> str:
        if self._size == 0:
            raise IndexError("circular queue is empty")

        item = self._items[self._head]
        if item is None:
            raise RuntimeError("circular queue state is inconsistent")

        self._items[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return item


def demonstrate_queues() -> tuple[list[int], list[str]]:
    """Demonstrate collections.deque and a circular FIFO queue."""
    values: deque[int] = deque([20])
    values.append(30)
    values.appendleft(10)

    first_removed = values.popleft()
    last_removed = values.pop()

    circular = CircularQueue(3)
    for item in ("first", "second", "third"):
        circular.enqueue(item)

    circular_result = [
        circular.dequeue(),
        circular.dequeue(),
        circular.dequeue(),
    ]

    return list(values), circular_result


print(demonstrate_queues())
# ([20], ['first', 'second', 'third'])

The deque changes from [20] to [20, 30], then [10, 20, 30]. Removing 10 from the front and 30 from the rear leaves [20].

Common Pitfalls

  • Using list.pop(0): This shifts every remaining element and costs O(n). Use deque.popleft() for O(1) removal.

  • Random access: deque[i] is O(n); use a list when indexed access dominates the workload.

  • Empty queues: popleft() and pop() raise IndexError, so check the deque or catch the exception.

  • Mutation during iteration: A deque permits mutation during iteration, but it does not provide a stable snapshot. Use deque.copy() or list(d) when a stable copy is required.

  • Incorrect assumptions: Duplicates and negative values are valid elements. A deque preserves insertion order but does not provide priority ordering.

  • Thread safety: collections.deque is not a replacement for a thread-safe queue.Queue in concurrent producer-consumer systems.

22

How do you implement a Blocking Queue in Python 3.12?

A blocking queue is a thread-safe FIFO queue whose put operation waits when it is full and whose get operation waits when it is empty. In Python 3.12, queue.Queue provides this behavior with optional timeouts, task tracking, and bounded capacity.

Read full answer

Applies toPython 3.12

How It Works

queue.Queue(maxsize) exposes the required producer-consumer operations:

  • put(item): Adds an item to the rear. If a bounded queue is full, the calling thread blocks until space becomes available.

  • get(): Removes and returns the oldest item. If the queue is empty, the calling thread blocks until an item arrives.

  • put_nowait(item): Raises queue.Full instead of blocking.

  • get_nowait(): Raises queue.Empty instead of blocking.

  • Timeout support: put(item, timeout=seconds) raises queue.Full after the timeout; get(timeout=seconds) raises queue.Empty.

  • Completion tracking: task_done() marks one item as processed, while join() waits until all queued tasks have been marked complete.

The queue preserves FIFO ordering for successfully completed operations. With multiple producers, the global insertion order can depend on thread scheduling.

Implementation Details

Internally, queue.Queue stores items in a collections.deque, protected by a mutex (threading.Lock) and condition variables (threading.Condition): not_full for producers waiting for space and not_empty for consumers waiting for items (plus all_tasks_done for join()). put appends to the deque and get calls popleft(), both O(1). A custom implementation follows the same pattern: acquire the lock, wait with wait_for until the condition (not full / not empty) holds, perform the deque operation, and notify the other side.

Code Example

The following bounded queue demonstrates producer-consumer processing and backpressure:

from queue import Queue
from threading import Thread


def process_jobs() -> int:
    """Process five integer jobs using a bounded producer-consumer queue."""
    work_queue: Queue[int] = Queue(maxsize=2)

    def produce_jobs() -> None:
        for job_id in range(1, 6):
            # Blocks here when the bounded queue contains two jobs.
            work_queue.put(job_id)

    producer = Thread(target=produce_jobs)
    producer.start()

    total = 0
    for _ in range(5):
        # Blocks until the producer makes a job available.
        total += work_queue.get()

    producer.join()
    return total


print(process_jobs())  # Expected output: 15

Complexity

  • queue.Queue.put: O(1) best, average, and worst case (deque.append), excluding time spent waiting.

  • queue.Queue.get: O(1) best, average, and worst case (deque.popleft), excluding time spent waiting.

  • Blocking latency: The total completion time also includes time spent waiting for another thread, so it can be unbounded. It cannot be represented by a finite O(1) wall-clock guarantee.

  • Space: A bounded queue uses O© storage for capacity C. An unbounded queue uses O(n) storage for n queued items. The input is not counted separately, and the recursion-stack usage is O(1) because no recursion is involved.

Producer-Consumer Use Case

A bounded blocking queue is useful when one or more threads produce work and one or more threads consume it:

  1. The producer places jobs into the queue.

  2. The queue reaches its capacity of two.

  3. Further put calls block, preventing excessive memory growth.

  4. The consumer removes and processes jobs.

  5. Removing an item frees capacity and unblocks the producer.

This provides thread-safe communication, flow control, and backpressure. Examples include worker pools, image-processing pipelines, log-processing systems, and request-handling pipelines.

Common Pitfalls

  • Deadlock: If consumers stop before draining the queue, producers can remain blocked in put.

  • Unbounded queues: Queue() or Queue(maxsize=0) can grow indefinitely and may exhaust memory.

  • Missing task_done(): If using join(), every processed item must have a matching task_done() call.

  • Waiting forever: Prefer a timeout when the application should fail rather than block indefinitely.

  • Shutdown coordination: Python 3.12 has no built-in queue shutdown sentinel. Use a separate stop event or a documented sentinel value, and ensure consumers distinguish it from valid data.

  • Building on a list: A hand-written blocking queue that removes items with list.pop(0) makes get O(n); use collections.deque as queue.Queue does.

23

How do I implement an automatically resizing FIFO queue?

A resizable FIFO queue can be implemented with collections.deque, which grows its internal storage as new elements are enqueued. append adds elements at the rear in amortized O(1) time, while popleft removes them from the front in O(1) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

collections.deque stores elements in contiguous internal blocks and links those blocks together. When more space is needed, it allocates additional storage automatically.

  • Enqueue: Use queue.append(element) to add an element to the rear.

  • Dequeue: Use queue.popleft() to remove the oldest element.

  • Peek: Use queue[0] to inspect the front without removing it.

  • Empty queue: Check if not queue before calling popleft().

  • Thread safety: collections.deque is not thread-safe. Use queue.Queue instead when multiple threads or processes access the queue.

Unlike a circular queue backed by a fixed array, a deque has no configured capacity limit. Its effective limit is available memory.

Queue Variants

Variant Typical implementation Enqueue Dequeue Resizing
Simple FIFO queue collections.deque O(1) amortized O(1) Automatic
Circular queue Fixed array with head/tail indices O(1) O(1) Fixed capacity
Double-ended queue collections.deque O(1) O(1) from either end Automatic
Priority queue heapq O(log n) O(log n) Automatic

A priority queue does not preserve FIFO order; it removes the element with the highest priority. heapq is a min-heap, so values are negated when implementing a max-heap.

Complexity

  • Enqueue

  • Best, average, and worst case: O(1). collections.deque.append adds a new block when needed and never copies existing elements, so each operation is constant time.

  • Amortized cost: O(1) (trivially, since every operation is O(1)).

  • Dequeue

  • Best, average and worst case: O(1), because removing the front does not shift the remaining elements.

  • Peek and emptiness check: O(1).

  • Space: O(n) for the elements stored in the queue. This excludes the caller’s original input, which is not copied into an additional collection.

Edge Cases and Example Trace

Operation Queue state from front to rear
Enqueue 10 [10]
Enqueue 20 [10, 20]
Enqueue 30 [10, 20, 30]
Dequeue Returns 10; state becomes [20, 30]
Dequeue all elements Returns 20, then 30, then raises IndexError if attempted again

Duplicates and negative values are ordinary elements and require no special handling. A one-element queue behaves like any other queue. Empty queues should be checked before dequeuing.

Code Example

from collections import deque
from typing import Generic, TypeVar

T = TypeVar("T")


class ResizableQueue(Generic[T]):
    """A FIFO queue that grows automatically as elements are enqueued."""

    def __init__(self) -> None:
        self._items: deque[T] = deque()

    def enqueue(self, element: T) -> None:
        """Add an element to the rear of the queue."""
        self._items.append(element)

    def dequeue(self) -> T:
        """Remove and return the oldest element."""
        if not self._items:
            raise IndexError("dequeue from an empty queue")
        return self._items.popleft()

    def peek(self) -> T:
        """Return the oldest element without removing it."""
        if not self._items:
            raise IndexError("peek at an empty queue")
        return self._items[0]

    def is_empty(self) -> bool:
        """Return whether the queue contains no elements."""
        return not self._items

    def __len__(self) -> int:
        """Return the number of queued elements."""
        return len(self._items)


def run_queue_demo() -> None:
    """Demonstrate automatic growth and FIFO removal order."""
    queue = ResizableQueue[int]()

    for element in (10, 20, 30, 40):
        queue.enqueue(element)

    print(queue.dequeue(), queue.dequeue(), queue.dequeue(), queue.dequeue())


if __name__ == "__main__":
    run_queue_demo()
    # Expected output: 10 20 30 40

Common Pitfalls

  • Avoid list.pop(0) and list.insert(0, element): both shift the remaining elements and cost O(n) per operation.

  • Do not treat a priority queue as FIFO; it orders elements by priority rather than arrival time.

  • Check for emptiness before popleft() or indexing to avoid IndexError.

  • Remember that an automatically growing queue can eventually exhaust memory; use a bounded circular queue or queue.Queue(maxsize=...) when backpressure is required.

  • In languages with fixed-width integers, ensure indices and capacity calculations cannot overflow.

  • Interviewers commonly follow up about FIFO ordering, thread safety, queue capacity, and why deque avoids the shifting cost of a list-based implementation.

24

How do you implement a queue with O(1) enqueue, dequeue, and max?

A monotonic deque provides efficient FIFO queue operations while maintaining the maximum at its front. Enqueue and dequeue take amortized or worst-case constant time as appropriate, and finding the maximum is constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain two collections.deque instances:

  • _items stores every queued value together with a unique insertion index.

  • _candidates stores only values that could still become the maximum.

The candidate values are kept in decreasing order from front to back.

For enqueue(value):

  1. Append (value, index) to _items.

  2. Remove candidates from the back whose values are less than or equal to value.

  3. Append the new value and index to _candidates.

For dequeue():

  1. Remove the oldest item from _items.

  2. If that item is still the front candidate, remove it from _candidates.

The front of _candidates is always the current maximum.

Complexity

Operation Best Average or Sequence Cost Worst Case Reason
enqueue O(1) O(1) amortized O(n) One insertion can remove many dominated candidates, but each candidate is removed at most once.
dequeue O(1) O(1) O(1) Removes one queue item and at most one candidate.
maximum O(1) O(1) O(1) Reads the front of _candidates.

Space usage is O(n), including the queued items and the candidate deque. The recursion stack is O(1) because the implementation is iterative.

The standard monotonic-deque implementation gives amortized constant-time updates rather than strict worst-case O(1) for every individual enqueue. For example, enqueuing a very large value can remove many smaller candidates at once.

Queue Variants

  • Simple FIFO queue: Use deque.append() and deque.popleft(); never use list.pop(0) because it is O(n).

  • Circular queue: Use a fixed-size array with head and tail indices modulo capacity.

  • Double-ended queue: Use deque.append(), appendleft(), popleft(), and popleft().

  • Priority queue: Use heapq for a min-heap; negate values to simulate a max-heap. This is not FIFO.

  • Thread-safe producer/consumer queue: Use queue.Queue, which provides locking and blocking operations.

Common queue use cases include BFS, buffering, task scheduling, and rate limiting.

Code Example

from collections import deque


class MaxQueue:
    """FIFO queue with amortized O(1) updates and O(1) maximum lookup."""

    def __init__(self) -> None:
        self._items: deque[tuple[int, int]] = deque()
        self._candidates: deque[tuple[int, int]] = deque()
        self._next_index = 0

    def enqueue(self, value: int) -> None:
        """Add a value to the back of the queue."""
        index = self._next_index
        self._next_index += 1

        self._items.append((value, index))

        # Dominated values can never become the maximum while value exists.
        while self._candidates and self._candidates[-1][0] <= value:
            self._candidates.pop()

        self._candidates.append((value, index))

    def dequeue(self) -> int:
        """Remove and return the oldest value."""
        if not self._items:
            raise IndexError("dequeue from an empty queue")

        value, index = self._items.popleft()

        # Remove the candidate only if this exact item is still a candidate.
        if self._candidates and self._candidates[0][1] == index:
            self._candidates.popleft()

        return value

    def maximum(self) -> int:
        """Return the current maximum without removing it."""
        if not self._candidates:
            raise IndexError("maximum from an empty queue")

        return self._candidates[0][0]

    def __len__(self) -> int:
        return len(self._items)


example = MaxQueue()
example.enqueue(5)
example.enqueue(3)
example.enqueue(7)

print(example.maximum())  # Expected output: 7

For the example:

Operation Queue values Candidate values Maximum
Initial [] [] Error
Enqueue 5 [5] [5] 5
Enqueue 3 [5, 3] [5, 3] 5
Enqueue 7 [5, 3, 7] [7] 7

Common Pitfalls

  • Empty queue: dequeue() and maximum() should raise a clear IndexError.

  • Duplicates: Store insertion indices with values; removing candidates by value alone can remove the wrong occurrence.

  • Negative numbers: The comparison logic works unchanged.

  • Single element: Maximum lookup and dequeue behave correctly.

  • Already sorted input: No special handling is required; the queue does not assume input ordering.

  • Arbitrary deletion: This API supports FIFO deletion only. Removing an item and its candidate can preserve the monotonic ordering, but locating that candidate by index in _candidates takes O(n); a different design is needed for O(1) arbitrary deletion.

  • Disconnected graphs and cycles: These are not queue inputs, but when a queue is used for BFS, maintain a separate visited set to avoid revisiting nodes.

  • Complexity wording: Say “O(1) amortized” for updates rather than claiming strict O(1) worst-case behavior for every enqueue.

25

How do linear and circular queues differ?

A linear queue stores elements in a straight FIFO sequence, while a circular queue connects the end of its storage back to the beginning so vacated positions can be reused. Circular queues are especially useful when memory is fixed and operations must consistently take constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Linear queue: Elements are enqueued at the rear and dequeued from the front.

  • In a fixed-array implementation, the front and rear indices move forward until the rear reaches the array’s end. Earlier slots may then be empty but cannot be reused without shifting elements or creating a new queue.

  • A linked-list implementation or collections.deque can reclaim space from the front, but it is still logically a non-wrapping FIFO queue.

  • Circular queue: The buffer is treated as a ring. When an index reaches the end, modulo arithmetic wraps it to zero:

  • next_index = (current_index + 1) % capacity

  • This allows the queue to continue using positions released by earlier dequeues.

  • A circular queue does not have unlimited capacity; it becomes full when the number of stored elements equals its fixed capacity.

Comparison

Aspect Linear Queue Circular Queue
Storage layout Straight sequence Ring buffer
Reuses front positions Not inherently in a fixed array Yes
Requires shifting Sometimes, to reuse array slots No
Fixed capacity Possible Natural fit
FIFO ordering Front to rear Front to rear, wrapping at the boundary
Typical use General FIFO buffering Embedded systems, audio buffers, BFS with fixed storage
Common Python equivalent collections.deque Usually implemented with an array and indices

For a capacity-three circular queue, the internal progression is:

Operation Head Next Insertion Size Buffer
Initial 0 0 0 [_, _, _]
Enqueue A 0 1 1 [A, _, _]
Enqueue B 0 2 2 [A, B, _]
Enqueue C 0 0 3 [A, B, C]
Dequeue A 1 0 2 [_ , B, C]
Enqueue D 1 1 3 [D, B, C]

Complexity

For index-based fixed-array implementations:

Operation Best Average Worst Reason
Linear queue enqueue/dequeue/peek O(1) O(1) O(1) Front and rear indices are updated directly
Circular queue enqueue/dequeue/peek O(1) O(1) O(1) Index updates and modulo wrapping take constant time
  • Linear queue space: O(capacity) for a fixed array, or O(m) for a linked-list/deque implementation storing m elements.

  • Circular queue space: O(capacity) because the entire fixed buffer is allocated.

  • The input itself is not counted in these space complexities.

  • An implementation that uses list.pop(0) or list.insert(0, value) has O(n) time because all existing elements must be shifted. Use collections.deque for a dynamic Python FIFO queue.

Common Pitfalls

  • Confusing full and empty states: An index-based ring may need a separate size counter, as above, to distinguish those conditions.

  • Forgetting modulo wrapping: Without % capacity, the queue stops when the rear reaches the final array position.

  • Using list.pop(0): This is O(n) and defeats the benefit of an efficient queue.

  • Assuming circular means infinite: Capacity remains fixed; enqueueing into a full queue must fail or trigger a separate overflow policy.

  • Ignoring thread safety: Use queue.Queue or queue.SimpleQueue for thread-safe producer-consumer code; collections.deque is appropriate for general in-process FIFO usage.

  • Edge cases: Empty dequeue and peek must fail cleanly, capacity one must work, and duplicate or negative-valued items require no special handling. Sorting and graph connectivity are not applicable to queues.

26

How do you implement a monotonic queue for sliding-window problems?

A monotonic queue is a deque that maintains elements in sorted order, usually decreasing from front to back. It removes elements that can no longer be useful, allowing algorithms such as sliding-window maximum to run in linear time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A typical monotonic queue stores indices rather than values. This makes it possible to identify and remove elements that fall outside the current window.

For a sliding-window maximum, maintain a deque of indices whose corresponding values are strictly decreasing:

  1. Remove indices from the front when they leave the current window.

  2. Remove indices from the back while their values are less than or equal to the new value.

  3. Append the new index.

  4. The front contains the index of the current window’s maximum.

A newer element with an equal or larger value makes older, smaller elements unnecessary. This is why the queue remains small and each index is inserted and removed at most once.

Code Example

from collections import deque


def sliding_window_max(values: list[int], window_size: int) -> list[int]:
    """Return the maximum of every contiguous window of the given size."""
    if window_size <= 0:
        raise ValueError("window_size must be greater than zero")

    candidates: deque[int] = deque()
    results: list[int] = []

    for index, value in enumerate(values):
        # Remove indices that are outside the current window.
        while candidates and candidates[0] <= index - window_size:
            candidates.popleft()

        # Remove values dominated by the current value.
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()

        candidates.append(index)

        # Emit a result once a complete window has been processed.
        if index >= window_size - 1:
            results.append(values[candidates[0]])

    return results


print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Example Walkthrough

For values = [1, 3, -1, -3, 5, 3, 6, 7] and window_size = 3:

Window Maximum Queue indices after processing
[1, 3, -1] 3 [1, 2]
[3, -1, -3] 3 [1, 2, 3]
[-1, -3, 5] 5 [4]
[-3, 5, 3] 5 [4, 5]
[5, 3, 6] 6 [6]
[3, 6, 7] 7 [7]

Complexity

Let n be the number of elements and k the window size.

  • Best case: O(n) time. Every index is still inspected, even when the queue remains small.

  • Average case: O(n) time. Each index is appended once and removed at most once.

  • Worst case: O(n) time. Repeated removals do not make the total quadratic because there are at most n removals.

  • Auxiliary space: O(k) for the deque, excluding the input and returned results. Including the output, total extra space is O(n).

  • There is no recursion stack, and the input itself is not modified.

collections.deque.append() and popleft() are O(1), unlike list.pop(0), which is O(n).

Related Queue Variants

Variant Ordering Typical use
FIFO queue First in, first out Task processing and buffering
Circular queue Fixed-capacity FIFO using modulo indices Embedded buffers and ring buffers
Double-ended queue Insert and remove at both ends Sliding windows and backtracking
Priority queue Highest-priority item first Scheduling and Dijkstra’s algorithm
Monotonic queue Sorted while preserving useful candidates Sliding-window maximum and minimum

Common Pitfalls

  • Using list.pop(0): It shifts all remaining elements and takes O(n) time. Use collections.deque.

  • Confusing values with indices: Store indices so expired elements can be removed efficiently.

  • Removing only strictly smaller values: Using <= safely discards older duplicates because the newer equal value remains in the window longer.

  • Ignoring invalid windows: The implementation handles an empty input by returning [], rejects window_size <= 0, supports one-element inputs, and correctly processes negative values.

  • Mutating the input: The function leaves the original list unchanged.

  • Using a recursive traversal: This solution is iterative and avoids Python’s recursion-depth limit.

Interviewers commonly follow up by asking why each element is pushed and popped only once, how to adapt the algorithm to find sliding-window minimums, and how the monotonic property would change for a different ordering rule.

27

What is a bounded queue and how do you implement one?

A bounded queue is a FIFO data structure with a fixed maximum capacity. It prevents unlimited growth by applying backpressure or rejecting new elements when the capacity is reached. A circular queue is a common implementation because it reuses empty array slots efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Behaviors

  • Enqueue: Add an item to the rear of the queue.

  • Dequeue: Remove and return the item at the front.

  • Peek: Inspect the front item without removing it.

  • Capacity: The queue can contain at most capacity items.

  • Empty queue: Dequeueing or peeking raises an error.

  • Full queue: The chosen overflow policy determines what happens during enqueue.

Common overflow policies include:

Policy Behavior
Reject Raise an exception such as queue.Full
Block Wait until another consumer frees space
Drop newest Discard the incoming item
Drop oldest Remove the front item and enqueue the new one
Caller-defined Apply a custom policy, often using a callback

Rejecting or blocking is usually preferable when data loss is unacceptable.

Why Use a Circular Queue?

A normal Python list is inefficient for FIFO operations because pop(0) shifts all remaining elements and costs O(n). A circular queue stores elements in a fixed-size array and uses modulo arithmetic to wrap the indices:

  • head: index of the next item to remove

  • tail: index where the next item will be inserted

  • size: current number of elements

The queue is empty when size == 0 and full when size == capacity. Tracking size avoids the common ambiguity where head == tail could mean either empty or full.

Complexity

  • Enqueue: O(1) best, average, and worst case; it performs a constant number of index and assignment operations.

  • Dequeue: O(1) best, average, and worst case; removing an array slot does not require shifting other elements.

  • Peek: O(1) in all cases.

  • Space: O© for c preallocated slots. The queue’s storage is counted, while the caller’s input container or reference is not separately counted; there is no recursion stack.

Related Queue Variants

  • Simple FIFO: Use collections.deque, whose append and popleft operations are O(1).

  • Double-ended queue: Use deque when elements must be added or removed from both ends; those operations are O(1).

  • Priority queue: Use heapq; insertion and removal are O(log n). A bounded version needs an explicit capacity and eviction policy.

  • Monotonic deque: Used in algorithms such as sliding-window maximum. Each element is inserted and removed at most once, giving O(n) total time.

  • Thread-safe queue: Use queue.Queue(maxsize=...) for producer-consumer systems requiring blocking and synchronization.

Code Example

from queue import Empty, Full
from typing import Generic, TypeVar, cast

T = TypeVar("T")


class BoundedQueue(Generic[T]):
    """A fixed-capacity FIFO queue implemented with circular indexing."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be greater than zero")

        self.capacity = capacity
        self._items: list[T | None] = [None] * capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item: T) -> None:
        if self._size == self.capacity:
            raise Full("bounded queue is full")

        self._items[self._tail] = item
        self._tail = (self._tail + 1) % self.capacity
        self._size += 1

    def dequeue(self) -> T:
        if self._size == 0:
            raise Empty("bounded queue is empty")

        index = self._head
        item = cast(T, self._items[index])
        self._items[index] = None
        self._head = (self._head + 1) % self.capacity
        self._size -= 1
        return item

    def peek(self) -> T:
        if self._size == 0:
            raise Empty("bounded queue is empty")

        return cast(T, self._items[self._head])

    def __len__(self) -> int:
        return self._size


# Example usage
queue = BoundedQueue[str](3)
queue.enqueue("A")
queue.enqueue("B")
queue.enqueue("C")
# queue is now full (size == 3)

try:
    queue.enqueue("D")  # raises Full
except Full:
    print("queue is full")  # queue is full

print(queue.dequeue())  # A
queue.enqueue("D")      # succeeds (size becomes 3 again)
print(queue.dequeue())  # B
print(queue.dequeue())  # C
print(queue.dequeue())  # D

Walkthrough for capacity 3:

Operation Stored values head tail size
Initial [None, None, None] 0 0 0
Enqueue A ["A", None, None] 0 1 1
Enqueue B ["A", "B", None] 0 2 2
Enqueue C ["A", "B", "C"] 0 0 3
Dequeue A [None, "B", "C"] 1 0 2
Enqueue D ["D", "B", "C"] 1 1 3

The tail index wraps from 2 to 0 after the array becomes full.

Common Pitfalls

  • Do not use list.pop(0) or list.insert(0, value) in a loop; both can cause O(n) work.

  • Decide whether “full” means rejection, blocking, or data loss.

  • Handle empty and full states independently rather than relying only on head == tail.

  • In concurrent code, protect the queue’s state with appropriate locking or use queue.Queue.

  • Consider fairness, cancellation, shutdown behavior, and how producers learn that the system is overloaded.

  • Interviewers commonly ask about capacity handling, thread safety, and why a circular array is preferable to a list for FIFO operations.

28

How do single-ended and double-ended queues differ?

A single-ended queue allows insertion and removal at specific ends, while a double-ended queue (deque) allows insertion and removal at both ends. A single-ended queue normally follows FIFO ordering; a deque supports both FIFO and LIFO-style access patterns.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Single-ended queue: Elements enter at one end and leave at the other.

  • Common convention: insertion at the rear and removal from the front.

  • Preserves first-in, first-out ordering.

  • Python implementation: collections.deque using append() and popleft().

  • Double-ended queue: Elements can be inserted or removed at either the front or the rear.

  • Common operations: append(), appendleft(), popleft(), and pop().

  • Can behave as a FIFO queue, LIFO stack, or a combination of both.

  • Python implementation: collections.deque.

For example, using collections.deque:

  1. append(10) → deque becomes [10]

  2. append(20) → deque becomes [10, 20]

  3. popleft() → returns 10, leaving [20]

  4. appendleft(5) → deque becomes [5, 20]

  5. pop() → returns 20, leaving [5]

The first queue follows FIFO order, whereas the deque can be used from either end.

Operation Comparison

Operation Single-Ended Queue Double-Ended Queue
Insert at rear Supported Supported
Insert at front Usually unsupported Supported
Remove from front Supported Supported
Remove from rear Usually unsupported Supported
FIFO ordering Natural Optional, depending on which ends are used
LIFO ordering Not natural Possible using the same end for insertion and removal

Complexity

Using Python’s collections.deque:

Operation Best Average Worst Reason
Insert at either end O(1) O(1) O(1) Deques maintain efficient links to both ends.
Remove from either end O(1) O(1) O(1) Endpoints can be accessed and updated without shifting elements.
Access first or last element O(1) O(1) O(1) Both endpoints are directly accessible.
Access an arbitrary element O(n) O(n) O(n) The deque may need to traverse internal blocks.
  • Space complexity: O(n) for a queue containing n elements.

  • If the input is supplied as an existing collection, the additional queue storage can still be O(n) when elements are copied; sharing or referencing them can reduce that overhead.

  • A fixed-capacity circular array also provides O(1) end operations, but it requires a maximum capacity and must define behavior when full.

Typical Uses

  • Single-ended queue:

  • Breadth-first search

  • Task scheduling

  • Print jobs and buffering

  • Producer-consumer workflows

  • Double-ended queue:

  • Breadth-first search

  • Sliding-window algorithms

  • Work-stealing schedulers

  • Undo histories

  • LIFO stack behavior through one end

  • FIFO queue behavior through opposite ends

For thread-safe producer-consumer code in Python, use queue.Queue; it is not just an alias for collections.deque.

Common Pitfalls

  • A deque does not automatically guarantee FIFO behavior; that depends on the operations chosen.

  • Do not use list.pop(0) or list.insert(0, value) to implement a queue because each operation can shift O(n) elements.

  • Removing from an empty deque raises IndexError; production code should check if queue first.

  • Middle-element access on a deque is O(n), so it should not replace a random-access list when frequent indexed access is required.

  • Interviewers may follow up by asking for a queue implementation using two stacks, a fixed-size circular queue, or a monotonic deque for the sliding-window maximum problem.

29

How can you sort integers using a FIFO queue?

Queue-based merge sort sorts a list by splitting its elements into two FIFO queues, recursively sorting each queue, and merging the sorted queues by repeatedly dequeuing the smaller front element. It uses collections.deque, whose append and popleft operations are O(1).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Queue-Based Merge Sort

The algorithm uses queues in three stages:

  1. Split: Move elements from the input queue into two smaller queues.

  2. Sort: Recursively apply the same process until each queue has zero or one element.

  3. Merge: Compare the front elements of the two sorted queues and append the smaller one to the result queue.

A single-element or empty queue is already sorted. Using <= when merging ensures that duplicate values are preserved.

Walkthrough

For the input [5, -1, 3, 3, 0]:

Stage Queue or result
Initial [5, -1, 3, 3, 0]
Split Left: [5, -1], Right: [3, 3, 0]
Sorted left [-1, 5]
Sorted right [0, 3, 3]
Merge [-1, 0, 3, 3, 5]

Code Example

from collections import deque


def _merge_queues(
    left: deque[int],
    right: deque[int],
) -> deque[int]:
    """Merge two sorted FIFO queues into one sorted queue."""
    merged: deque[int] = deque()

    while left and right:
        if left[0] <= right[0]:
            merged.append(left.popleft())
        else:
            merged.append(right.popleft())

    # Only one queue can still contain elements.
    while left:
        merged.append(left.popleft())

    while right:
        merged.append(right.popleft())

    return merged


def sort_with_queue(values: list[int]) -> list[int]:
    """Sort integers using a FIFO queue-based merge sort."""
    def sort_queue(queue: deque[int]) -> deque[int]:
        if len(queue) <= 1:
            return queue

        midpoint = len(queue) // 2
        left: deque[int] = deque()
        right: deque[int] = deque()

        for _ in range(midpoint):
            left.append(queue.popleft())

        while queue:
            right.append(queue.popleft())

        sorted_left = sort_queue(left)
        sorted_right = sort_queue(right)

        return _merge_queues(sorted_left, sorted_right)

    return list(sort_queue(deque(values)))


print(sort_with_queue([5, -1, 3, 3, 0]))  # [-1, 0, 3, 3, 5]

Queue Variants

Variant Typical operations Relevance
Simple FIFO queue append, popleft Used by this algorithm
Circular queue Fixed array with head and tail indices modulo capacity Useful when memory must be bounded
Double-ended queue Add or remove from either end deque supports this, although the sort only needs FIFO behavior
Priority queue Remove the smallest or largest element first heapq implements a min-heap; useful when repeated minimum extraction is required

queue.Queue is not needed here. It is intended for thread-safe producer-consumer communication.

Complexity

  • Time: O(n log n) best, average, and worst case. Each recursion level processes all n elements, and there are O(log n) levels.

  • Auxiliary space: O(n) for the queues and merged results.

  • Recursion stack: O(log n), which is included in the total O(n) auxiliary space.

  • Input storage: The original list is not counted in auxiliary space; it is not modified by the implementation.

  • Queue operations: append and popleft are O(1), so dequeuing does not shift the remaining elements.

Common Pitfalls

  • Do not use list.pop(0) or list.insert(0, value) for queue operations; both can require O(n) shifting.

  • The merge must preserve duplicates and correctly handle negative values.

  • Empty and one-element lists are valid base cases.

  • The implementation returns a new list and leaves the caller’s input unchanged.

  • In other languages, check integer bounds when selecting the smallest value.

  • Interviewers may ask why the algorithm is O(n log n), how FIFO queues differ from priority queues, or how to implement the same merge using two stacks.

30

How do you reverse the first k elements of a queue?

To reverse the first k elements of a queue, dequeue the first k elements onto a stack, pop them back into the queue (reversing their order), then move the remaining n‑k elements from the front to the back so the reversed prefix stays at the front.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A FIFO queue supports efficient removal from the front and insertion at the back. The algorithm uses those operations as follows:

  1. Validate that k is between 0 and the queue length.

  2. Dequeue the first k elements and push them onto a temporary stack.

  3. Pop each element from the stack and enqueue it. The reversed prefix is now at the back of the queue, followed by the unchanged suffix.

  4. Move the suffix (the original remaining n‑k elements) from the front to the back by dequeuing and enqueuing them n‑k times. The queue now has the reversed prefix followed by the original suffix.

For example, reversing the first three elements of [1, 2, 3, 4]:

Step Queue Temporary stack
Initial [1, 2, 3, 4] []
Dequeue three items [4] [1, 2, 3]
Enqueue 3 [4, 3] [1, 2]
Enqueue 2 [4, 3, 2] [1]
Enqueue 1 [4, 3, 2, 1] []
Move suffix (1 item) [3, 2, 1, 4] []

Approach Comparison

Approach Time Auxiliary space When to use
Brute-force full rebuild O(n) O(n) When simplicity matters more than space
Stack + rotation (optimal) O(n) O(k) Preferred; only O(k) extra space

Code Example

from collections import deque


def reverse_first_k[T](queue: deque[T], k: int) -> None:
    """Reverse the first k elements of a queue in place."""
    n = len(queue)
    if not 0 <= k <= n:
        raise ValueError("k must be between 0 and the queue length")

    stack: list[T] = []

    # Remove the prefix while preserving its original order in the stack.
    for _ in range(k):
        stack.append(queue.popleft())

    # Re-enqueue the prefix in reverse order (now at the back).
    while stack:
        queue.append(stack.pop())

    # Move the original suffix (n - k elements) from front to back.
    for _ in range(n - k):
        queue.append(queue.popleft())


queue = deque([1, 2, 3, 4])
reverse_first_k(queue, 3)
print(list(queue))  # [3, 2, 1, 4]

Complexity

  • Best case: O(n). Even k = 0 rotates all n elements, and k = n pushes and pops all n through the stack.

  • Average case: O(n), because all n elements are dequeued and enqueued once.

  • Worst case: O(n), same fixed number of queue and stack operations.

  • Auxiliary space: O(k) for the temporary stack, excluding the input queue.

  • Total space including the input: O(n + k), where n is the original queue length.

  • Recursion stack: None; the implementation is fully iterative.

Each deque.popleft() and deque.append() is O(1). List-backed stack operations are amortized O(1), giving O(n) total time.

Queue Variants and Edge Cases

  • Simple FIFO queue: collections.deque is appropriate because popleft() and append() are efficient.

  • Circular queue: The same algorithm works through its dequeue and enqueue operations. A fixed-array circular queue advances indices using head = (head + 1) % capacity and tail = (tail + 1) % capacity.

  • Double-ended queue: deque also supports appendleft() and popleft(), although only FIFO operations are needed here.

  • Priority queue: heapq does not have a meaningful FIFO prefix to reverse because its ordering is based on priority rather than insertion order.

  • Thread-safe queue: Use queue.Queue for producer-consumer or multithreaded code instead of collections.deque.

The function leaves an empty queue unchanged when k = 0, handles a single element correctly, preserves duplicates and negative values, and raises ValueError for a negative k or one larger than the queue length.

Common Pitfalls

  • Do not use list.pop(0) to remove queue elements in a loop; each operation is O(n).

  • Forgetting to rotate the remaining n‑k elements leaves the reversed prefix at the back of the queue.

  • Decide and document how invalid k values are handled; raising ValueError is explicit and predictable.

  • Remember that the function mutates the supplied queue.

  • A common follow-up asks how to implement a FIFO queue using two stacks; its amortized operation cost is O(1).

31

How can queues implement an FIFO cache eviction policy?

FIFO (first-in, first-out) uses a queue to track cache entries in insertion order. When the cache reaches its capacity limit, the oldest entry is removed first, making FIFO suitable for workloads where insertion order should determine eviction priority.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A practical FIFO cache combines two data structures:

  • Queue: Stores cache keys in the order they were inserted. collections.deque.append() adds a key at the back, and popleft() removes the oldest key from the front.

  • Dictionary: Maps each key to its cached value and supports fast lookups and updates.

For each insertion:

  1. If the key already exists, update its value without changing its queue position.

  2. Otherwise, if the cache is full, remove the key at the front of the queue and delete it from the dictionary.

  3. Insert the new key into both the dictionary and the back of the queue.

FIFO is different from LRU: accessing an existing entry does not move it to the back of the queue. In LRU, a cache hit refreshes the entry’s recency.

Complexity

Operation Best Average Worst Reason
get or contains O(1) O(1) O(n) Dictionary lookup is constant time on average but can degrade during severe hash collisions.
put for an existing key O(1) O(1) O(n) The dictionary update does not change queue order; hash collisions determine the worst case.
put for a new key O(1) O(1) O(n) append, popleft, insertion, and deletion are constant-time on average; dictionary collision handling can cause O(n) worst-case behavior.
Space O(capacity) O(capacity) O(capacity) The queue and dictionary each store at most capacity entries; input data is not counted.

Queue operations are O(1) amortized because deque may occasionally resize its internal storage. In a typical bounded cache, the average end-to-end cost of an insertion or eviction is O(1).

Walkthrough

Suppose the cache has capacity 2:

Operation Queue after operation Cached values Result
Put a = 1 [a] {a: 1} Cache is not full.
Put b = 2 [a, b] {a: 1, b: 2} Cache is now full.
Put a = 3 [a, b] {a: 3, b: 2} Existing key updated; FIFO order is unchanged.
Put c = 4 [b, c] {b: 2, c: 4} a is evicted because it was inserted first.

Code Example

from collections import deque
from typing import Generic, TypeVar

Key = TypeVar("Key")
Value = TypeVar("Value")


class FifoCache(Generic[Key, Value]):
    """A bounded cache that evicts the oldest inserted key first."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be greater than zero")

        self.capacity = capacity
        self._entries: dict[Key, Value] = {}
        self._insertion_order: deque[Key] = deque()

    def get(self, key: Key) -> Value | None:
        """Return the value for key, or None if it is not cached."""
        return self._entries.get(key)

    def contains(self, key: Key) -> bool:
        """Return whether key is present in the cache."""
        return key in self._entries

    def put(self, key: Key, value: Value) -> Key | None:
        """Insert or update a key and return the evicted key, if any."""
        if key in self._entries:
            # FIFO does not refresh insertion order on a cache hit.
            self._entries[key] = value
            return None

        evicted_key: Key | None = None

        if len(self._entries) == self.capacity:
            evicted_key = self._insertion_order.popleft()
            del self._entries[evicted_key]

        self._entries[key] = value
        self._insertion_order.append(key)
        return evicted_key


cache: FifoCache[str, int] = FifoCache(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
cache.put("a", 3)
evicted = cache.put("c", 4)

print(evicted, cache.get("a"), cache.get("c"))
# Expected output: a None 4

Common Pitfalls and Interview Tips

  • Do not use list.pop(0): Removing the first list element is O(n), which would make repeated evictions inefficient. Use collections.deque.popleft().

  • Avoid duplicate queue entries: Check the dictionary before appending a key, otherwise one key could appear multiple times and be evicted incorrectly.

  • Do not reorder on cache hits unless implementing LRU instead of FIFO.

  • Handle capacity validation: A capacity of zero or a negative value should raise an error.

  • Distinguish missing keys from cached None values: get() returning None is ambiguous when None is a valid cached value; use contains() when presence matters.

  • Mention thread safety when relevant: collections.deque is appropriate for an in-process cache. Use queue.Queue when a thread-safe producer-consumer queue is required.

  • Discuss alternatives in interviews: FIFO is simple and predictable, but it may evict frequently used entries. LRU is usually better for general-purpose caches, while TTL-based eviction is appropriate when expiration times matter.

32

How do you rotate a queue by k elements?

A queue rotation moves elements from one end to the other while preserving their relative order. Here, a positive k is treated as a left rotation: the first k elements move to the rear of the queue.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Rotation Algorithm

For a FIFO queue containing n elements:

  1. Normalize the rotation with shift = k % n.

  2. Repeat shift times:

  3. Remove the front element with popleft().

  4. Insert it at the rear with append().

For example, rotating [10, 20, 30, 40] by 6 positions is equivalent to rotating it by 6 % 4 = 2 positions:

Step Queue
Initial [10, 20, 30, 40]
Move 10 to rear [20, 30, 40, 10]
Move 20 to rear [30, 40, 10, 20]

Python also provides deque.rotate(k) for right rotation and deque.rotate(-k) for left rotation. The explicit loop below makes the operation’s behavior and complexity straightforward.

Queue Variants

Variant Rotation behavior
Simple FIFO queue Move each front element to the rear k % size times.
Fixed-array circular queue Update head and tail using % capacity; move k % size elements from front to rear.
Double-ended queue Supports rotation from either end and is appropriate for collections.deque.
Priority queue Rotation is generally meaningless because heap ordering must remain valid; removing and reinserting elements costs at least O(k log n).

Use queue.Queue instead of deque only when thread-safe producer-consumer behavior is required.

Complexity

Let n be the queue size and r = k % n.

  • Best case: O(1) when r = 0, because no elements move.

  • Average case: O(n) when k is uniformly distributed over all rotation amounts.

  • Worst case: O(n) when r = n - 1.

  • Auxiliary space: O(1), excluding the input queue’s O(n) storage.

  • Recursion stack: O(1) because the algorithm is iterative.

Each popleft() and append() is O(1) worst-case, giving O(r) worst-case total time.

Code Example

from collections import deque
from typing import TypeVar

T = TypeVar("T")


def rotate_queue(queue: deque[T], k: int) -> None:
    """Rotate a FIFO queue left by k positions in place."""
    if not queue:
        return

    shift = k % len(queue)
    for _ in range(shift):
        queue.append(queue.popleft())


if __name__ == "__main__":
    queue = deque([10, 20, 30, 40])
    rotate_queue(queue, 6)
    print(list(queue))  # [30, 40, 10, 20]

Common Pitfalls

  • Direction ambiguity: State whether k means left or right rotation. The code above uses left rotation.

  • Empty queue: The function safely does nothing.

  • One element or k % n == 0: The order remains unchanged.

  • Duplicates and negative values: They are treated as ordinary elements and retain their relative order.

  • Large rotations: Normalize with k % n; repeatedly moving elements without normalization is unnecessary.

  • Mutable input: This implementation modifies the queue in place. Copy it first if the original order must be preserved.

  • Performance: Avoid list.pop(0) and list.insert(0, value) because they require O(n) shifts.

  • Graph edge cases: Disconnected graphs and cycles are not relevant to FIFO queue rotation.

33

How can a queue generate binary numbers from 1 to N?

A FIFO queue can generate the binary representations of integers 1 through N by traversing a binary tree in breadth-first order. Each dequeued value produces two children by appending 0 and 1 to its binary representation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Start the queue with 1, the binary representation of the first positive integer.

For each value removed from the queue:

  1. Convert the value to binary and add it to the result.

  2. Enqueue value * 2, representing the current binary representation with 0 appended.

  3. Enqueue value * 2 + 1, representing the current binary representation with 1 appended.

For example, the binary representation of 6 is 110:

  • 6 * 2 = 12, whose binary representation is 1100.

  • 6 * 2 + 1 = 13, whose binary representation is 1101.

Because the queue is FIFO, values are processed in ascending order, producing 1, 10, 11, 100, and so on.

Example Walkthrough

For N = 5:

Iteration Dequeued value Binary output Queue afterward
1 1 1 [2, 3]
2 2 10 [3, 4, 5]
3 3 11 [4, 5, 6, 7]
4 4 100 [5, 6, 7, 8, 9]
5 5 101 [6, 7, 8, 9, 10, 11]

Complexity

Under the standard unit-cost integer model:

Metric Complexity Reason
Queue operations O(N) time Each result requires one dequeue and at most two appends.
Total time including output O(N log N) Each of the N binary strings can contain up to O(log N) characters.
Auxiliary space O(N) The queue can contain O(N) integers.
Space including returned output O(N log N) The returned list stores N binary strings of up to O(log N) characters each.

The input bound is not copied or counted in the auxiliary-space figure. There is no recursion, so the recursion-stack space is O(1).

Code Example

from collections import deque


def generate_binary_numbers(n: int) -> list[str]:
    """Return the binary representations of integers from 1 through n."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return []

    queue: deque[int] = deque([1])
    result: list[str] = []

    for _ in range(n):
        value = queue.popleft()
        result.append(format(value, "b"))

        # Avoid adding children that cannot be needed for this result.
        if len(result) < n:
            queue.append(value * 2)
            queue.append(value * 2 + 1)

    return result


numbers = generate_binary_numbers(5)
print(numbers)  # ['1', '10', '11', '100', '101']

Common Pitfalls and Interview Tips

  • Avoid list.pop(0): Removing the first list element is O(n). collections.deque.popleft() is O(1).

  • Handle n = 0: Return an empty list rather than attempting to dequeue from an empty queue.

  • Handle n = 1: The result should be ["1"].

  • Reject negative values: Raise ValueError for a negative bound.

  • Do not add unnecessary children: The final iteration does not need to enqueue more values.

  • Duplicates cannot occur: Every positive integer has one unique parent, value // 2, and the two generated children are distinct.

  • Use queue.Queue only for threads: queue.Queue is appropriate for thread-safe producer-consumer systems, but it is unnecessary for this single-threaded algorithm.

  • Common follow-up: Interviewers may ask why value * 2 and value * 2 + 1 append binary digits, or how the approach changes if results should be streamed instead of collected.

34

How do queues support graph traversal algorithms?

A queue supports breadth-first search (BFS) by storing vertices in discovery order and processing them first-in, first-out. This makes BFS explore all vertices reachable through one edge before exploring vertices two edges away.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Queue-Based BFS Works

BFS maintains a FIFO queue containing the current traversal frontier:

  1. Enqueue the starting vertex and mark it as visited.

  2. Remove the front vertex using popleft().

  3. Add that vertex to the traversal order.

  4. Inspect its neighbors in the adjacency list.

  5. Enqueue each unvisited neighbor and immediately mark it as visited.

  6. Continue until the queue is empty.

Marking a vertex when it is enqueued—not when it is dequeued—prevents duplicate entries when a graph contains cycles or repeated edges.

For example:

0: [1, 2]
1: [3]
2: [3]
3: []
Step Queue before Action Queue after
1 [0] Dequeue 0; enqueue 1 and 2 [1, 2]
2 [1, 2] Dequeue 1; enqueue 3 [2, 3]
3 [2, 3] Dequeue 2; 3 is already visited [3]
4 [3] Dequeue 3 []

The traversal order is [0, 1, 2, 3].

Queue Variants for Graph Traversal

Variant Graph use Time and space
Simple FIFO queue Standard BFS using append() and popleft() O(1) per operation; O(V) frontier storage
Circular queue Fixed-capacity FIFO using head and tail modulo capacity O(1) per operation; O(capacity) storage
Double-ended queue collections.deque; 0-1 BFS can put zero-cost edges at the front O(1) per end operation; O(V) storage
Priority queue heapq for Dijkstra’s algorithm O(log E) per lazy heap operation and O(E) heap space; O(log V) for simple graphs
Thread-safe queue queue.Queue for producer-consumer systems O(1) work per successful operation, excluding blocking; O(n) storage

heapq implements a min-heap; negate numeric priority values to obtain max-heap behavior. Dijkstra requires non-negative edge weights, whereas ordinary BFS finds shortest paths measured by the number of edges. A monotonic deque is intended for sliding-window maximum rather than general graph traversal; each element is pushed and popped at most once, so that algorithm takes O(n) time.

Complexity

Let V be the number of vertices and E the number of edges.

  • Best case: O(1) for an absent or isolated start; O(V + E) when the complete graph is processed.

  • Average case: O(V + E), because each reachable vertex and adjacency entry is processed once and hash-based membership checks take O(1) expected time.

  • Worst case: O(V(V + E)) if adversarial hash collisions degrade dictionary and set lookups to O(V). With contiguous vertex labels and a boolean visited array, traversal is deterministically O(V + E).

  • Auxiliary space: O(V), including the visited set, queue, and traversal result. The input adjacency list is excluded; including it gives O(V + E) total space.

Code Example

from collections import deque
from queue import Empty, Full


def breadth_first_traversal(
    graph: dict[int, list[int]],
    start: int,
) -> list[int]:
    """Return the reachable vertices in breadth-first traversal order."""
    if not graph or start not in graph:
        return []

    visited: set[int] = {start}
    queue: deque[int] = deque([start])
    order: list[int] = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


class CircularQueue:
    """Fixed-capacity integer FIFO using modulo head and tail indices."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._items: list[int] = [0] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, value: int) -> None:
        if self._size == self._capacity:
            raise Full("queue is full")
        self._items[self._tail] = value
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self) -> int:
        if self._size == 0:
            raise Empty("queue is empty")
        value = self._items[self._head]
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value


graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2],
    4: [],
}

print(breadth_first_traversal(graph, 0))
# Expected output: [0, 1, 2, 3]

fixed_queue = CircularQueue(2)
fixed_queue.enqueue(7)
print(fixed_queue.dequeue())
# Expected output: 7

Common Pitfalls and Interview Tips

  • Do not use list.pop(0) because it is O(n); use deque.popleft().

  • Mark vertices visited when enqueuing them to prevent duplicates.

  • Empty graphs and unknown starts return an empty result; an isolated start returns one vertex.

  • Duplicate edges and cycles are handled by the visited set.

  • Negative vertex identifiers work with the dictionary implementation. Negative edge weights do not change BFS’s edge-count distance.

  • Sorted adjacency lists affect traversal order but not correctness.

  • BFS visits only the starting vertex’s connected component; run it from each unvisited vertex to traverse every component.

  • A circular queue raises Empty when empty and Full when its capacity is exceeded.

  • Common follow-ups include reconstructing shortest paths, counting connected components, traversing grids, and comparing BFS with DFS.

35

How do queues support CPU scheduling algorithms like Round Robin?

In CPU scheduling, a queue holds processes or threads that are ready to execute. Algorithms use it to decide which task runs next; in Round Robin scheduling, each task receives a fixed time quantum and returns to the back of the queue if it has not finished.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Queues Drive Scheduling

A scheduler generally maintains a ready queue containing runnable tasks:

  • The scheduler removes the next task from the front.

  • The task executes for a predetermined period.

  • If it completes, it leaves the queue.

  • If it still needs execution time, it is placed at the back.

  • In preemptive scheduling, tasks waiting for I/O leave the ready queue until they become runnable again.

Round Robin uses a simple FIFO queue so that tasks receive approximately equal service. The collections.deque implementation provides efficient append() and popleft() operations.

Round Robin Example

Given burst times [5, 3, 7], a quantum of 2, and process labels P0, P1, and P2:

  1. P0 runs for 2 units; 3 remain. Queue: [P1, P2, P0].

  2. P1 runs for 2 units; 1 remains. Queue: [P2, P0, P1].

  3. P2 runs for 2 units; 5 remain. Queue: [P0, P1, P2].

  4. P0 runs for 2 units; 1 remains. Queue: [P1, P2, P0].

  5. P1 runs for 1 unit and completes. Queue: [P2, P0].

  6. P2 runs for 2 units; 3 remain. Queue: [P0, P2].

  7. P0 runs for 1 unit and completes. Queue: [P2].

  8. P2 runs for 2 units; 1 remains, then runs for 1 unit and completes.

The completion order is [P1, P0, P2].

Queue Variants in Scheduling

Variant Scheduling use Important behavior
Simple FIFO queue Standard Round Robin ready queue Preserves arrival order for tasks with equal priority
Circular queue Fixed-capacity task or buffer queue Uses head and tail indices modulo capacity without shifting elements
Double-ended queue Scheduling tasks that may be added or cancelled at either end Supports O(1) insertion and removal at both ends
Priority queue Priority-based scheduling heapq implements a min-heap; use negated values for a max-heap
Monotonic deque Sliding-window maximum rather than CPU scheduling Each element is pushed and popped at most once, giving O(n) time
queue.Queue Thread-safe producer-consumer work queues Provides locking for inter-thread communication; it is unnecessary for a single-threaded scheduler

Complexity

For n tasks with burst times B[i] and quantum q:

  • Queue operations: append() and popleft() are O(1) best, average, and worst case in collections.deque.

  • Scheduling time: O(n + S), where S = Σ max(1, ceil(B[i] / q)) is the number of task dispatches. This is O(n) in the best case and at most O(n + B), where B = Σ B[i], in the worst case. The average depends on the burst-time distribution.

  • Space: O(n) extra space for the ready queue, remaining burst times, and output. The input is not counted, and no recursion stack is used.

Code Example

from collections import deque


def round_robin_completion_order(
    burst_times: list[int],
    quantum: int,
) -> list[int]:
    """Return process indexes in completion order using Round Robin."""
    if quantum <= 0:
        raise ValueError("quantum must be positive")
    if any(burst < 0 for burst in burst_times):
        raise ValueError("burst times must be non-negative")

    remaining = burst_times.copy()
    ready_queue: deque[int] = deque(range(len(burst_times)))
    completion_order: list[int] = []

    while ready_queue:
        process_index = ready_queue.popleft()
        execution_time = min(quantum, remaining[process_index])
        remaining[process_index] -= execution_time

        if remaining[process_index] == 0:
            completion_order.append(process_index)
        else:
            ready_queue.append(process_index)

    return completion_order


print(round_robin_completion_order([5, 3, 7], 2))
# [1, 0, 2]

Common Pitfalls

  • Using list.pop(0): Removing the first list element is O(n); use deque.popleft() for O(1) removal.

  • Invalid quantum: A quantum of zero causes an infinite loop; reject non-positive values.

  • Requeuing completed tasks: Only unfinished tasks should return to the ready queue.

  • Mutating input: Copy burst times before reducing them.

  • Duplicate values: Duplicate burst times are valid because process indexes provide distinct identities.

  • Edge cases: Empty input returns []; one process is handled normally; negative burst times are rejected. Input ordering does not affect correctness, while graph concepts such as cycles and disconnected components do not apply.

  • Real operating systems: Production schedulers also handle arrivals, blocked I/O, context-switch overhead, priorities, and timer interrupts, so the implementation above is a simplified model.

36

How do queues support thread-safe producer-consumer systems?

A queue provides a FIFO mechanism for safely handing work from producers to consumers. In Python’s producer-consumer pattern, queue.Queue synchronizes access with locks and condition variables, so threads do not need to share mutable state directly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • A producer places tasks into the queue with put().

  • A consumer retrieves tasks with get(), blocking when the queue is empty.

  • queue.Queue uses locks and condition variables to coordinate concurrent access.

  • Each consumer should call task_done() exactly once after finishing each retrieved item, including a sentinel when join() is used.

  • A unique sentinel value tells each consumer to stop. With multiple consumers, enqueue one sentinel per consumer; the sentinel must not collide with valid task values.

Use queue.Queue instead of collections.deque for thread-safe producer-consumer communication. A deque is appropriate for ordinary single-threaded FIFO operations, but it does not provide the synchronization required by multiple threads.

Small Example Walkthrough

For two workers processing [1, 2, 3]:

Stage Work queue Results
Initial [] []
Producer enqueues tasks [1, 2, 3] []
Worker A takes 1 [2, 3] [2]
Worker B takes 2 [3] [2, 2]
Worker A takes 3 [] [2, 2, 6]
Workers receive sentinels [] [2, 2, 6]

The exact worker assignment can vary, but each task is processed exactly once.

Complexity

The complexity excludes time spent waiting for another thread or the operating-system scheduler.

Operation Best Average Worst
put_nowait() or get_nowait() O(1) O(1) O(1)
  • Why O(1): queue.Queue stores items in a deque and inserts or removes them at its ends. put_nowait() raises Full for a full bounded queue, and get_nowait() raises Empty for an empty queue.

  • Core processing: Processing n tasks with w workers takes O(n + w) time when each task requires constant work.

  • Sorting results: The final sorted(results) takes O(n) when the results are already ordered and O(n log n) on average and in the worst case. Therefore, the complete function takes O(n + w) in the best case and O(n log n + w) on average and in the worst case.

  • Space: O(n + w), including the original input, queued tasks, results, sorted-result temporary storage, and worker objects. Excluding the input does not change the bound. No recursion stack is used.

Code Example

from collections.abc import Sequence
from queue import Queue
from threading import Thread


def process_items(items: Sequence[int], worker_count: int = 2) -> list[int]:
    """Double every item concurrently and return the sorted results."""
    if worker_count < 1:
        raise ValueError("worker_count must be at least 1")
    if len(items) == 0:
        return []

    task_queue: Queue[int | None] = Queue()
    result_queue: Queue[int] = Queue()

    def produce() -> None:
        for item in items:
            task_queue.put(item)

        # One sentinel terminates each consumer.
        for _ in range(worker_count):
            task_queue.put(None)

    def consume() -> None:
        while True:
            item = task_queue.get()
            try:
                if item is None:
                    return
                result_queue.put(item * 2)
            finally:
                task_queue.task_done()

    producer = Thread(target=produce, name="producer")
    workers = [
        Thread(target=consume, name=f"worker-{index}")
        for index in range(worker_count)
    ]

    producer.start()
    for worker in workers:
        worker.start()

    producer.join()
    task_queue.join()
    for worker in workers:
        worker.join()

    results: list[int] = []
    while not result_queue.empty():
        results.append(result_queue.get())

    return sorted(results)


print(process_items([1, 2, 3, 4], worker_count=2))  # [2, 4, 6, 8]

Best Practices and Edge Cases

  • Empty input: The function returns an empty list without starting threads.

  • One item: Exactly one worker processes the task.

  • Duplicates: Every occurrence is processed and preserved.

  • Negative numbers: Values are processed normally.

  • Already sorted input: Sorting the final results does not affect processing correctness.

  • Disconnected graphs and cycles: Not applicable to this queue scenario.

  • Use a bounded queue to control memory usage; its put() may block.

  • Do not use list.pop(0) to emulate a queue because removing the first element is O(n).

Common Pitfalls

  • Using collections.deque directly between threads without additional synchronization.

  • Sending only one sentinel when multiple consumers need to terminate.

  • Forgetting to balance put() and task_done() calls when using queue.join().

  • Assuming result order matches input order; completion order is nondeterministic.

  • Ignoring worker exceptions, which can leave consumers waiting indefinitely. Production systems should capture and report worker failures.

37

What is a dequeuable priority queue and when is it used?

A dequeuable priority queue is a priority queue that additionally allows a specified pending entry to be removed before it reaches the front. Many implementations also support decreasing an entry’s priority, which is useful when its urgency or ordering key changes while it is queued.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Operations

Using the min-heap convention, where a smaller ordering key means higher priority:

Operation Behavior Typical complexity
insert(item, key) Adds an item to the queue O(1) average; O(log n) worst
peek_min() Returns the best item without removing it O(1)
extract_min() Removes and returns the best item O(log n) average/worst
remove(item_id) Removes a specified pending item O(log n) average/worst
decrease_key(item_id, new_key) Changes the item’s ordering key and restores heap order O(log n) average/worst

The complexities assume a binary heap containing n entries and an index map for arbitrary removal and key updates.

Complexity

  • Insertion: O(1) best case and O(1) average case for random keys, because a new item normally rises only a constant number of levels on average. An adversarial key can rise through the entire heap, making the worst case O(log n).

  • Peek minimum: O(1) in all cases because the root contains the best item.

  • Extract minimum: O(log n) average and worst case because the last item replaces the root and may sift downward; it is O(1) when only one item exists.

  • Arbitrary removal or key update: O(log n) average and worst case in an indexed heap because the index map identifies the item’s position before the heap is repaired.

  • Building a heap: O(n) with heap construction.

Space is O(n), including the queued entries themselves. Excluding those entries, a plain binary heap uses O(1) auxiliary space, while an indexed heap uses an O(n) position map. All operations are iterative, so the recursion stack is O(1). Lazy deletion can require O(m) physical heap space after m insertions because canceled entries remain until they are popped.

Typical Implementations

  • Indexed binary heap: Stores the heap plus a map from stable item IDs to heap positions. This supports arbitrary removal and decrease-key operations in O(log n).

  • collections.deque: Provides FIFO or double-ended queue behavior with O(1) insertion and removal at the appropriate ends.

  • collections.heapq: Python 3.12’s min-heap supports efficient insertion, peeking, and extraction, but it does not directly remove an arbitrary element or update an existing priority.

  • Lazy deletion: Push versioned entries into heapq and mark obsolete entries as canceled. When a canceled entry reaches the top, discard it and continue. This avoids an index map but can accumulate stale entries and delay cleanup.

  • Double heaps: Maintain min-heap and max-heap structures for a double-ended priority queue. Lazy deletion can be used to detect and skip stale entries in both heaps.

For a max-priority queue using heapq, negate ordering keys before insertion and negate them again when reading them.

Queue Variants

Structure Core operations Time complexity Space Typical use
Simple FIFO queue Enqueue at rear, dequeue at front O(1) per operation O(n) BFS and buffering
Circular queue Fixed-capacity array with modulo indices O(1) per operation O(capacity) Bounded producer/consumer buffers
Double-ended queue Insert or remove at either end O(1) per operation O(n) Sliding windows and work scheduling
Priority queue Extract the best-priority entry O(log n) per heap update O(n) Task and event scheduling
Monotonic deque Maintain candidates in monotonic priority order O(1) amortized per operation O(n) Sliding-window maximum
Dequeuable priority queue Also remove or update a specified entry O(log n) per indexed operation O(n) Scheduling with cancellation and priority updates

A monotonic deque pushes and pops each candidate at most once, so a complete traversal takes O(n). In Python, use collections.deque rather than list.pop(0), which is O(n). Use queue.Queue for thread-safe producer/consumer code; use multiprocessing.Queue when exchanging data between processes.

When It Is Used

A dequeuable priority queue is valuable when queued work can become obsolete or change urgency before it is processed:

  • Dijkstra’s algorithm: When a vertex’s tentative distance decreases, update its existing queue entry or invalidate the old one. Edge weights must be non-negative.

  • Task scheduling: A pending task can be canceled, rescheduled, or given higher priority.

  • Event simulation: A scheduled event can be retracted before execution.

  • Caching and resource allocation: A cached object or waiting request can be invalidated by its identifier.

For Dijkstra’s algorithm, a settled set or stale-entry check prevents repeated processing in cyclic graphs. In a disconnected graph, unreachable vertices remain unsettled.

Common Pitfalls

  • Clarify the requirement: Normal extraction is already supported by an ordinary priority queue; arbitrary removal is the defining dequeuable extension.

  • heapq limitations: It does not directly support arbitrary deletion or priority updates; use an indexed structure or lazy deletion.

  • Duplicate values: Use stable unique IDs if one particular duplicate must be removed.

  • Empty queue: Define whether peek or extraction raises an exception or returns a sentinel.

  • Negative keys: They work normally; ordering still follows the numeric comparison rule.

  • Stale entries: A canceled entry must be skipped rather than processed.

  • Interview follow-up: Expect questions about indexed heaps, lazy-deletion trade-offs, and how Dijkstra’s algorithm updates priorities.

38

How do queues support BFS and A* pathfinding?

Queues manage the search frontier in BFS and A*. BFS uses a FIFO queue to explore nodes level by level, while A* uses a priority queue ordered by estimated total cost to explore promising paths first.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

BFS and the FIFO Queue

In breadth-first search, the queue contains discovered nodes that have not yet been expanded.

  1. Enqueue the starting node.

  2. Remove the oldest node with popleft().

  3. Enqueue each unvisited, reachable neighbor.

  4. Stop when the goal is removed or the queue becomes empty.

Because every edge has equal cost, nodes are explored in increasing distance from the start. Nodes should normally be marked visited when enqueued; otherwise, they may enter the queue multiple times.

In Python, collections.deque is the expected implementation. Both append() and popleft() take O(1) time. Using list.pop(0) would make each removal O(n) because all remaining elements must shift left.

A* and the Priority Queue

A* also maintains a frontier, but it should not use an ordinary FIFO queue. Its frontier is a min-priority queue containing candidates ordered by:

f(n) = g(n) + h(n)

  • g(n) is the known cost from the start to n.

  • h(n) estimates the cost from n to the goal.

  • f(n) is the estimated cost of a complete path through n.

The candidate with the smallest f(n) is removed next. This allows A* to move toward the goal instead of exploring every node in breadth-first order. In Python, heapq implements a min-heap; heappush() and heappop() take O(log q) for a queue of size q.

For an optimal A* search, h(n) should be admissible: it must not overestimate the remaining cost. A consistent heuristic, which also satisfies |h(n) - h(m)| <= cost(n,m), prevents a settled node from needing to be reopened.

Queue Variants and Complexity

Variant Typical use
FIFO queue or deque BFS, buffering, task scheduling
Priority queue or heapq A*, Dijkstra, ordered task processing
Circular queue Fixed-capacity FIFO systems
Monotonic deque Sliding-window maximum; not standard BFS or A*
queue.Queue Thread-safe producer-consumer systems

For a graph with V vertices and E edges:

Algorithm Time Auxiliary space Reason
BFS Worst O(V + E); best O(1) when start is goal; average depends on goal depth Worst O(V); best O(1) In the worst case every reachable vertex is visited and every edge examined; the queue holds at most one level of nodes
A* with a consistent heuristic Best O(1) when start equals goal; average/worst upper bound O((V + E) log V) O(V + E) with duplicate heap entries; O(V) for a grid or with decrease-key Each priority-queue operation costs O(log V)

These space bounds exclude the input graph and include the queue or heap. Recursion-stack space is O(1) because both implementations are iterative.

Worked Example

For a grid containing a wall, the frontier develops approximately as follows:

Expanded node BFS FIFO frontier A* min-heap frontier
Start (0, 0) [(0, 0)] (0, 0), f = 4.24
(0, 0) [(0, 1)] (0, 1), f = 4.61
(0, 1) [(0, 2)] (0, 2), f = 5.16
(0, 2) [(0, 3), (1, 2)] (1, 2), f = 5.24 and (0, 3), f = 6.00

BFS proceeds strictly by insertion order. A* selects the smallest f value and still finds the same shortest path in this unweighted grid.

Code Example

from collections import deque
from heapq import heappop, heappush
from math import hypot

Position = tuple[int, int]
Grid = list[list[int]]


def _validate(grid: Grid, start: Position, goal: Position) -> None:
    if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("Grid must be non-empty and rectangular")

    rows, columns = len(grid), len(grid[0])
    for position in (start, goal):
        row, column = position
        if not (0 <= row < rows and 0 <= column < columns):
            raise ValueError("Position is outside the grid")
        if grid[row][column] != 0:
            raise ValueError("Start and goal must be traversable")


def _neighbors(grid: Grid, position: Position) -> list[Position]:
    row, column = position
    result: list[Position] = []

    for row_delta, column_delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_row = row + row_delta
        next_column = column + column_delta
        if (
            0 <= next_row < len(grid)
            and 0 <= next_column < len(grid[0])
            and grid[next_row][next_column] == 0
        ):
            result.append((next_row, next_column))

    return result


def _restore(
    parent: dict[Position, Position | None], goal: Position
) -> list[Position]:
    path: list[Position] = []
    current: Position | None = goal

    while current is not None:
        path.append(current)
        current = parent[current]

    return path[::-1]


def bfs_path(grid: Grid, start: Position, goal: Position) -> list[Position]:
    """Return a shortest four-direction path in an unweighted grid."""
    _validate(grid, start, goal)
    frontier: deque[Position] = deque([start])
    parent: dict[Position, Position | None] = {start: None}

    while frontier:
        current = frontier.popleft()
        if current == goal:
            return _restore(parent, goal)

        for neighbor in _neighbors(grid, current):
            if neighbor not in parent:
                parent[neighbor] = current
                frontier.append(neighbor)

    raise ValueError("No path exists")


def astar_path(grid: Grid, start: Position, goal: Position) -> list[Position]:
    """Return a shortest path using A* with a consistent Euclidean heuristic."""
    _validate(grid, start, goal)

    def heuristic(position: Position) -> float:
        return hypot(goal[0] - position[0], goal[1] - position[1])

    distances: dict[Position, float] = {start: 0.0}
    parent: dict[Position, Position | None] = {start: None}
    closed: set[Position] = set()
    sequence = 0
    frontier: list[tuple[float, int, Position, float]] = [
        (heuristic(start), sequence, start, 0.0)
    ]

    while frontier:
        _, _, current, current_cost = heappop(frontier)

        if current in closed or current_cost != distances[current]:
            continue

        closed.add(current)
        if current == goal:
            return _restore(parent, goal)

        for neighbor in _neighbors(grid, current):
            tentative_cost = current_cost + 1.0
            if tentative_cost < distances.get(neighbor, float("inf")):
                distances[neighbor] = tentative_cost
                parent[neighbor] = current
                sequence += 1
                heappush(
                    frontier,
                    (
                        tentative_cost + heuristic(neighbor),
                        sequence,
                        neighbor,
                        tentative_cost,
                    ),
                )

    raise ValueError("No path exists")


grid = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]

# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)]
print(bfs_path(grid, (0, 0), (3, 3)))

# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)]
print(astar_path(grid, (0, 0), (3, 3)))

Common Pitfalls

  • Using list.pop(0) creates an O(n) queue operation; use deque.popleft().

  • Mark BFS nodes visited when enqueued to prevent duplicates and cycles.

  • Do not ignore stale A* heap entries after finding a cheaper route.

  • A* is not generally optimal with an inadmissible heuristic, and negative edge costs are incompatible with standard A* and Dijkstra.

  • Always handle an empty grid, an unreachable goal, and start == goal.

  • The code does not mutate the input grid, and parent maps support reconstructing the final path.

39

How do queues support event-driven programming and messaging systems?

A queue provides a FIFO boundary between event producers and consumers. In event-driven systems, it buffers ready events or tasks; in message-queueing systems, a broker stores and routes messages so producers and consumers can operate independently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Queues Are Used

  • Decoupling: Producers enqueue work without waiting for consumers to process it.

  • Event scheduling: An event loop or task scheduler dequeues callbacks, jobs, or notifications in arrival order.

  • Buffering: A queue absorbs temporary bursts and smooths differences between production and consumption rates.

  • Load balancing: Several consumers can process messages from the same queue, allowing work to be shared.

  • Failure isolation: If a consumer is unavailable, queued messages remain available for later processing.

  • Backpressure: A bounded queue can temporarily slow producers when consumers cannot keep up.

In a message broker, the queue is usually more than an in-memory collection. It commonly provides persistence, acknowledgements, retries, visibility timeouts, routing, and dead-letter queues.

Queue Variants

Variant Typical use Time complexity Space complexity
Simple FIFO with collections.deque General event and message buffering append and popleft: O(1) best/average/worst (a deque is a linked list of fixed-size blocks, so it never copies to grow) O(q) for q queued items
Fixed circular queue Bounded buffers with predictable capacity O(1) best/average/worst for enqueue and dequeue O(capacity)
Double-ended queue Work queues supporting both FIFO and LIFO behavior End operations are O(1) O(q)
Priority queue using heapq Scheduling urgent tasks first heappush: O(1) best, O(log n) average/worst; heappop: O(log n) O(n)
Monotonic deque Sliding-window maximum O(n) total because each element is pushed and popped at most once O(n) worst case

A circular queue uses a fixed array with head and size; the insertion index is (head + size) % capacity. It distinguishes full and empty states without wasting array positions.

heapq is a min-heap. Negate priority values when a max-heap is required. In a monotonic deque, dominated elements are removed from the back, ensuring each element is added once and removed at most once.

Delivery Semantics

  • At-least-once delivery may produce duplicates after a consumer processes a message but its acknowledgement is lost. Consumers should therefore be idempotent.

  • Ordering is normally guaranteed within a queue or broker partition, not necessarily across the entire system.

  • Retries should use backoff and eventually send permanently failing messages to a dead-letter queue.

  • Publish/subscribe differs from ordinary queue consumption: subscriptions fan out messages to interested consumers, while competing consumers usually share the messages in one queue.

Code Example

This function models an event-driven worker consuming queued events in FIFO order:

from collections import deque


def process_events(events: list[str]) -> list[str]:
    """Consume events from a FIFO queue and return their processing order."""
    pending: deque[str] = deque()

    for event in events:
        pending.append(event)

    processed: list[str] = []
    while pending:
        processed.append(pending.popleft())

    return processed


print(process_events(["order.created", "payment.received"]))
# Expected output: ['order.created', 'payment.received']

The trace is:

  1. order.created is appended.

  2. payment.received is appended.

  3. popleft() returns order.created.

  4. popleft() returns payment.received.

For a thread-safe producer-consumer system, use queue.Queue; it provides locking and blocking operations. It remains process-local and does not provide the durability of a message broker.

Common Pitfalls

  • Using list.pop(0): Removing the front of a Python list is O(n) because remaining elements must shift. Use collections.deque and popleft().

  • Assuming exactly-once processing: Design consumers to tolerate duplicate deliveries.

  • Ignoring backpressure: Unbounded queues can exhaust memory during traffic spikes.

  • Losing failure information: Configure retries, error handling, and dead-letter queues.

  • Incorrect edge-case assumptions: Empty input produces no processed events, one event is preserved, duplicates remain separate messages, and values such as negative identifiers are unchanged. Sortedness is irrelevant because FIFO preserves arrival order.

  • Interview follow-ups: Expect questions about acknowledgement timing, ordering, duplicate handling, queue capacity, priority scheduling, throughput, and horizontal scaling.

40

Why are queues important in OS process management

Queues are the fundamental data structure that enables an operating system to serialize, prioritize, and fairly allocate CPU time and other resources among competing processes. They appear at every level of process management: the scheduler’s ready queue, per-device wait queues, the job queue for long-term admission, and message queues for inter-process communication.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Queues in Process Management

  • Job queue: Holds all processes in the system (newly submitted, waiting for memory). The long-term scheduler picks from here.

  • Ready queue: Contains processes that are in memory and ready to execute. The short-term (CPU) scheduler selects the next process from this queue.

  • Wait/block queues: One per I/O device or event (disk, keyboard, timer, semaphore). A process moves here when it requests I/O or waits for a signal; it returns to the ready queue when the event occurs.

  • Priority queues: Used when scheduling is priority-based (e.g., real-time systems). Implemented as a heap so the highest-priority ready process is always at the front.

  • Message queues: Kernel-managed buffers for IPC; processes send/receive messages without shared memory.

Scheduling Algorithms Built on Queues

Algorithm Queue Discipline Typical Use Case
First-Come-First-Served (FCFS) Simple FIFO Batch systems, simple embedded
Round Robin Circular FIFO with time slice Time-sharing, general-purpose OS
Priority Scheduling Priority queue (heap) Real-time, multi-class workloads
Multilevel Queue Multiple FIFO queues, fixed priority Separate system/interactive/batch
Multilevel Feedback Queue Multiple queues, processes migrate Adaptive general-purpose (Windows, classic Unix/BSD schedulers; Linux instead uses CFS, a red-black tree ordered by virtual runtime, replaced by EEVDF in 6.6)

Process State Transitions and Queue Movement

  1. New → Ready: Long-term scheduler admits process; enqueued on ready queue.

  2. Ready → Running: Short-term scheduler dequeues from ready queue; dispatches to CPU.

  3. Running → Ready: Time slice expires (Round Robin) or higher-priority process arrives (preemptive); re-enqueued on ready queue.

  4. Running → Wait: Process requests I/O or waits on semaphore; enqueued on device/event wait queue.

  5. Wait → Ready: I/O completes or signal received; interrupt handler moves process from wait queue to ready queue.

  6. Running → Terminated: Process exits; resources released, PCB deallocated.

Concurrency and Synchronization

  • Semaphores and mutexes internally maintain a wait queue of blocked threads. wait() enqueues the caller if the count is zero; signal() dequeues one waiter.

  • Condition variables associate a wait queue with a predicate; wait() atomically releases the mutex and enqueues the thread.

  • Lock-free queues (e.g., Michael-Scott queue) are used in kernel paths where blocking is unacceptable.

Interrupt Handling and Buffering

  • Interrupt request (IRQ) queues: Hardware interrupts are queued by the interrupt controller; the OS processes them in priority order.

  • Softirq/tasklet queues: Deferred work (bottom halves) runs after the hard interrupt, preventing long IRQ handler execution.

  • Spooling queues: Print jobs, network packets, and disk I/O requests are buffered in queues to decouple producer speed from consumer speed.

Time and Space Complexity

Operation Simple FIFO (deque) Priority Queue (heap)
Enqueue O(1) O(log n)
Dequeue O(1) O(log n)
Peek O(1) O(1)
Space O(n) O(n)

Reason: collections.deque uses a doubly-linked block array; heap operations traverse tree height.

Interview Tips

  • Know the three classic queues: job, ready, wait — and which scheduler owns each.

  • Explain Round Robin with a circular queue: time quantum expires → move PCB to tail.

  • Priority inversion: a high-priority task waits on a lock held by low-priority task; solution is priority inheritance (boost holder’s priority temporarily).

  • Multilevel feedback queue: processes that use full time slices are demoted; I/O-bound processes stay high. This approximates SJF without knowing burst times.

  • Don’t confuse kernel queues with user-space queue.Queue: the latter is for thread-safe producer/consumer in Python; the former is implemented in C with spinlocks or lock-free algorithms.

  • Follow-up questions: “How would you implement a scheduler with O(1) enqueue/dequeue and priority support?” (answer: multiple FIFO queues per priority level, or a calendar queue). “What happens if the ready queue is empty?” (idle task runs, or CPU halts via HLT/WFI).

41

How does a queue implement the producer-consumer model in Python?

A Queue decouples producers from consumers: producers add work items, while consumers retrieve and process them independently. In Python, queue.Queue provides this pattern with thread-safe FIFO operations and optional bounded capacity for backpressure.

Read full answer

Applies toPython 3.12

How It Works

The producer-consumer model separates task creation from task execution:

  1. Producer threads create work and call put() to add it to the queue.

  2. Consumer threads call get() to retrieve work and process it.

  3. queue.Queue coordinates access using locks and conditions.

  4. A bounded queue blocks producers when it is full, preventing unlimited memory growth.

  5. Consumers block when the queue is empty, avoiding busy waiting.

  6. A sentinel value such as None tells consumers that no more work will arrive.

This design is useful for task scheduling, request buffering, work distribution, and parallel data processing.

Queue Variants

Implementation Behavior Typical Use
queue.Queue Thread-safe FIFO queue with optional capacity Thread-based producer-consumer systems
collections.deque In-process FIFO or double-ended queue; not thread-safe Local buffers, BFS, sliding windows
multiprocessing.Queue FIFO queue shared between processes Multiprocessing workers
queue.PriorityQueue Thread-safe queue ordered by priority Scheduling by urgency or cost
Circular queue Fixed-size array using modulo-based head and tail indices Embedded systems and fixed-capacity buffers

Use queue.Queue when producer and consumer threads need thread-safe coordination. Use multiprocessing.Queue when the workers are separate processes.

Complexity

For n items, w consumers, and bounded queue capacity q:

  • Queue operations: put() and get() have O(1) best, average, and worst-case algorithmic overhead. Actual waiting time depends on producer and consumer speed.

  • Total time: O(n) when each item requires O(1) processing, or O(n × T) for task-processing cost T.

  • Space: O(n + w), including the results and consumer state. The bounded task queue itself uses O(min(n, q)).

  • Input storage: The input list is excluded from the implementation’s additional-space calculation.

  • Recursion stack: No recursion is used, so there is no recursion-stack cost.

Example Walkthrough

For [1, 2, 3, 4] with two consumers and a queue capacity of two:

  1. The producer inserts 1 and 2; the queue is now full.

  2. Two consumers retrieve 1 and 2, producing 1 and 4.

  3. The producer resumes and inserts 3 and 4.

  4. The consumers produce 9 and 16.

  5. The producer inserts one None sentinel per consumer.

  6. Each consumer processes its sentinel and exits.

The result is [1, 4, 9, 16] after sorting; the original completion order can vary.

Code Example

from queue import Empty, Queue
from threading import Thread


def run_producer_consumer(
    values: list[int],
    worker_count: int = 2,
    queue_size: int = 2,
) -> list[int]:
    """Run producer-consumer workers and return their sorted results."""
    if worker_count <= 0:
        raise ValueError("worker_count must be positive")
    if queue_size <= 0:
        raise ValueError("queue_size must be positive")

    task_queue: Queue[int | None] = Queue(maxsize=queue_size)
    result_queue: Queue[int] = Queue()

    def consume() -> None:
        while True:
            item = task_queue.get()
            try:
                if item is None:
                    return
                result_queue.put(item * item)
            finally:
                task_queue.task_done()

    def produce() -> None:
        try:
            for item in values:
                task_queue.put(item)
        finally:
            # One sentinel stops each consumer.
            for _ in range(worker_count):
                task_queue.put(None)

    consumer_threads = [
        Thread(target=consume, name=f"consumer-{index}")
        for index in range(worker_count)
    ]
    producer_thread = Thread(target=produce, name="producer")

    for thread in consumer_threads:
        thread.start()
    producer_thread.start()

    producer_thread.join()
    task_queue.join()

    for thread in consumer_threads:
        thread.join()

    results: list[int] = []
    while True:
        try:
            results.append(result_queue.get_nowait())
        except Empty:
            break

    return sorted(results)


print(run_producer_consumer([1, 2, 3, 4]))  # [1, 4, 9, 16]

Common Pitfalls

  • Missing task_done(): Every successful get() must have exactly one matching task_done() when using Queue.join().

  • Deadlock: Avoid calling put() while holding unrelated locks, and ensure every consumer can eventually receive a shutdown sentinel.

  • Using empty() for synchronization: It is unreliable when other threads may add or remove items; use blocking get() instead.

  • Unbounded production: Set maxsize when downstream processing is slower than production.

  • Incorrect shutdown: Send one sentinel per consumer, not one for the entire queue.

  • Edge cases: The example handles empty input, one item, duplicates, and negative integers; invalid worker or queue sizes raise ValueError.

  • Process boundary: queue.Queue cannot be shared across processes; use multiprocessing.Queue there.

42

How do queues support network packet routing and load balancing?

Queues are the buffering and scheduling mechanism used by routers, proxies, and application servers. They hold packets or requests when arrival rates exceed processing or transmission rates, then apply policies such as FIFO, priority, or weighted scheduling to determine what is sent next.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Queues Support Routing and Load Balancing

In packet routing, a router commonly maintains a separate output queue for each outgoing interface:

  1. Packets arrive from an incoming interface.

  2. The forwarding engine determines the destination interface.

  3. Each packet is appended to that interface’s queue.

  4. If the link is busy, packets wait in the buffer.

  5. A scheduling algorithm selects packets for transmission.

  6. Successfully transmitted packets are removed from the queue.

In load balancing, a queue holds pending packets, connections, or requests while workers or backend servers become available. The scheduler can distribute work using round-robin, least-connections, weighted scheduling, or work stealing.

Queues also provide backpressure: when a buffer is full, a router may drop packets, mark congestion with ECN, apply traffic shaping, or rely on upstream flow-control mechanisms where supported.

Common Queue Variants

Variant Networking use Time complexity Space complexity
Simple FIFO queue Buffers packets in arrival order O(1) per enqueue/dequeue O(q) for q queued packets
Circular queue Uses a fixed-size array for a bounded buffer O(1) per operation O(c) for capacity c
Deque Supports queue-like operations at both ends O(1) per end operation O(q)
Priority queue Gives higher-priority traffic earlier service O(log p) per heap insertion/removal O(p)

These per-operation bounds have the same best, average, and worst-case order for the stated implementations. The space bounds count queued entries and exclude the input storage.

In Python, collections.deque is the usual non-thread-safe FIFO queue because append() and popleft() are O(1). A priority queue can be built with heapq, which is a min-heap; lower values receive earlier service. Use queue.Queue for thread-safe producer-consumer communication.

Routing and Load-Balancing Strategies

  • FIFO: Simple and preserves packet order within one queue, but one large flow can occupy the buffer.

  • Priority scheduling: Serves voice or interactive traffic before bulk traffic. Strict priority may starve lower-priority classes.

  • Weighted fair queueing: Gives selected queues different bandwidth shares while supporting fair treatment among flows.

  • Round-robin balancing: Sends packets or requests to workers in rotation. It is simple and fair per packet, but it is not flow-aware.

  • Least-connections balancing: Sends new work to the backend with the fewest active connections. This is useful when request durations vary.

  • Work stealing: Workers first process their own queues and then take work from idle or overloaded peers.

A router may use separate queues for different traffic classes. Each queue can have its own scheduling weight, allowing VoIP traffic to receive predictable service without completely blocking file transfers.

Complexity and Operational Trade-offs

Queue operations are efficient but do not remove the fundamental limits of buffering:

  • FIFO, circular, and deque operations take O(1) best, average, and worst-case time per operation.

  • Heap-based priority-queue insertion and removal take O(log p) in the best, average, and worst cases because the heap property may need to be restored.

  • Queue storage is O(q) auxiliary space for q queued items, excluding the input source. Including input storage, total space is O(q + n) when n is the number of input items.

  • Larger buffers can absorb short traffic bursts but also increase queueing delay and memory use.

Best Practices

  • Use deque.append() and deque.popleft() in Python; list.pop(0) is O(n) and can become a bottleneck.

  • Set explicit queue-size limits to control memory usage and limit bufferbloat.

  • Preserve ordering per flow when the application requires it.

  • Use weighted scheduling when traffic classes have different service requirements.

  • Distinguish queue delay from processing delay when diagnosing latency.

  • Avoid unnecessary packet copies, especially in high-throughput network code.

  • Use thread-safe queues only when coordination between multiple producers and consumers is required.

Common Pitfalls

  • Head-of-line blocking: A FIFO queue can delay later packets behind a slow or large flow.

  • Priority starvation: Strict priority scheduling can indefinitely delay low-priority traffic.

  • Unbounded buffers: Accepting packets indefinitely increases latency and may exhaust memory.

  • Unfair balancing: Round-robin equalizes packet counts, not bandwidth use or connection duration.

  • Incorrect circular-queue capacity handling: A fixed array must distinguish full and empty states correctly, often by reserving one slot or tracking a count.

  • Order violations: Multiple queues or parallel workers may reorder packets globally even when each individual queue remains FIFO.

43

How to reduce time complexity of queue operations

The time complexity of queue operations depends on the underlying implementation. A well-chosen structure — array-based circular buffer, linked list, or double-ended queue — gives O(1) enqueue and dequeue, while a naive Python list with pop(0) is O(n). For priority queues, a binary heap provides O(log n) insertion and removal. Amortized analysis shows that dynamic-array queues and two-stack queues achieve O(1) amortized cost per operation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Implementation Choices and Their Complexities

Implementation Enqueue Dequeue Peek Space Notes
Circular array (fixed size) O(1) O(1) O(1) O(capacity) Best when max size known; no allocation overhead
Dynamic array (resizing) O(1) amortized O(1) amortized O(1) O(n) Resizing copies elements; amortized cost stays constant
Singly linked list (tail pointer) O(1) O(1) O(1) O(n) Extra memory per node; no resizing needed
collections.deque (CPython) O(1) O(1) O(1) O(n) Block-linked list; thread-safe for single-producer/consumer
Two stacks (queue via stacks) O(1) amortized O(1) amortized O(1) amortized O(n) Useful when only stack primitives available
Binary heap (priority queue) O(log n) O(log n) O(1) O(n) Order by priority, not FIFO

Key Optimization Strategies

  • Avoid list.pop(0) or list.insert(0, x) in loops — both shift all elements, making each call O(n). Use collections.deque instead.

  • Pre-allocate capacity when the maximum size is known (circular buffer). This eliminates resizing overhead and guarantees worst-case O(1).

  • Use a tail pointer in linked-list queues so enqueue does not traverse the list.

  • Amortized resizing: grow the backing array by a constant factor (e.g., 2×) so the cost of copying is spread over many cheap inserts.

  • Batch operations when the API allows: deque.extend(iterable) and deque.extendleft(iterable) are faster than repeated single-element calls.

  • Choose the right variant: a double-ended queue (deque) supports O(1) inserts/removes at both ends; a priority queue (heapq) is needed when processing order depends on a key, not arrival time.

When to Use Which Structure

  • BFS, task scheduling, rate limiting, buffering → simple FIFO queue (deque or circular array).

  • Sliding window maximum/minimum → monotonic deque (each element pushed and popped at most once, total O(n)).

  • Thread-safe producer/consumer → queue.Queue (internally uses a deque with locks).

  • Priority-based processing (Dijkstra, Huffman, event simulation) → binary heap (heapq).

  • Interview constraint: “implement a queue using two stacks” → two-stack approach with amortized O(1).

Common Pitfalls

  • Using list as a queue: pop(0) is O(n); the interview expects deque or a custom circular buffer.

  • Forgetting the modulo operation in a circular array: tail = (tail + 1) % capacity and similarly for head.

  • Not handling empty/full conditions in a fixed-size circular queue: distinguish full from empty by keeping one slot unused or tracking size separately.

  • Assuming heapq is a max-heap: it is a min-heap; negate values or store (-priority, item) for max-heap behavior.

  • Mutating the input queue in a function that should be non-destructive — copy with deque(original) if needed.

  • Recursion depth in queue-based algorithms (e.g., recursive BFS): prefer iterative loops; Python’s default recursion limit is ~1000.

Interview Tips

  • State the complexity upfront: “Enqueue and dequeue are O(1) amortized with a dynamic array, O(1) worst-case with a circular buffer or linked list.”

  • Explain amortization: “Resizing happens rarely; the total cost of n inserts is O(n), so average cost per insert is O(1).”

  • Know the two-stack queue: push to in_stack, pop from out_stack; when out_stack is empty, reverse in_stack into it. Each element moves at most twice → amortized O(1).

  • Monotonic deque for sliding window: maintain decreasing values; pop from back while new value is larger, pop from front when index leaves window. Each element enters and leaves once → O(n) total.

  • Follow-up: “How would you implement a queue with O(1) worst-case (not amortized)?” → circular array with fixed capacity or linked list with tail pointer. “How to make it thread-safe?” → queue.Queue or add locks to a custom implementation.

44

How can stack and queue operations be implemented together efficiently?

Two stacks provide the classic efficient implementation of a FIFO queue using only stack operations: enqueue is O(1), while dequeue is O(1) amortized. If the same structure must directly support both LIFO and FIFO behavior, Python’s collections.deque is simpler and supports append/pop and append/popleft in O(1) worst-case time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Design

A queue implemented with two stacks maintains:

  • Incoming stack: New elements are pushed here.

  • Outgoing stack: Elements are moved here when a removal is required.

  • Transfer rule: If the outgoing stack is empty, move every element from the incoming stack to it.

  • FIFO ordering: Reversing the incoming stack during transfer places the oldest element on top of the outgoing stack.

The transfer must happen only when the outgoing stack is empty. Otherwise, newly arriving elements would be inserted before older elements waiting for removal.

Complexity

Operation Best case Average/amortized Worst case Reason
enqueue O(1) O(1) amortized O(n) A Python list may occasionally resize while appending
dequeue O(1) O(1) amortized O(n) The outgoing stack may need to be filled from the incoming stack
peek O(1) O(1) amortized O(n) It may trigger the same transfer as dequeue
is_empty O(1) O(1) O(1) It checks both stacks

For a sequence of (m) queue operations, total time is O(m): every element is pushed into the incoming stack, transferred at most once, and removed at most once.

Space complexity is O(n) including the n stored queue elements. The input sequence is not copied, there is no recursion stack, and auxiliary overhead beyond the stored elements is O(1).

Walkthrough

For enqueue(A), enqueue(B), then dequeue():

  1. Incoming stack: [A, B]; outgoing stack: [].

  2. The outgoing stack is empty, so transfer elements.

  3. Transfer B, then A: outgoing stack becomes [B, A].

  4. Pop A from the outgoing stack, preserving FIFO order.

  5. The next dequeue() returns B in O(1).

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class QueueUsingStacks(Generic[T]):
    """Implement a FIFO queue using two LIFO stacks."""

    def __init__(self) -> None:
        self._incoming: list[T] = []
        self._outgoing: list[T] = []

    def enqueue(self, value: T) -> None:
        """Add an element to the back of the queue."""
        self._incoming.append(value)

    def _prepare_for_removal(self) -> None:
        if not self._outgoing:
            while self._incoming:
                self._outgoing.append(self._incoming.pop())

    def dequeue(self) -> T:
        """Remove and return the oldest element."""
        self._prepare_for_removal()
        if not self._outgoing:
            raise IndexError("dequeue from empty queue")
        return self._outgoing.pop()

    def peek(self) -> T:
        """Return the oldest element without removing it."""
        self._prepare_for_removal()
        if not self._outgoing:
            raise IndexError("peek from empty queue")
        return self._outgoing[-1]

    def is_empty(self) -> bool:
        """Return whether the queue contains no elements."""
        return not self._incoming and not self._outgoing

    def __len__(self) -> int:
        return len(self._incoming) + len(self._outgoing)


queue = QueueUsingStacks[str]()
queue.enqueue("A")
queue.enqueue("B")
print(queue.dequeue())  # A

For a directly combined stack and queue, use collections.deque: append and pop provide stack behavior, while append and popleft provide queue behavior.

Best Practices and Edge Cases

  • Empty queue: dequeue and peek should raise a clear exception rather than silently return None.

  • One element: It transfers to the outgoing stack and is returned correctly.

  • Duplicates: Preserve every occurrence; queues do not deduplicate values.

  • Negative or other values: The implementation is generic and does not depend on value ordering.

  • Concurrency: For thread-safe producer-consumer code, use queue.Queue instead of this custom structure.

  • Direct deque usage: When there is no requirement to implement the queue using stacks, prefer collections.deque for simpler worst-case O(1) operations.

Common Pitfalls

  • Transferring elements on every dequeue causes O(n) work repeatedly and can degrade total performance to O(n²).

  • Removing from the beginning of a Python list with pop(0) is O(n); use collections.deque or the two-stack design instead.

  • A single dequeue can take O(n), so describe the guarantee as O(1) amortized, not always O(1).

  • Do not assume FIFO ordering merely because values were inserted in order; the transfer reverses the internal stack intentionally.

  • A frequent follow-up is: “Why is each element transferred only once?” Because an element moves from incoming to outgoing once and is then removed without being transferred back.

45

How do modern CPU and memory caching affect queue performance?

Modern CPUs and the memory hierarchy affect queue performance chiefly through cache locality: contiguous data usually incurs fewer cache misses than pointer-chasing layouts. Consequently, queues with the same asymptotic complexity can have substantially different real-world execution times.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How CPU Caching Affects Queues

CPU caches hold recently accessed data in faster levels such as L1, L2 and L3; main memory has much higher latency.

  • Contiguous storage: Circular-buffer operations access neighboring memory, benefiting from cache lines, spatial locality and hardware prefetching.

  • Block-based storage: CPython’s collections.deque stores references in linked, fixed-size blocks. Most operations touch one block; crossing a block boundary adds pointer traversal but avoids shifting elements.

  • Linked-node storage: Nodes may occupy scattered memory, causing cache misses and pointer-chasing overhead on every traversal.

  • Heap storage: heapq uses a contiguous list, but heap sifting jumps between parent and child positions, so it is less local than FIFO operations.

  • Concurrent queues: Producer and consumer threads updating nearby head and tail counters can cause false sharing, repeatedly invalidating the same CPU cache line.

Queue Variants and Performance

Approach Time complexity Cache behavior When to use
collections.deque FIFO or double-ended queue O(1) best, average and worst per end operation; no shifting Fixed-size linked blocks with good locality within each block FIFO, double-ended queues and BFS
Fixed circular array O(1) best, average and worst; one slot access and one index update Excellent contiguous locality Bounded, high-throughput queues
Linked-node queue O(1) best, average and worst per operation; one link update Pointer chasing and scattered nodes Custom node-based designs
heapq priority queue Push: O(1) best, O(1) average for random insertion and O(log n) worst; pop: O(log n) best, average and worst because heap levels are traversed Contiguous list, but sifting is less local Priority scheduling
queue.Queue O(1) best, average and worst internal work per put or get; a call may block Lock and condition-variable overhead Thread-safe producer-consumer systems

Variants and Typical Uses

  • Two-stack queue: Enqueue is O(1), while dequeue is O(1) amortized because each element moves between the stacks at most once. Extra space is O(m).

  • Monotonic deque for sliding-window maximum: Candidate indices are kept in decreasing value order. Expired indices leave the front, while a new value removes dominated indices from the back. Each index is pushed and popped once, giving O(n) total time and O(k) extra space for a window of size k.

  • BFS and rotting oranges: BFS uses a FIFO queue and takes O(V + E) time with O(V) queue space. Rotting oranges is multi-source BFS over a grid and takes O(rows × columns) time and queue space.

  • Scheduling, rate limiting and buffering: FIFO operations are O(1) per enqueue or dequeue. Priority scheduling uses a heap when urgent tasks must overtake ordinary ones; rate limiters and buffers smooth bursts and bound stored work.

Space Complexity

Let m be the queue size, c its fixed capacity, n the heap size, k the window size and V the number of graph vertices.

  • FIFO, deque, linked-node and two-stack queues: O(m) extra space.

  • Circular buffer: O© space regardless of current occupancy.

  • Priority queue: O(n) heap storage.

  • Monotonic deque: O(k) extra space.

  • BFS: O(V) queue space.

  • Recursion stack: O(1) for these iterative operations.

These figures exclude the original input or graph; include the input size instead if counting total memory.

Worked Example

Consider a circular buffer with capacity four and a separate count:

Operation Buffer state Head Tail Count
Initial [None, None, None, None] 0 0 0
Enqueue A ["A", None, None, None] 0 1 1
Enqueue B ["A", "B", None, None] 0 2 2
Dequeue returns "A" ["A", "B", None, None] 1 2 1
Enqueue E ["A", "B", "E", None] 1 3 2
Enqueue F ["A", "B", "E", "F"] 1 0 3
Dequeue returns "B" ["A", "B", "E", "F"] 2 0 2
Enqueue G ["G", "B", "E", "F"] 2 1 3

Indices wrap modulo capacity. Each operation accesses one element slot and updates an index, so it remains O(1); the count distinguishes empty from full.

Common Pitfalls

  • Using list.pop(0): This shifts the remaining elements and costs O(n). Use collections.deque or a circular buffer.

  • Ignoring capacity: Define an overflow policy and track fullness with a count or by leaving one slot unused.

  • Adding unnecessary locks: Use queue.Queue for thread-safe producer-consumer systems, not an ordinary single-threaded FIFO.

  • Overlooking payloads: Empty and one-element queues, duplicates and negative values are valid; an already sorted input still follows FIFO order.

  • Forgetting BFS safeguards: Use a visited set for cycles and start separately for disconnected components.

  • Measuring poorly: Warm up the process, repeat measurements and control for allocation and garbage collection before drawing conclusions.

46

How do you design an O(1) rolling-average queue?

A rolling-average queue maintains a FIFO window of the most recent values and stores their running sum, allowing each enqueue, dequeue, and average query to complete in O(1) time. The implementation below uses a fixed-size collections.deque window.

Read full answer

Applies toPython 3.12

How It Works

The queue keeps three pieces of state:

  • _values: a collections.deque containing the current window.

  • _sum: the sum of all values currently in the window.

  • _max_size: the maximum number of values retained.

When a value is enqueued:

  1. If the window is full, remove the oldest value with popleft() and subtract it from _sum.

  2. Append the new value and add it to _sum.

The current average is then:

_sum / len(_values)

Because the sum is maintained incrementally, the query does not need to scan the queue.

Complexity

Operation Best case Average case Worst case Reason
enqueue O(1) O(1) O(1) Deque endpoint operations and arithmetic are constant-time
dequeue O(1) O(1) O(1) popleft() removes the oldest value directly
average O(1) O(1) O(1) Uses the stored sum and queue length
Storage O(k) O(k) O(k) Stores up to k values

Here, k is the window size. Auxiliary space beyond the stored queue is O(1), and there is no recursion stack. The input values themselves are counted in the O(k) total space usage.

Compared with recomputing the sum on every query:

Approach enqueue dequeue Average query Space
Recalculate by scanning O(1) O(1) O(n) O(n)
Maintain a running sum O(1) O(1) O(1) O(n)

Queue Variants and Use Cases

  • collections.deque is the appropriate Python structure for a FIFO queue because append() and popleft() are O(1). Do not use list.pop(0) in a loop because it is O(n).

  • A fixed-array circular queue can implement the same design using head and tail indices modulo the capacity. It is useful when a preallocated buffer is preferred.

  • Use queue.Queue instead of collections.deque for thread-safe producer-consumer communication.

  • Use heapq for a priority queue; it does not preserve FIFO ordering.

  • A monotonic deque is appropriate for sliding-window maximum problems, where each element is pushed and removed at most once, but it is unnecessary for a rolling average.

Walkthrough

For a window size of 3:

  1. Enqueue 10: window is [10], sum is 10, average is 10.0.

  2. Enqueue 20: window is [10, 20], sum is 30, average is 15.0.

  3. Enqueue 30: window is [10, 20, 30], sum is 60, average is 20.0.

  4. Enqueue 40: 10 is evicted, window becomes [20, 30, 40], sum becomes 90, average is 30.0.

Code Example

from collections import deque


class RollingAverageQueue:
    """Maintain the average of the most recent values in a fixed-size queue."""

    def __init__(self, max_size: int) -> None:
        if max_size <= 0:
            raise ValueError("max_size must be positive")

        self._max_size = max_size
        self._values: deque[int | float] = deque()
        self._sum: int | float = 0

    def enqueue(self, value: int | float) -> None:
        """Add a value, evicting the oldest value if the window is full."""
        if len(self._values) == self._max_size:
            oldest_value = self._values.popleft()
            self._sum -= oldest_value

        self._values.append(value)
        self._sum += value

    def dequeue(self) -> int | float:
        """Remove and return the oldest value."""
        if not self._values:
            raise IndexError("dequeue from an empty queue")

        value = self._values.popleft()
        self._sum -= value
        return value

    def average(self) -> float:
        """Return the average of the current window."""
        if not self._values:
            raise ValueError("average requires a non-empty queue")

        return self._sum / len(self._values)

    def __len__(self) -> int:
        return len(self._values)


if __name__ == "__main__":
    queue = RollingAverageQueue(max_size=3)

    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    print(queue.average())  # 20.0

    queue.enqueue(40)
    print(queue.average())  # 30.0

    queue.dequeue()
    print(queue.average())  # 25.0

Common Pitfalls

  • Calling average() on an empty queue is invalid; the example raises ValueError.

  • The implementation handles one element, duplicate values, negative numbers, and values whose sum is zero without special cases.

  • Floating-point running sums can accumulate small precision errors. For precision-critical applications, periodically recompute the sum from the deque.

  • Avoid list.pop(0) and list.insert(0, value) for queue-like behavior because they require shifting elements.

  • The current average depends only on the values currently retained, but insertion order determines which value is evicted and can affect later averages. Sorted input requires no special handling, but it can produce different later averages from an unsorted sequence with the same values.

  • Graph-specific edge cases such as disconnected graphs and cycles do not apply here.

47

How do you implement a priority queue that minimizes total dequeue waiting time?

Shortest-job-first (SJF) minimizes total waiting time when each job has a known processing time and jobs can be reordered. Implement it as a priority queue using heapq, ordering jobs by processing time and using insertion order to break ties.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Each queued job has a non-negative service time, representing how long it takes to process the job.

  • The waiting time of a job is the total processing time of all jobs dequeued before it.

  • The priority queue stores (service_time, insertion_index) tuples.

  • heapq always removes the job with the smallest service time.

  • The insertion index preserves FIFO order when jobs have equal service times.

This is optimal when all jobs are available at time zero, there are no deadlines, preemption is not required, and reordering is allowed. If FIFO order is a hard constraint, the order cannot be optimized; use collections.deque with append and popleft instead.

The greedy choice is safe by an exchange argument: if a longer job precedes a shorter job, swapping them reduces the total waiting time. Therefore, processing jobs in nondecreasing service time produces an optimal schedule.

Example Walkthrough

For service times [4, 1, 2, 1]:

Dequeue order Service time Waiting time Elapsed time afterward
Index 1 1 0 1
Index 3 1 1 2
Index 2 2 2 4
Index 0 4 4 8

The total waiting time is 0 + 1 + 2 + 4 = 7.

Complexity

Approach Time Space When to use
Heap-based SJF Best, average and worst: O(n log n) O(n) auxiliary space; input excluded Reordering is allowed
Brute-force permutations Best, average and worst: O(n · n!) O(n) auxiliary space Small inputs or verification
Strict FIFO using deque O(n) total processing time O(n) queue storage; O(1) extra space FIFO ordering is mandatory

For the heap approach, heapify takes O(n) and each of the n removals takes O(log n), giving O(n log n) total time. The heap and result list require O(n) auxiliary space, not counting the input.

Code Example

from collections.abc import Sequence
from heapq import heapify, heappop


def minimize_total_wait_time(
    service_times: Sequence[int],
) -> tuple[list[int], int]:
    """Return the SJF dequeue order and total waiting time."""
    if any(service_time < 0 for service_time in service_times):
        raise ValueError("Service times must be non-negative")

    heap: list[tuple[int, int]] = [
        (service_time, index)
        for index, service_time in enumerate(service_times)
    ]
    heapify(heap)

    elapsed_time = 0
    total_wait_time = 0
    dequeue_order: list[int] = []

    while heap:
        service_time, index = heappop(heap)
        dequeue_order.append(index)

        total_wait_time += elapsed_time
        elapsed_time += service_time

    return dequeue_order, total_wait_time


print(minimize_total_wait_time([4, 1, 2, 1]))
# ([1, 3, 2, 0], 7)

Common Pitfalls

  • Using FIFO for an optimizable queue: FIFO cannot reduce waiting time by reordering.

  • Ignoring arrival times or deadlines: Plain SJF is not guaranteed to minimize total waiting time when jobs arrive dynamically or have deadline constraints.

  • Breaking equal-time ordering incorrectly: Always include an insertion index so ties remain stable and fair.

  • Using list.pop(0): It is O(n); use collections.deque.popleft() for an ordinary FIFO queue.

  • Rejecting zero-duration jobs: Zero is valid; only negative service times are invalid.

  • Confusing waiting time and completion time: Waiting time excludes the current job’s own service time.

  • Using queue.Queue unnecessarily: It is intended for thread-safe producer-consumer communication; heapq is appropriate for this scheduling priority queue.

48

How do you implement an immutable queue functionally?

An immutable queue preserves every existing queue state: operations such as enqueue and dequeue return a new queue instead of modifying the original. A functional implementation can use two persistent stacks, giving constant-time enqueue and amortized constant-time dequeue.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The queue maintains two stack-like structures:

  • Front stack: its top contains the oldest element and is used for dequeue and peek.

  • Back stack: new elements are pushed here in constant time.

  • When the front stack is empty, the back stack is transferred to it in reverse order. This puts the oldest element on top.

Each stack is represented by immutable linked nodes. Enqueue creates one new node; dequeue creates a new queue while sharing unaffected nodes. No existing node or queue is changed.

For example, after enqueueing A and B:

  1. Back stack, top to bottom: B, A

  2. Front stack is empty, so the back stack is transferred.

  3. Front stack, top to bottom: A, B

  4. dequeue() removes A, leaving B as the next element.

Complexity

Operation Best time Amortized time Worst time Additional space
enqueue O(1) O(1) O(1) O(1)
dequeue O(1) O(1) O(n) O(n) during transfer
peek O(1) O(1) O(n) O(n) during transfer
len O(1) O(1) O(1) O(1)
  • enqueue is constant time because it creates one persistent node.

  • A dequeue that transfers the back stack costs O(n), but each element is transferred at most once along an operation sequence. Therefore, dequeue is O(1) amortized.

  • Total space for one live queue is O(n), including the stored elements. Retaining historical versions may increase aggregate memory, although unaffected nodes are shared.

  • The implementation is iterative, so it uses no recursion stack.

Queue Variants

Variant Typical use Key characteristic
Simple FIFO queue BFS, buffering deque.append and deque.popleft are O(1)
Circular queue Fixed-capacity buffers Uses head and tail indices modulo capacity
Double-ended queue Sliding windows, work queues Supports O(1) insertion and removal at both ends
Priority queue Scheduling by urgency heapq provides O(log n) insertion and removal
Immutable queue Functional, persistent applications Old versions remain unchanged

Code Example

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass(frozen=True, slots=True)
class _Stack(Generic[T]):
    """An immutable stack node; the node is the stack's top."""

    value: T
    next: _Stack[T] | None = None


@dataclass(frozen=True, slots=True)
class ImmutableQueue(Generic[T]):
    """A persistent FIFO queue implemented with two immutable stacks."""

    _front: _Stack[T] | None
    _back: _Stack[T] | None
    _size: int

    @classmethod
    def empty(cls) -> ImmutableQueue[T]:
        """Create an empty immutable queue."""
        return cls(_front=None, _back=None, _size=0)

    def __len__(self) -> int:
        """Return the number of queued elements."""
        return self._size

    def enqueue(self, value: T) -> ImmutableQueue[T]:
        """Return a new queue with value added to the rear."""
        return ImmutableQueue(
            _front=self._front,
            _back=_Stack(value=value, next=self._back),
            _size=self._size + 1,
        )

    def dequeue(self) -> ImmutableQueue[T]:
        """Return a new queue with the oldest element removed."""
        front = self._front
        back = self._back

        if front is None:
            # Reverse the back stack so its oldest element becomes the top.
            while back is not None:
                front = _Stack(value=back.value, next=front)
                back = back.next

        if front is None:
            raise IndexError("dequeue from an empty queue")

        return ImmutableQueue(
            _front=front.next,
            _back=back,
            _size=self._size - 1,
        )

    def peek(self) -> T:
        """Return the oldest element without removing it."""
        front = self._front
        back = self._back

        if front is None:
            while back is not None:
                front = _Stack(value=back.value, next=front)
                back = back.next

        if front is None:
            raise IndexError("peek from an empty queue")

        return front.value


if __name__ == "__main__":
    original = ImmutableQueue[str].empty()
    populated = original.enqueue("A").enqueue("B")
    remaining = populated.dequeue()

    print(populated.peek(), len(populated), remaining.peek())  # A 2 B

Common Pitfalls

  • Mutating shared state: Reassigning a stack or modifying its nodes would break immutability; every operation must return a new queue.

  • Reversing the wrong stack: The back stack has the newest element on top, so it must be reversed when transferred.

  • Using list.pop(0): Removing the first list element is O(n); use linked stacks or collections.deque.popleft.

  • Empty-queue behavior: dequeue and peek raise IndexError when no element exists.

  • Ordering guarantees: Duplicate and negative values require no special handling; FIFO order is preserved.

  • Thread safety: This data structure is not a replacement for queue.Queue, which is designed for thread-safe producer-consumer communication.

49

What is a distributed queue, and how does it support distributed systems?

A distributed queue is a FIFO data structure whose storage and processing are shared across multiple machines through a network service, message broker, or coordination system. It enables independent producers and consumers to exchange work reliably, distribute load, and tolerate failures.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Model

A distributed queue usually consists of:

  • Producers: Submit messages or tasks to the queue.

  • Broker or coordinator: Stores messages, tracks acknowledgements, and delivers them to consumers.

  • Consumers: Retrieve and process messages, then acknowledge successful completion.

  • Partitions or shards: Divide the queue for capacity and throughput; ordering is normally guaranteed only within a partition.

For example, an order service can publish an OrderCreated event. Inventory, billing, and notification services consume that event independently. If billing is temporarily unavailable, the event remains available for later processing instead of being lost.

The logical operation remains FIFO, but concurrency and distributed failures make ordering, durability, and delivery guarantees more important than in an in-memory queue.

Delivery and Consistency

  • At-least-once delivery: A message may be delivered more than once if a consumer crashes before acknowledging it. Consumers should therefore be idempotent.

  • At-most-once delivery: A message is not redelivered, but it may be lost when a consumer fails.

  • Exactly-once processing: Achieving the equivalent effect exactly once usually requires transactional coordination, idempotency, deduplication, or transactional messaging. It is more complex than ordinary queue delivery.

  • Visibility timeout: The broker temporarily hides an in-flight message. If the consumer does not acknowledge it before the timeout, the broker can redeliver it.

  • Acknowledgements: A consumer confirms that processing completed. The broker removes or advances past the message only according to the configured delivery policy.

  • Dead-letter queue: Messages that repeatedly fail can be moved to a separate queue for inspection and replay.

A distributed queue may also provide ordered consumption, delayed delivery, consumer groups, and backpressure when consumers cannot keep up.

Queue Variants

Variant Ordering or behavior Typical use
Simple FIFO queue First in, first out General background processing
Circular queue Fixed capacity with head and tail indices using modulo arithmetic Bounded buffers and embedded systems
Double-ended queue Supports insertion and removal at both ends Sliding-window algorithms and scheduling
Priority queue Removes elements by priority rather than arrival order Urgent tasks and event scheduling
Distributed work queue FIFO across workers, usually through a broker Task distribution across services

In Python, collections.deque provides efficient FIFO and double-ended operations. heapq implements a min-heap for priority queues; values can be negated for a max-heap. queue.Queue is appropriate for thread-safe producer-consumer code inside one process, but it is not a distributed queue.

Complexity

Distributed performance depends on the broker, network, partitioning, persistence, and failure handling:

  • Best case: Broker-local enqueue and dequeue operations are O(1) when no synchronization or disk write is required.

  • Average case: A client operation takes O(1) broker round trips under normal operation, excluding message-processing time and payload transfer.

  • Worst case: With r retries, a bounded timeout, and backoff, latency can be O(r + b), where b is the total backoff duration. Without bounded retries, there is no finite upper bound.

  • End-to-end processing: O(p + h), where p is payload transfer and serialization cost and h is consumer handler time.

  • Space: Broker storage is O© for c bounded-size records, or O(B) bytes for total stored data. A client normally uses O(1) additional space, excluding the input payload and any local result.

These figures exclude replication overhead. Durable replicated queues may require multiple network or disk operations per acknowledgement, affecting both latency and storage amplification.

Example Workflow

Consider a distributed queue for image processing:

  1. A producer uploads an image and enqueues its job ID and storage location.

  2. The broker stores the job in partition 2.

  3. Consumer C1 receives the job and begins processing it.

  4. C1 crashes before acknowledging completion.

  5. The visibility timeout expires, and the broker redelivers the job.

  6. Consumer C2 processes it and acknowledges success.

  7. The broker removes the job from the available queue.

Partitions provide parallelism, while ordering is normally preserved only among jobs assigned to the same partition.

Common Pitfalls

  • Assuming global FIFO when the broker partitions messages.

  • Treating at-least-once delivery as exactly-once delivery.

  • Building non-idempotent consumers that duplicate charges, emails, or records.

  • Using a large visibility timeout that delays recovery after a consumer crash.

  • Using a short timeout that redelivers messages while processing is still active.

  • Ignoring poison messages and failing to configure retries or a dead-letter queue.

  • Failing to monitor backlog age, consumer lag, redelivery rate, and partition imbalance.

  • Forgetting that retries and network partitions affect latency guarantees, not just the underlying queue’s nominal O(1) operations.

50

How do you design a fault-tolerant queuing system with crash recovery?

A fault-tolerant queuing system should use at-least-once message delivery backed by durable, replicated storage. The broker survives process or node crashes, while consumers acknowledge messages only after processing them successfully.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Reliability Model

  • Durable broker: Store messages in a replicated log or database before acknowledging them to producers.

  • Replication: Use leader-follower replication and a write quorum so an acknowledged message survives the failure of a broker node.

  • Manual acknowledgements: A consumer acknowledges a message only after its business transaction succeeds.

  • Redelivery: An unacknowledged message becomes visible again after a visibility timeout or consumer lease expires.

  • Idempotent consumers: Store a processed message ID so redelivery does not repeat side effects.

  • Dead-letter queue: Move repeatedly failing messages to a separate queue for investigation instead of blocking the main queue.

This provides at-least-once rather than absolute exactly-once delivery. Effectively-once processing is achieved by combining redelivery with consumer-side idempotency.

End-to-End Flow

  1. The producer writes its business data and an outbox record in one database transaction.

  2. An outbox relay publishes the message using a stable message ID.

  3. The broker synchronizes the message to a quorum of replicas before acknowledging it.

  4. The broker delivers the message and gives it a limited processing lease.

  5. The consumer performs its work and records the message ID in an idempotency table.

  6. The consumer acknowledges the message only after both operations succeed.

  7. If the consumer crashes before acknowledgement, the broker redelivers the message after the lease expires.

For FIFO ordering, use partition keys: messages with the same key remain ordered within one partition, but global ordering is usually too expensive to guarantee.

Failure Handling

Failure System behavior
Producer crashes before publishing The transactional outbox recovers the unsent message
Broker process crashes Another broker takes over after leader election
Broker node fails Replicas retain the committed message
Consumer crashes The unacknowledged message is redelivered
Message causes repeated failure Retry with backoff, then move it to a dead-letter queue
Network partition Operations time out and are retried using the same message ID

FIFO, priority, and dead-letter queues can be supported by the same architecture. In-memory structures such as collections.deque or a circular array are fast but do not provide crash durability. queue.Queue is appropriate only for thread-safe, single-process producer-consumer communication.

Complexity

Assume message payload size is p, replication factor is R, retained payload size is B, and there are M messages, W in-flight deliveries, and D retained idempotency keys.

Operation Time Space
Broker enqueue O(p + R) for serialization and replication O(p) transient memory
Message delivery O(p) O(1) transient client memory
Consumer processing O(f(p)), where f is the business operation Depends on the side effect
Retained system state — O(B + M + W + D)

The producer’s original input is not counted separately, but retained message copies and idempotency records are. During failures, additional time is spent on retries, leases, leader election, and quorum coordination.

Code Example

This runnable SQLite example demonstrates durable persistence, leases, and redelivery after a simulated worker crash. It illustrates the acknowledgement semantics only; a production system should use a replicated broker to survive node or disk failure.

import sqlite3
import tempfile
import time
from contextlib import closing
from pathlib import Path


def durable_queue_demo() -> None:
    """Demonstrate durable enqueue, crash recovery, redelivery, and acknowledgement."""
    with tempfile.TemporaryDirectory() as directory:
        database = str(Path(directory) / "queue.db")

        with closing(sqlite3.connect(database, isolation_level=None)) as connection:
            connection.row_factory = sqlite3.Row
            connection.execute("PRAGMA journal_mode = WAL")
            connection.execute("PRAGMA synchronous = FULL")
            connection.execute(
                """
                CREATE TABLE messages (
                    id INTEGER PRIMARY KEY,
                    payload TEXT NOT NULL,
                    status TEXT NOT NULL,
                    attempts INTEGER NOT NULL,
                    lease_until REAL NOT NULL
                )
                """
            )
            connection.execute(
                "CREATE INDEX messages_pending "
                "ON messages(id) WHERE status = 'pending'"
            )
            connection.execute(
                "CREATE INDEX messages_expired "
                "ON messages(lease_until, id) WHERE status = 'processing'"
            )
            connection.execute(
                "INSERT INTO messages "
                "(payload, status, attempts, lease_until) "
                "VALUES (CAST(? AS TEXT), 'pending', 0, 0.0)",
                ("transfer 100",),
            )
            print("enqueued id=1")

        def claim_one(
            connection: sqlite3.Connection,
            now: float,
            lease_seconds: float,
        ) -> tuple[int, int] | None:
            try:
                connection.execute("BEGIN IMMEDIATE")
                row = connection.execute(
                    "SELECT id FROM messages "
                    "WHERE status = 'pending' ORDER BY id LIMIT 1"
                ).fetchone()
                if row is None:
                    row = connection.execute(
                        "SELECT id FROM messages "
                        "WHERE status = 'processing' "
                        "AND lease_until <= CAST(? AS REAL) "
                        "ORDER BY lease_until, id LIMIT 1",
                        (now,),
                    ).fetchone()

                if row is None:
                    connection.commit()
                    return None

                message_id = int(row["id"])
                connection.execute(
                    "UPDATE messages SET status = 'processing', "
                    "attempts = attempts + 1, lease_until = CAST(? AS REAL) "
                    "WHERE id = CAST(? AS INTEGER)",
                    (now + lease_seconds, message_id),
                )
                connection.commit()
                attempts = connection.execute(
                    "SELECT attempts FROM messages WHERE id = CAST(? AS INTEGER)",
                    (message_id,),
                ).fetchone()["attempts"]
                return message_id, int(attempts)
            except Exception:
                connection.rollback()
                raise

        with closing(sqlite3.connect(database, isolation_level=None)) as connection:
            connection.row_factory = sqlite3.Row
            first_claim = claim_one(connection, time.time(), 0.05)
            print(f"first claim={first_claim}")
            # Closing without acknowledging simulates a worker crash.

        time.sleep(0.06)

        with closing(sqlite3.connect(database, isolation_level=None)) as connection:
            connection.row_factory = sqlite3.Row
            reclaimed = claim_one(connection, time.time(), 0.05)
            print(f"reclaimed={reclaimed}")

            connection.execute("BEGIN IMMEDIATE")
            connection.execute(
                "DELETE FROM messages WHERE id = CAST(? AS INTEGER)",
                (reclaimed[0],),
            )
            connection.commit()
            print(f"acknowledged id={reclaimed[0]}")


durable_queue_demo()
# Expected output:
# enqueued id=1
# first claim=(1, 1)
# reclaimed=(1, 2)
# acknowledged id=1

Common Pitfalls

  • Acknowledging a message before completing its business transaction causes message loss.

  • Publishing before durably recording the message creates a producer-side failure window.

  • Retrying without a stable message ID can create duplicate business operations.

  • Using an unbounded retry loop can cause a poison message to block a partition.

  • Assuming FIFO ordering across partitions or consumers is incorrect.

  • Treating broker replication as a substitute for consumer idempotency.

  • Using list.pop(0) for an in-memory queue causes O(n) removal; use collections.deque with append and popleft.

51

What distributed application scenario uses a queue for load leveling?

A load-leveling queue absorbs bursts of incoming work between producers and consumers that process requests at a steadier rate. In a distributed application, it decouples request arrival rate from service capacity, preventing short traffic spikes from overwhelming downstream services.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Load-Leveling Scenario

Consider an image-processing service:

  • Requests arrive in bursts of 1,000 images.

  • A worker pool can process only 100 images per second.

  • A queue stores the extra requests while workers process them at a controlled rate.

  • Producers continue accepting work until the queue reaches its configured capacity.

Without the queue, each incoming request might immediately consume a worker or overload the processing service. With the queue, the burst is buffered and service remains stable.

In production, this pattern commonly uses distributed brokers such as RabbitMQ or Amazon SQS. Apache Kafka can also provide the pattern through topics and consumer groups.

How It Works

  1. Producers publish requests to a queue.

  2. Consumers or workers retrieve requests independently of the arrival rate.

  3. The queue holds pending work when consumers are slower than producers.

  4. Workers process requests at the service’s sustainable capacity.

  5. Acknowledgment occurs only after successful processing or when the message is deliberately routed to a failure-handling mechanism.

For a smaller burst of six requests with two workers that each take 20 milliseconds per request, two requests begin processing while four wait. The workers complete three rounds in approximately 60 milliseconds, spreading the burst instead of concentrating all work on them at once.

Load leveling differs from load balancing:

Technique Primary purpose
Load leveling Buffers uneven arrival rates and smooths bursts
Load balancing Distributes concurrent work across available resources

Queue Variants

  • Simple FIFO queue: Preserves arrival order and is the usual choice for general load leveling.

  • Circular queue: A fixed-capacity FIFO ring buffer implemented with an array and head/tail indices advanced modulo capacity. It is useful for bounded local buffering but does not provide distributed durability by itself.

  • Double-ended queue: Supports insertion and removal at both ends. It can behave as a FIFO queue, but its additional operations are unnecessary for ordinary load leveling.

  • Priority queue: Orders work by priority rather than arrival time. Python’s heapq implements a min-heap; this can violate FIFO fairness and is better for explicitly prioritized work.

  • Monotonic deque: Supports sliding-window maximum calculations by pushing each element once and popping each element at most once from each end, giving O(n) total time. It is not normally the queue used for distributed load leveling.

  • Thread-safe local queue: queue.Queue is appropriate for thread-based producer-consumer code within one process. Processes on the same host can share a multiprocessing.Queue; producers and consumers on different hosts need a distributed broker.

Complexity

For the local in-memory FIFO operations modeled by collections.deque:

Operation Best Average Worst Reason
Enqueue O(1) O(1) O(1) A deque is a linked list of fixed-size blocks, so appending never copies existing elements
Dequeue O(1) O(1) O(1) Removing the front element does not shift the remaining elements
Perform all queue operations O(n) O(n) O(n) Every request is enqueued and dequeued once

If each request requires c units of work, total processing work is O(nc). With w workers and balanced work, ideal wall-clock time is approximately O(ceil(n/w) × c), although contention and uneven task durations can reduce the benefit of parallelism.

The local queue uses O(q) space for up to q fixed-size pending messages, excluding the original input; variable-sized messages instead require space proportional to their total pending size. Worker execution uses O(w) additional space. There is no recursion stack. A distributed broker adds network and broker-specific overhead, so end-to-end latency does not have a universal O(1) guarantee.

Best Practices

  • Bound the queue: An unbounded queue can exhaust memory during sustained overload.

  • Apply backpressure: When the queue is full, reject, delay, or redirect new requests.

  • Set processing limits: Consumer concurrency should match downstream capacity and database or API limits.

  • Use durable delivery: For important work, persist messages and acknowledge them only after successful processing.

  • Make consumers idempotent: Many brokers provide at-least-once delivery, so a request may be processed more than once.

  • Monitor backlog age and depth: These metrics reveal whether workers can keep up with incoming traffic.

Common Pitfalls

  • A queue buffers a temporary burst but cannot fix a sustained arrival rate above the service rate.

  • An unbounded queue may avoid immediate overload while eventually causing an outage.

  • FIFO ordering does not guarantee fair scheduling across different request types.

  • Adding consumers to one queue may improve throughput but can overload a shared downstream dependency.

  • Retries can create a feedback loop; use bounded retries, exponential backoff, and a dead-letter queue.

52

How do you simulate a grocery store queue with multiple cashiers?

A queue follows FIFO ordering: customers join the end of a line and are served from the front. In a multi-cashier simulation, maintain one FIFO queue per cashier and choose how arriving customers are assigned to those lines.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Simulation Works

This simulation uses an event-driven approach rather than advancing one simulated minute at a time:

  • Each cashier has a deque containing waiting customers.

  • The customer currently being served is tracked separately.

  • Before processing an arrival, service completions at or before that time are handled.

  • Arriving customers join the line with the fewest assigned customers, including the customer currently being served.

  • Ties go to the lowest cashier ID, making the simulation deterministic.

  • Customers arriving simultaneously are processed by customer_id order.

The simulation assumes any cashier can serve any customer and that service times are known in advance.

Queue Variants

Variant Appropriate structure When to use it
Simple FIFO line collections.deque Standard checkout or service lines
Circular queue Fixed-size array with head, tail = (head + size) % capacity, and size Bounded-capacity simulations
Double-ended queue collections.deque Operations are required at both ends
Priority queue heapq min-heap; negate numeric priority keys for max-heap behavior Express lanes, VIP customers, or urgent orders
Thread-safe queue queue.Queue Producer-consumer communication between threads

The main simulation uses deque because append() and popleft() are amortized O(1).

Complexity

For n customers and c cashiers:

  • Best case: O(n + nc), when customers are already ordered by (arrival_time, customer_id) and hash operations do not collide.

  • Average case: O(n log n + nc), assuming average O(1) set and dict operations. Sorting costs O(n log n), while each arrival scans the cashiers to find the shortest line.

  • Worst case: O(n² + nc), because pathological hash collisions can make each set or dict operation O(n).

  • Each customer starts and completes service once, so total service transitions are O(n).

  • Auxiliary space: O(n + c), including receipts, the sorted customer list, and cashier queues. The caller-owned input is another O(n) if counted. Recursion stack space is O(1).

Example Walkthrough

With two cashiers and customers C1, C2, and C3 arriving at time 0:

  1. C1 starts at cashier 1, and C2 starts at cashier 2.

  2. Both lines have one assigned customer, so C3 joins cashier 1.

  3. When C1 finishes, C3 begins service because it is the next customer waiting at that cashier.

Code Example

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass, field


@dataclass(frozen=True)
class Customer:
    customer_id: str
    arrival_time: int
    service_time: int


@dataclass(frozen=True)
class CustomerReceipt:
    customer_id: str
    cashier_id: int
    arrival_time: int
    service_start_time: int
    completion_time: int


@dataclass
class Cashier:
    cashier_id: int
    line: deque[Customer] = field(default_factory=deque)
    active: Customer | None = None
    busy_until: int | None = None


def simulate_grocery_queue(
    customers: Sequence[Customer],
    cashier_count: int = 2,
) -> list[CustomerReceipt]:
    """Simulate FIFO checkout lines and return receipts in input order."""
    if cashier_count <= 0:
        raise ValueError("cashier_count must be positive")

    seen_ids: set[str] = set()
    for customer in customers:
        if customer.customer_id in seen_ids:
            raise ValueError(f"Duplicate customer ID: {customer.customer_id}")
        seen_ids.add(customer.customer_id)

        if customer.arrival_time < 0:
            raise ValueError("arrival_time cannot be negative")
        if customer.service_time <= 0:
            raise ValueError("service_time must be positive")

    if not customers:
        return []

    cashiers = [Cashier(cashier_id=index + 1) for index in range(cashier_count)]
    receipts: dict[str, CustomerReceipt] = {}

    def start_service(
        customer: Customer,
        cashier: Cashier,
        start_time: int,
    ) -> None:
        completion_time = start_time + customer.service_time
        receipts[customer.customer_id] = CustomerReceipt(
            customer_id=customer.customer_id,
            cashier_id=cashier.cashier_id,
            arrival_time=customer.arrival_time,
            service_start_time=start_time,
            completion_time=completion_time,
        )
        cashier.active = customer
        cashier.busy_until = completion_time

    def process_completions(until: float) -> None:
        for cashier in cashiers:
            while (
                cashier.busy_until is not None
                and cashier.busy_until <= until
            ):
                completion_time = cashier.busy_until
                assert cashier.active is not None

                cashier.active = None
                cashier.busy_until = None

                if cashier.line:
                    next_customer = cashier.line.popleft()
                    start_service(next_customer, cashier, completion_time)

    ordered_customers = sorted(
        customers,
        key=lambda customer: (customer.arrival_time, customer.customer_id),
    )

    for customer in ordered_customers:
        process_completions(customer.arrival_time)

        chosen_cashier = min(
            cashiers,
            key=lambda cashier: (
                len(cashier.line) + (1 if cashier.active is not None else 0),
                cashier.cashier_id,
            ),
        )

        if chosen_cashier.active is None:
            start_service(customer, chosen_cashier, customer.arrival_time)
        else:
            chosen_cashier.line.append(customer)

    process_completions(float("inf"))
    return [receipts[customer.customer_id] for customer in customers]


customers = [
    Customer("C1", arrival_time=0, service_time=3),
    Customer("C2", arrival_time=0, service_time=2),
    Customer("C3", arrival_time=0, service_time=1),
    Customer("C4", arrival_time=1, service_time=1),
]

receipts = simulate_grocery_queue(customers, cashier_count=2)
for receipt in receipts:
    print(receipt)

# Expected output:
# CustomerReceipt(customer_id='C1', cashier_id=1, arrival_time=0, service_start_time=0, completion_time=3)
# CustomerReceipt(customer_id='C2', cashier_id=2, arrival_time=0, service_start_time=0, completion_time=2)
# CustomerReceipt(customer_id='C3', cashier_id=1, arrival_time=0, service_start_time=3, completion_time=4)
# CustomerReceipt(customer_id='C4', cashier_id=2, arrival_time=1, service_start_time=2, completion_time=3)

Common Pitfalls

  • Using list.pop(0): Removing the first element is O(n); use deque.popleft().

  • Undefined timing: This implementation treats arrival time t and one unit of service as completion at t + 1.

  • Ignoring queue policy: State whether customers choose the shortest line, a dedicated line, or another policy.

  • Mutating the input: Sort a separate list rather than rearranging the caller’s data.

  • Unhandled edge cases: The function handles empty input and one customer; it rejects duplicate IDs, negative arrivals, nonpositive service times, and invalid cashier counts.

  • Using queue.Queue unnecessarily: It is intended for thread-safe producer-consumer communication, not this single-threaded simulation.

  • Confusing FIFO with priority ordering: Use heapq only for an explicit priority policy; it does not preserve shortest-line FIFO behavior.

  • Common follow-up: Interviewers may ask how to support priority customers with heapq or implement the store’s fixed-capacity lines with a circular queue.

53

How do you implement a queue that finds the kth-last element?

A FIFO queue can use collections.deque to append at the rear and remove from the front in O(1) time. To find the kth-last element, temporarily rotate the deque by the smaller of k positions and n - k positions, read the front, and restore the original order.

Read full answer

Applies toPython 3.12

How It Works

  • Enqueue: call deque.append(item) to insert at the rear.

  • Dequeue: call deque.popleft() to remove the oldest item.

  • Kth-last lookup: use 1-based indexing, so k = 1 returns the tail and k = 2 returns the second-last element.

  • Restoration: rotate back in a finally block so the queue retains its original order.

For [10, 20, 30, 40] with k = 2:

  1. Rotate right by two positions: [30, 40, 10, 20].

  2. Read the front element, 30.

  3. Rotate left by two positions to restore [10, 20, 30, 40].

Queue Variants

Variant Core behavior Typical use
Simple FIFO queue deque.append() and deque.popleft() Task processing
Circular queue Fixed array with modulo-based indices Bounded buffers
Double-ended queue Insertion and removal at both ends Sliding windows and backtracking
Priority queue heapq orders by priority Scheduling and shortest paths

heapq implements a min-heap; negate numeric priorities when a max-heap is required. A monotonic deque is useful for sliding-window maxima: remove expired indices from the front and dominated indices from the back before inserting each new index. Each index is pushed and popped at most once, giving O(n) total time and O(window size) storage.

For the circular implementation below, _head is the logical front and _size is the number of stored elements. Therefore, the kth-last element is at (_head + _size - k) % capacity.

Code Example

from collections import deque
from typing import Generic, TypeVar, cast

T = TypeVar("T")


def kth_from_tail(queue: deque[T], k: int) -> T:
    """Return the kth element from the tail using 1-based indexing."""
    if k < 1:
        raise ValueError("k must be at least 1")

    size = len(queue)
    if k > size:
        raise IndexError("k exceeds the queue size")

    # Rotating right by k is equivalent to rotating left by size - k.
    rotation = k if k <= size // 2 else k - size
    queue.rotate(rotation)
    try:
        return queue[0]
    finally:
        queue.rotate(-rotation)


class CircularQueue(Generic[T]):
    """Fixed-capacity FIFO queue with O(1) kth-last lookup."""

    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self._slots: list[T | None] = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._size = 0

    def enqueue(self, item: T) -> None:
        if self._size == self._capacity:
            raise OverflowError("queue is full")
        index = (self._head + self._size) % self._capacity
        self._slots[index] = item
        self._size += 1

    def dequeue(self) -> T:
        if self._size == 0:
            raise IndexError("dequeue from an empty queue")
        index = self._head
        item = cast(T, self._slots[index])
        self._slots[index] = None
        self._head = (index + 1) % self._capacity
        self._size -= 1
        return item

    def kth_from_tail(self, k: int) -> T:
        if k < 1:
            raise ValueError("k must be at least 1")
        if k > self._size:
            raise IndexError("k exceeds the queue size")
        index = (self._head + self._size - k) % self._capacity
        return cast(T, self._slots[index])


queue: deque[int] = deque()
for item in (10, 20, 30, 40):
    queue.append(item)

print(kth_from_tail(queue, 2))  # Expected output: 30

circular = CircularQueue[int](4)
for item in (10, 20, 30, 40):
    circular.enqueue(item)

print(circular.kth_from_tail(2))  # Expected output: 30

Complexity

Operation Best Average Worst Auxiliary space Reason
deque.append() O(1) O(1) O(1) O(1) Adds to the last block; a deque never copies existing elements to grow
deque.popleft() O(1) O(1) O(1) O(1) Removes the front block directly
kth_from_tail() O(1) O(n) for uniformly distributed k O(n) O(1) Exact lookup time is O(min(k, n-k) + 1)
Circular-queue operations O(1) O(1) O(1) O(1) Uses direct indices and modulo arithmetic

There is no recursion stack. Auxiliary space excludes the queue’s stored elements; data storage is O(n) for a deque and O(capacity) for the circular queue.

Common Pitfalls

  • Off-by-one errors: Define k = 1 as the tail explicitly.

  • Boundary checks: An empty queue or k > len(queue) raises IndexError; k < 1 raises ValueError.

  • One-element queue: k = 1 returns that element, while larger values are invalid.

  • Duplicate or negative values: They are valid elements and need no special handling.

  • Wrong removal operation: Never use list.pop(0) for FIFO dequeue because it shifts O(n) elements.

  • Temporary mutation: Restore the deque after rotation, and do not share one mutable deque between unsynchronized threads.

  • Thread safety: Use queue.Queue for thread-safe producer-consumer code.

  • Follow-up: A two-stack FIFO queue also provides amortized O(1) enqueue and dequeue, while a fixed circular queue provides O(1) kth-last access.

54

How can a queue provide the median of all enqueued items?

A running-median queue uses two heaps: a max-heap for the lower half of the values and a min-heap for the upper half. After each insertion, the heaps are rebalanced so their roots provide the current median in constant time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain two heaps:

  • Lower heap: a max-heap containing the smaller half of the values. In Python, heapq implements a min-heap, so values are negated.

  • Upper heap: a min-heap containing the larger half.

The following invariants must hold:

  1. Every value in the lower heap is less than or equal to every value in the upper heap.

  2. The lower heap contains either the same number of elements as the upper heap or exactly one more.

For an odd number of elements, the maximum of the lower heap is the median. For an even number, the median is the average of the maximum of the lower heap and the minimum of the upper heap.

A brute-force implementation could sort all values after every insertion, but that costs O(n log n) per insertion. The two-heap design supports the operation efficiently for streaming data.

Complexity

Operation Best case Average case Worst case Reason
enqueue O(1) O(1) O(log n) Heap insertion and possible rebalance are O(log n) worst case; average insertion depth is constant.
median O(1) O(1) O(1) Only the two heap roots are inspected.
n enqueues O(n) O(n) O(n log n) Building the heaps by repeated insertion takes linear time on average.
  • Space complexity: O(n) for the values stored in the two heaps.

  • Auxiliary space excluding stored values: O(1).

  • Recursion stack: O(1), since the implementation is iterative.

  • The external input collection is not counted; the enqueued values are retained by the data structure.

Code Example

from heapq import heappop, heappush


class MedianQueue:
    """Maintain the median of integer values added to a queue."""

    def __init__(self) -> None:
        # Max-heap represented by negated values.
        self._lower: list[int] = []
        # Min-heap containing the upper half.
        self._upper: list[int] = []

    def enqueue(self, value: int) -> float:
        """Add a value and return the median of all enqueued values."""
        if not self._lower or value <= -self._lower[0]:
            heappush(self._lower, -value)
        else:
            heappush(self._upper, value)

        # Keep the lower heap the same size as the upper heap or one larger.
        if len(self._lower) > len(self._upper) + 1:
            heappush(self._upper, -heappop(self._lower))
        elif len(self._upper) > len(self._lower):
            heappush(self._lower, -heappop(self._upper))

        return self.median()

    def median(self) -> float:
        """Return the current median, or raise ValueError if empty."""
        if not self._lower and not self._upper:
            raise ValueError("cannot take the median of an empty queue")

        if len(self._lower) == len(self._upper):
            return (-self._lower[0] + self._upper[0]) / 2.0

        return float(-self._lower[0])


if __name__ == "__main__":
    queue = MedianQueue()
    print(queue.enqueue(5))   # 5.0
    print(queue.enqueue(10))  # 7.5
    print(queue.enqueue(3))   # 5.0
    print(queue.enqueue(7))   # 6.0

Example Walkthrough

For the values 5, 10, 3, and 7:

Operation Lower heap, logically Upper heap, logically Median
Enqueue 5 [5] [] 5.0
Enqueue 10 [5] [10] 7.5
Enqueue 3 [3, 5] [10] 5.0
Enqueue 7 [3, 5] [7, 10] 6.0

Best Practices

  • Use collections.deque for an ordinary FIFO queue, where append and popleft are O(1). It is not sufficient by itself for maintaining a running median.

  • Use heapq for heap-based operations. Because heapq is a min-heap, negate values when implementing the lower max-heap.

  • This implementation assumes the requested operations are enqueue and median. If FIFO removal is also required, it must be designed separately, commonly with a deque and lazy deletion or indexed heap entries.

  • Use queue.Queue instead when thread-safe producer-consumer behavior is required; it does not provide median queries.

Common Pitfalls

  • Calling median() on an empty queue: the implementation raises ValueError rather than returning an invalid result.

  • Assuming the median is always an integer: with an even number of values, the two middle values must be averaged.

  • Forgetting to rebalance after insertion: the heap roots may then represent the wrong values.

  • Negating values incorrectly: store -value in the lower heap and reverse the sign when reading its root.

  • The design handles duplicates, negative numbers, one-element queues, and already sorted input without special cases. Disconnected graphs and cycles are not applicable to this queue operation.

55

How do you implement a frequency-prioritized queue?

A frequency-prioritized queue removes the element with the highest access count before elements with lower counts. This implementation uses a heap for ordering and a dictionary for frequencies, with FIFO ordering for equal frequencies.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • enqueue(value) adds an item with frequency 0 and returns a stable item handle.

  • access(item_id) increases that item’s frequency and inserts an updated heap entry.

  • dequeue() removes the item with the highest frequency.

  • Ties use the original enqueue sequence, so the oldest item wins regardless of when it was accessed.

  • Because heapq entries are immutable snapshots, updating an item pushes a new entry and leaves the old one stale.

  • Stale entries are discarded lazily, and the heap is rebuilt when it grows too large relative to the number of active items.

  • The negative frequency in each heap tuple makes Python’s min-heap behave like a max-frequency queue.

Duplicates are supported as separate queue items because each enqueue call returns a distinct handle.

Variant Representation Typical use
Simple FIFO Fixed array with head and tail indices modulo capacity Bounded, predictable memory
Double-ended queue collections.deque FIFO or LIFO behavior
Priority queue heapq Items ordered by a changing priority

For thread-safe producer/consumer code, use queue.Queue rather than this implementation.

Complexity

Let n be the number of active items.

Operation Best Average Amortized Worst
enqueue O(1) O(log n) O(log n) O(log n)
access O(1) O(log n) O(log n) O(n)
dequeue O(log n) O(log n) O(log n) O(n log n)

Heap insertion and removal account for the logarithmic cost. An access can trigger an O(n) compaction. A dequeue can remove O(n) stale entries, each costing O(log n), giving an O(n log n) individual worst case. Across a complete operation sequence, each stale entry is removed at most once, so stale-entry removal is charged to the access that created it and the amortized cost remains O(log n).

Space usage is O(n), including the heap and dictionary; the input is not counted, and there is no recursion stack.

Example Walkthrough

  1. Enqueue A, B, and C; all frequencies are 0.

  2. Access A twice; its frequency becomes 2.

  3. Access B once; its frequency becomes 1.

  4. Dequeue A because frequency 2 is highest.

  5. Dequeue B because frequency 1 is next.

  6. Dequeue C last.

Code Example

from __future__ import annotations

from dataclasses import dataclass
import heapq
from typing import Generic, TypeVar


T = TypeVar("T")


@dataclass
class _QueueItem(Generic[T]):
    item_id: int
    value: T
    frequency: int
    order: int
    version: int


class FrequencyPriorityQueue(Generic[T]):
    """Remove the most frequently accessed item first."""

    def __init__(self) -> None:
        self._items: dict[int, _QueueItem[T]] = {}
        self._heap: list[tuple[int, int, int, int]] = []
        self._next_id = 0
        self._next_order = 0

    def __len__(self) -> int:
        return len(self._items)

    def enqueue(self, value: T) -> int:
        """Add a value and return a handle for accessing it."""
        item = _QueueItem(
            item_id=self._next_id,
            value=value,
            frequency=0,
            order=self._next_order,
            version=0,
        )
        self._next_id += 1
        self._next_order += 1

        self._items[item.item_id] = item
        heapq.heappush(
            self._heap,
            (-item.frequency, item.order, item.item_id, item.version),
        )
        self._maybe_compact()
        return item.item_id

    def access(self, item_id: int) -> int:
        """Record an access and return the new frequency."""
        item = self._items.get(item_id)
        if item is None:
            raise KeyError(f"Unknown item id: {item_id}")

        item.frequency += 1
        item.version += 1

        heapq.heappush(
            self._heap,
            (-item.frequency, item.order, item.item_id, item.version),
        )
        self._maybe_compact()
        return item.frequency

    def dequeue(self) -> T | None:
        """Remove and return the highest-frequency item, or None if empty."""
        self._discard_stale_entries()
        if not self._heap:
            return None

        _, _, item_id, _ = heapq.heappop(self._heap)
        item = self._items.pop(item_id)
        self._maybe_compact()
        return item.value

    def _is_current(
        self,
        negative_frequency: int,
        order: int,
        item_id: int,
        version: int,
    ) -> bool:
        item = self._items.get(item_id)
        return (
            item is not None
            and item.frequency == -negative_frequency
            and item.order == order
            and item.version == version
        )

    def _discard_stale_entries(self) -> None:
        while self._heap:
            if self._is_current(*self._heap[0]):
                return
            heapq.heappop(self._heap)

    def _maybe_compact(self) -> None:
        if not self._items:
            self._heap.clear()
        elif len(self._heap) > 2 * len(self._items):
            self._heap = [
                (-item.frequency, item.order, item.item_id, item.version)
                for item in self._items.values()
            ]
            heapq.heapify(self._heap)


if __name__ == "__main__":
    queue = FrequencyPriorityQueue[str]()
    first = queue.enqueue("A")
    second = queue.enqueue("B")
    queue.enqueue("C")

    queue.access(first)
    queue.access(first)
    queue.access(second)

    print([queue.dequeue(), queue.dequeue(), queue.dequeue()])
    # Expected output: ['A', 'B', 'C']

Common Pitfalls

  • Calling list.pop(0) is O(n); use collections.deque for ordinary FIFO queues.

  • A heapq entry cannot be updated in place, so stale entries must be handled explicitly.

  • Keep the tie-breaking sequence separate from the access timestamp if FIFO ties are required.

  • Clarify whether “access” includes peek, get, or only an explicit access operation.

  • Empty queues return None; a one-element queue works normally.

  • Negative values are supported because values are opaque; only access frequency affects priority.

  • Duplicate values are separate items, and each item requires its own handle.

  • Sorted input, disconnected graphs, and cycles are not relevant to this queue structure.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 55 Queues answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects