Circular Queue

Overview

A circular queue (also called a ring buffer) is a fixed-size queue that reuses space by wrapping around when the rear reaches the end of the array. Unlike a regular array-based queue where space is wasted as the front pointer moves forward, a circular queue efficiently uses all available space by treating the array as circular.

Circular queues are essential when you need a fixed-size queue with O(1) enqueue and dequeue operations, such as in embedded systems, real-time applications, or when memory is constrained. They're particularly useful for buffering, task scheduling with fixed capacity, and streaming data processing.

Key characteristics:

• Fixed size - Predefined capacity that cannot be exceeded
• Wraparound - Rear wraps to front when reaching end
• O(1) operations - Enqueue and dequeue in constant time
• Space efficient - Reuses space instead of wasting it
• Two pointers - Front (dequeue) and rear (enqueue) indices

How Circular Queue Works

Circular queue uses modulo arithmetic to wrap around:

1. Array - Fixed-size array to store elements
2. Front pointer - Index of first element (for dequeue)
3. Rear pointer - Index where next element will be added (for enqueue)
4. Modulo operation - (index + 1) % capacity wraps around
5. Empty vs Full - Need special handling to distinguish empty from full

The wraparound allows the queue to reuse space efficiently.

Basic Circular Queue Implementation

Standard implementation with front and rear pointers:

class CircularQueue<T> {
  private items: (T | null)[];
  private front = 0;
  private rear = -1;
  private size = 0;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
  
  enqueue(item: T): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = item;
    this.size++;
    return true;
  }
  
  dequeue(): T | null {
    if (this.isEmpty()) return null;
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
  
  peek(): T | null {
    return this.isEmpty() ? null : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
  
  getSize(): number {
    return this.size;
  }
}

Time: O(1) for all operations, Space: O(capacity)

Key points:

• Use size counter to distinguish empty from full
• Modulo arithmetic for wraparound: (index + 1) % capacity
• Initialize rear = -1 so first enqueue sets rear = 0

Alternative: Using Only Front and Rear (No Size Counter)

Implementation without size counter (more space-efficient but trickier):

class CircularQueueNoSize<T> {
  private items: (T | null)[];
  private front = 0;
  private rear = -1;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
  
  enqueue(item: T): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = item;
    return true;
  }
  
  dequeue(): T | null {
    if (this.isEmpty()) return null;
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    return item;
  }
  
  peek(): T | null {
    return this.isEmpty() ? null : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.rear === -1 || (this.front === (this.rear + 1) % this.capacity && this.items[this.front] === null);
  }
  
  isFull(): boolean {
    return this.front === (this.rear + 1) % this.capacity && this.items[this.front] !== null;
  }
}

Note: This approach is more complex and error-prone. Using a size counter is recommended.

Pattern 1: Design Circular Queue (LeetCode)

LeetCode-style implementation:

class MyCircularQueue {
  private items: number[];
  private front = 0;
  private rear = -1;
  private size = 0;
  private capacity: number;
  
