Circular Queue

Series: Data Structures

Episodes: (6/6)

Introduction

A Circular Queue, also known as a Ring Buffer or Circular Buffer, is a data structure that behaves like a regular queue but with a fixed size. It overcomes one of the limitations of a standard linear queue, which is the wasted space at the beginning of the queue after a number of dequeuing operations. In a circular queue, when an element is dequeued, its position is reused for subsequent enqueued elements, effectively making the queue circular.

Implementation

 
/**
 * Implementation of a circular queue data structure.
 * @template T Type of items stored in the queue
 */
class CircularQueue<T> {
  /** Maximum number of items the queue can hold */
  private capacity: number;
 
  /** Internal storage array */
  private queue: Array<T | undefined>;
 
  /** Index of the front element */
  private front: number;
 
  /** Index of the rear element */
  private rear: number;
 
  /** Number of items in the queue */
  private size: number;
 
  /**
   * Creates a circular queue with the given capacity.
   * @param {number} capacity Maximum number of items the queue can hold
   */
  constructor(capacity: number) {
    this.capacity = capacity;
    this.queue = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
  }
 
  /**
   * Adds an item to the back of the queue.
   * @param {T} item Item to be added
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      console.log("Queue is full");
      return;
    }
    this.rear = (this.rear + 1) % this.capacity;
    this.queue[this.rear] = item;
    this.size++;
  }
 
  /**
   * Removes an item from the front of the queue.
   * @returns {T|undefined} The item removed, or undefined if the queue is empty
   */
  dequeue(): T | undefined {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return undefined;
    }
    const item = this.queue[this.front];
    this.queue[this.front] = undefined; // Remove the dequeued item
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
 
  /**
   * Gets the front item in the queue without removing it.
   * @returns {T|undefined} The front item, or undefined if the queue is empty
   */
  peek(): T | undefined {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return undefined;
    }
    return this.queue[this.front];
  }
 
  /**
   * Checks if the queue is full.
   * @returns {boolean} True if the queue is full
   */
  isFull(): boolean {
    return this.size === this.capacity;
  }
 
  /**
   * Checks if the queue is empty.
   * @returns {boolean} True if the queue is empty
   */
  isEmpty(): boolean {
    return this.size === 0;
  }
 
  /**
   * Displays the queue for debugging purposes.
   */
  display(): void {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return;
    }
    let index = this.front;
    let elements = [];
    for (let i = 0; i < this.size; i++) {
      elements.push(this.queue[index]);
      index = (index + 1) % this.capacity;
    }
    console.log("Queue:", elements.join(", "));
  }
}

Usage

 
// Example usage:
const queue = new CircularQueue<number>(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6); // Should print "Queue is full"
queue.display(); // Should print "Queue: 1, 2, 3, 4, 5"
console.log("Dequeued:", queue.dequeue()); // Should print "Dequeued: 1"
queue.display(); // Should print "Queue: 2, 3, 4, 5"
console.log("Peeked:", queue.peek()); // Should print "Peeked: 2"