Queue

A queue is a FIFO (first-in, first-out) structure: enqueue at the rear, dequeue from the front. Classic uses include BFS, level-order traversal, task scheduling, and buffering.

When to use a queue

Scenario	Why queue
BFS on graph/grid	Process nodes in increasing distance order
Level-order tree traversal	Visit level k before level k+1
Sliding window maximum (with deque)	See Deque
Producer–consumer / task pipeline	Fair ordering

Do not use a Python list with pop(0) for BFS — each dequeue is O(n) because elements shift left.

Complexity

Operation	collections.deque	List (pop(0))	Linked-list queue
Enqueue	O(1)	O(1) append	O(1)
Dequeue	O(1)	O(n)	O(1)
Peek front	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)
Space	O(n)	O(n)	O(n)

Always prefer collections.deque in Python interviews.

Python standard library (recommended)

from collections import deque

q: deque[int] = deque()

q.append(10)          # enqueue rear — O(1)
q.append(20)
front = q[0]          # peek — O(1)
x = q.popleft()       # dequeue front — O(1)

if q:
    q.popleft()

# BFS template
def bfs(start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Time: each node/edge processed once → O(V + E) for graphs.
Space: O(V) for queue + visited set.

Implementation with linked list

Maintains O(1) enqueue and dequeue without shifting.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class QueueLinkedList:
    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def enqueue(self, item) -> None:
        node = Node(item)
        if self.rear is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        self._size -= 1
        return data

    def peek(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        return self.front.data

    def is_empty(self) -> bool:
        return self.front is None

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

Time: enqueue/dequeue O(1).
Space: O(n) nodes.

Implementation with list (educational only)

class QueueList:
    """Avoid in production — dequeue is O(n). Use collections.deque instead."""

    def __init__(self):
        self._items: list = []

    def enqueue(self, item) -> None:
        self._items.append(item)      # O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.pop(0)     # O(n) — shifts all elements

    def peek(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        return self._items[0]

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

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

Queue vs stack vs deque

Structure	Order	Primary ops	Typical algorithm
Stack	LIFO	push/pop one end	DFS, parsing, monotonic stack
Queue	FIFO	enqueue rear, dequeue front	BFS, level order
Deque	Both ends	append/pop left & right	BFS with 0-1 weights, sliding window

Circular queue (fixed capacity)

Useful when buffer size is bounded (embedded systems, ring buffers):

class CircularQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.buffer = [None] * capacity
        self.head = 0
        self.tail = 0
        self.count = 0

    def enqueue(self, item) -> bool:
        if self.count == self.capacity:
            return False
        self.buffer[self.tail] = item
        self.tail = (self.tail + 1) % self.capacity
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            raise IndexError("empty queue")
        item = self.buffer[self.head]
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return item

Time: O(1) enqueue/dequeue.
Space: O(capacity).

Related pages

• Deque — double-ended queue; BFS with deque
• Graph — BFS traversal
• Tree — level-order traversal
• Stack — LIFO counterpart