Implementing the Queue

A Queue follows FIFO (First In, First Out). It is essential for breadth-first search (BFS), printer spools, and web server request handling.

1. Core Operations

All Queue operations must be O(1).

  • Enqueue(val): Add val to the back.
  • Dequeue(): Remove and return the front element.
  • Peek(): Return the front element.
  • IsEmpty(): Check if empty.

2. Implementation Strategies

A. Linked List Implementation

  • Head: Front of Queue (Dequeue here).
  • Tail: Back of Queue (Enqueue here).
  • Pros: Infinite size.
  • Cons: Dynamic allocation overhead.

B. Array Implementation (The Trap)

If you use a simple array [A, B, C]:

  • Dequeue A → [_, B, C]
  • Dequeue B → [_, _, C]
  • Problem: You have empty space at the front but run out of space at the back!
  • Solution: Ring Buffer (Circular Queue).

3. The Mathematical Anchor: Circular Queue (Modular Arithmetic)

How do we reuse space in a fixed-size array without expensive O(N) shifts? We use Modular Arithmetic.

The Wrap-Around Formula

If our array has size N:

  • Enqueue: tail = (tail + 1) % N
  • Dequeue: head = (head + 1) % N

Why it works

The % operator keeps our indices bounded between [0, N-1]. When tail reaches index 7 in an 8-size array, (7 + 1) % 8 = 0. The pointer “warps” back to the start.

The “Full” vs “Empty” Dilemma

How do we tell if the queue is full or empty if head == tail in both cases?

  1. Count approach: Keep a separate count variable (Simplest).
  2. Size-1 approach: Always keep one slot empty. Full is (tail + 1) % size == head.

4. Interactive: Ring Buffer Visualizer

A fixed-size array that wraps around. When the tail hits the end, it goes back to index 0.

Empty
Head Index: 0 | Tail Index: 0

5. Implementation

Java

// Using Java's built-in LinkedList as a Queue
import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
  public void demo() {
    Queue<Integer> q = new LinkedList<>();

    q.offer(10); // Enqueue
    q.offer(20);

    int front = q.peek(); // 10
    int removed = q.poll(); // 10

    // ArrayDeque is also valid and faster!
  }
}

Go

type Queue []int

func (q *Queue) Enqueue(v int) {
  *q = append(*q, v)
}

func (q *Queue) Dequeue() int {
  if len(*q) == 0 { return -1 }
  val := (*q)[0]
  *q = (*q)[1:] // Slicing off front
  return val
}