Implementing the Queue

[!NOTE] This module explores the core principles of Queue Implementations, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

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

Core Operations (O(1)):

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

Implementations:

1. Linked List: Infinite size, but dynamic allocation overhead.
2. Ring Buffer (Circular Array): Fixed size, cache-friendly, uses modular arithmetic.

---

2. Interactive Analysis: Ring Buffer

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

Empty

Head Index: 0 | Tail Index: 0

---

3. Intuition: Modular Arithmetic

How do we reuse space? 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.

---

4. Implementation

Java

Go

// 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 for stack/queue!
  }
}

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
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Linked List	O(1)	O(N)	Dynamic size.
Ring Buffer	O(1)	O(N)	Fixed size, no alloc overhead.