Queue

A queue is a linear data structure that follows First In, First Out (FIFO) order:

  • Elements are added at the back (tail).
  • Elements are removed from the front (head).

Queues model real‑world lines: the first person to join is the first to be served.

Core Operations

Typical queue API:

  • offer(x) / enqueue(x) – add x to the back.
  • poll() / dequeue() – remove and return the front element.
  • peek() – return the front element without removing it.
  • isEmpty() – check if the queue is empty.

Implementation options:

  • Circular buffer on top of an array.
  • Linked list with head and tail pointers.
  • Language‑provided Queue / ArrayDeque.

All core operations are O(1) amortized.

Queues in Algorithms

Queues are central to:

  • Breadth‑First Search (BFS):
    • Process nodes level by level in graphs and grids.
  • Topological sort (Kahn’s algorithm):
    • Maintain a queue of nodes with in‑degree 0.
  • Sliding window (with monotonic queue):
    • Maintain max/min over a moving window.

Any time you process “by layers” or “arrival order” matters, queues are natural.

Queues in Backend Systems

Queues also underpin many system design components:

  • Message queues (Kafka, RabbitMQ, RocketMQ):
    • Producers enqueue messages; consumers process them in order.
  • Task scheduling:
    • Job queues for background workers.
  • Rate limiting and buffering:
    • Requests or events are staged in queues to smooth out bursts.

Conceptually, these are distributed or durable versions of the same FIFO idea.

Pitfalls

  • Using a simple array and always inserting at index 0:
    • This leads to O(n) shift per operation; use a circular buffer or Deque instead.
  • Forgetting backpressure:
    • In systems, if producers are faster than consumers, queues can grow unbounded unless you enforce limits.

In most interview code:

  • Java: Queue<Integer> q = new ArrayDeque<>();
  • Python: from collections import deque and q = deque() with append / popleft.

As long as you respect FIFO semantics, the exact implementation can be swapped easily.

Example: BFS Using a Queue (Java)

Java
void bfs(int start, List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new ArrayDeque<>();

    visited[start] = true;
    q.offer(start);

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

This is the standard BFS pattern: the queue ensures nodes are processed in level order.