  constructor(k: number) {
    this.capacity = k;
    this.items = new Array(k);
  }
  
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = value;
    this.size++;
    return true;
  }
  
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return true;
  }
  
  Front(): number {
    return this.isEmpty() ? -1 : this.items[this.front];
  }
  
  Rear(): number {
    return this.isEmpty() ? -1 : this.items[this.rear];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Time: O(1) for all operations

Pattern 2: Moving Average from Data Stream

Use circular queue to maintain sliding window:

class MovingAverage {
  private queue: CircularQueue<number>;
  private sum = 0;
  
  constructor(size: number) {
    this.queue = new CircularQueue<number>(size);
  }
  
  next(val: number): number {
    if (this.queue.isFull()) {
      const removed = this.queue.dequeue();
      if (removed !== null) {
        this.sum -= removed;
      }
    }
    
    this.queue.enqueue(val);
    this.sum += val;
    
    return this.sum / this.queue.getSize();
  }
}

Time: O(1) per call, Space: O(size)

Pattern 3: Task Scheduler with Fixed Capacity

Circular queue for round-robin task scheduling:

interface Task {
  id: number;
  name: string;
}

class TaskScheduler {
  private queue: CircularQueue<Task>;
  
  constructor(capacity: number) {
    this.queue = new CircularQueue<Task>(capacity);
  }
  
  addTask(task: Task): boolean {
    return this.queue.enqueue(task);
  }
  
  processNext(): Task | null {
    return this.queue.dequeue();
  }
  
  hasTasks(): boolean {
    return !this.queue.isEmpty();
  }
  
  isFull(): boolean {
    return this.queue.isFull();
  }
}

Use case: Round-robin scheduling with fixed capacity

Pattern 4: Circular Buffer for Streaming Data

Use circular queue as buffer for streaming:

class StreamBuffer<T> {
  private buffer: CircularQueue<T>;
  
  constructor(capacity: number) {
    this.buffer = new CircularQueue<T>(capacity);
  }
  
  write(data: T): boolean {
    return this.buffer.enqueue(data);
  }
  
  read(): T | null {
    return this.buffer.dequeue();
  }
  
  peek(): T | null {
    return this.buffer.peek();
  }
  
  getBufferSize(): number {
    return this.buffer.getSize();
  }
  
  isBufferFull(): boolean {
    return this.buffer.isFull();
  }
}

Use case: Buffering streaming data with fixed capacity

Pattern 5: Rate Limiter with Circular Queue

Track requests in time windows:

class RateLimiter {
  private timestamps: CircularQueue<number>;
  private windowSize: number;
  
  constructor(capacity: number, windowSizeMs: number) {
    this.timestamps = new CircularQueue<number>(capacity);
    this.windowSize = windowSizeMs;
  }
  
  canMakeRequest(): boolean {
    const now = Date.now();
    
    // Remove old timestamps outside window
    while (!this.timestamps.isEmpty()) {
      const oldest = this.timestamps.peek();
      if (oldest !== null && now - oldest > this.windowSize) {
        this.timestamps.dequeue();
      } else {
        break;
      }
    }
    
    // Check if we can add new request
    if (this.timestamps.isFull()) {
      return false;
    }
    
    this.timestamps.enqueue(now);
    return true;
  }
}

Use case: Rate limiting with fixed request capacity

When to Use Circular Queue

Use circular queue when you see these signals:

• "Fixed size" or "fixed capacity" - Cannot exceed capacity
• "Ring buffer" or "circular buffer" - Explicitly mentioned
• "Reuse space" - Need to reuse array space efficiently
• "O(1) operations" - Need constant time enqueue/dequeue
• "Memory constrained" - Limited memory available
• "Sliding window" - Fixed-size window over data stream
• "Round-robin" - Circular processing pattern

Key distinction:

• Circular Queue - Fixed size, wraparound, O(1) operations
• Regular Queue - Dynamic size, may waste space
• Deque - Double-ended, can grow dynamically

Circular Queue vs Regular Queue

| Aspect | Circular Queue | Regular Queue |

|--------|----------------|---------------|

| Size | Fixed capacity | Dynamic size |

| Space | Reuses space efficiently | May waste space |

| Operations | O(1) enqueue/dequeue | O(1) amortized |

| Use case | Fixed capacity, memory constrained | Dynamic capacity needed |

| Implementation | Modulo arithmetic | Linked list or array |

Remember:

• Circular queue for fixed-size, space-efficient scenarios
• Regular queue for dynamic size requirements

Template (Basic Circular Queue)

class CircularQueueTemplate<T> {
  private items: (T | null)[];
  private front = 0;
  private rear = -1;
  private size = 0;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
  
  enqueue(item: T): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = item;
    this.size++;
    return true;
  }
  
  dequeue(): T | null {
    if (this.isEmpty()) return null;
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
  
  peek(): T | null {
    return this.isEmpty() ? null : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Template (Sliding Window with Circular Queue)

function slidingWindowTemplate<T>(data: T[], windowSize: number): T[] {
  const queue = new CircularQueueTemplate<T>(windowSize);
  const result: T[] = [];
  
  for (const item of data) {
    if (queue.isFull()) {
      const removed = queue.dequeue();
      // Process removed item if needed
    }
    
    queue.enqueue(item);
    
    // Process window if needed
    // processWindow(queue);
  }
  
  return result;
}

Time and Space Complexity

All Operations

• enqueue: O(1)
• dequeue: O(1)
• peek: O(1)
• isEmpty: O(1)
• isFull: O(1)
• Space: O(capacity)

Note: All operations are O(1) because:

• Array access is O(1)
• Modulo operation is O(1)
• Size counter check is O(1)

Practice Tips

1. Use size counter - Simplest way to distinguish empty from full
2. Modulo arithmetic - (index + 1) % capacity for wraparound
3. Initialize rear = -1 - So first enqueue sets rear = 0
4. Handle full queue - Return false or throw error when full
5. Clear references - Set items to null when dequeuing (for GC)
6. Test wraparound - Ensure front/rear wrap correctly
7. Edge cases - Empty queue, full queue, single element

Common Mistakes

1. Not using size counter - Hard to distinguish empty from full
2. Wrong modulo calculation - Off-by-one errors in wraparound
3. Not initializing rear = -1 - First enqueue won't work correctly
4. Forgetting to check full - Enqueue when full causes data loss
5. Not clearing references - Memory leaks in dequeued items
6. Wrong empty check - Using front === rear doesn't work
7. Index out of bounds - Not using modulo for index calculation

Real-World Applications

Circular queues are used extensively in:

• Operating Systems - Process scheduling, interrupt handling
• Embedded Systems - Fixed-size buffers, sensor data
• Networking - Packet buffering, network queues
• Audio/Video Processing - Streaming buffers, sample buffers
• Real-Time Systems - Fixed-capacity task queues
• Game Development - Input buffering, event queues
• Data Streaming - Sliding window calculations
• Rate Limiting - Fixed-capacity request tracking

Related Concepts

• Queue Basics - Foundation for circular queue
• Deque - Double-ended queue (can be circular)
• Sliding Window - Often uses circular queue
• Ring Buffer - Another name for circular queue
• Fixed-Size Buffer - General concept circular queue implements

Summary

Circular queue is a fixed-size queue with wraparound:

• Fixed capacity - Cannot exceed predefined size
• Wraparound - Reuses space efficiently
• O(1) operations - Constant time enqueue/dequeue
• Space efficient - No wasted space
• Essential - For fixed-size queue requirements

Key takeaways:

• Use size counter to distinguish empty from full
• Modulo arithmetic for wraparound: (index + 1) % capacity
• Initialize rear = -1 for correct first enqueue
• All operations are O(1)
• Essential for fixed-capacity scenarios

Mastering circular queue will help you solve fixed-size queue problems efficiently in coding interviews.