Circular Queue Implementation in TypeScript

Circular queues are a fundamental data structure that follows the First-In-First-Out (FIFO) principle, but with a unique twist—the last element is connected to the first, forming a circular structure. In this article, we’ll delve into the TypeScript implementation of a circular queue, exploring its key components and understanding how it efficiently manages data.

Understanding Circular Queues

A circular queue consists of a fixed-size array and two pointers: a front pointer (head) and a rear pointer (tail). The front represents the beginning of the queue, and the rear represents the end. Unlike a standard linear queue, when the rear pointer reaches the end of the array, it wraps around to the beginning. This circular nature optimizes memory usage and facilitates a continuous flow of data.

TypeScript Implementation

Let’s break down the TypeScript implementation of a circular queue:

Interface: IQueue<T>

export interface IQueue<T> {
  items: T[];
  size: number;
  head: number;
  tail: number;

  enqueue(item: T): T | undefined;
  dequeue(): T | undefined;
}

The IQueue interface defines the structure of a circular queue, specifying properties like items, size, head, and tail. It also declares methods for enqueueing and dequeuing items.

Class: Queue<T>

export class Queue<T> implements IQueue<T> {
  // ... (constructor and private storage)

  get items(): T[] {
    // Implementation for getting items based on head and tail pointers
  }

  get size(): number {
    // Implementation for calculating the size of the queue
  }

  enqueue(item: T): T | undefined {
    // Implementation for enqueueing an item
  }

  dequeue(): T | undefined {
    // Implementation for dequeuing an item
  }
}

The Queue class implements the IQueue interface and includes private storage, head, and tail properties. Getter methods retrieve items and calculate the size based on the circular nature of the queue. Enqueue and dequeue methods add and remove items while considering the circular structure.

Example Usage

// Example usage of the circular queue
(function () {
  const queue = new Queue<string>(5);

  queue.enqueue("Hola1");
  queue.enqueue("Hola2");
  queue.enqueue("Hola3");
  console.log(queue.items); // [ 'Hola1', 'Hola2', 'Hola3' ]
  
  queue.dequeue();
  queue.enqueue("Hola4");
  
  console.log(queue.items); // [ 'Hola2', 'Hola3', 'Hola4' ]
  console.log("Actual Size: ", queue.size); // Actual Size:  3
  console.log("Head: ", queue.head); // Head:  1
  console.log("Tail: ", queue.tail); // Tail:  4
})();

The example demonstrates the usage of the circular queue by enqueuing and dequeuing items and printing the current state of the queue, including its size, head, and tail pointers.

Final Circular Queue

/**
 * @description Queue Interface
 * @type {interface}
 */
export interface IQueue<T> {
  items: T[];
  size: number;
  head: number;
  tail: number;

  enqueue(item: T): T | undefined;
  dequeue(): T | undefined;
}

/**
 * @description: Circular Queue
 * @implements {IQueue<T>}
 * @example
 * ```ts
 * const queue = new Queue<string>(5);
 * queue.enqueue("Hola1");
 * queue.dequeue();
 * ```
 */
export class Queue<T> implements IQueue<T> {
  private _storage: T[] = [];
  public head: number = 0;
  public tail: number = 0;

  /**
   * @param {number} [_capacity=100] - capacity is max number of queue items, Default queue 100 of item can be take
   */
  constructor(private _capacity: number = 100) {
    this._storage.length = this._capacity + 1;
  }

  /**
   * @return {number[]} queue storage
   */
  get items(): T[] {
    if (this.head < this.tail) return this._storage.slice(this.head, this.tail);
    if (this.head > this.tail) {
      const _items = this._storage.slice(this.head)
      if (this.tail > 0) {
        _items.concat(this._storage.slice(0, this.tail))
        return  _items.concat(this._storage.slice(0, this.tail))
      }
      return _items
    }
    return [];
  }

  /**
   * @return {number} queue size
   */
  get size(): number {
    if (this.head < this.tail) return this.tail - this.head;
    if (this.head > this.tail)
      return this._capacity - this.head + this.tail + 1;
    return 0;
  }

  /**
   * @param {T} item
   * @return {T | undefined} When successfully pushed it's return item, If failed, return undefined
   *
   * @description Push Item To Circler Queue
   * @Time-Complexity: O(1)
   * @Space-Complexity: O(1)
   */
  enqueue(item: T): T | undefined {
    if ((this.tail + 1) % (this._capacity + 1) === this.head) return undefined; // console.error("Queue is full!!! Maximum capacity of storage reached!!!", `Item: ${item}`)
    this._storage[this.tail] = item;
    this.tail = (this.tail + 1) % (this._capacity + 1);
    return item;
  }

  /**
   * @return {T | undefined} When successfully remove it's return item, If failed, return undefined
   *
   * @description: Remove Item From Circler Queue
   * @Time-Complexity: O(1)
   * @Space-Complexity: O(1)
   */
  dequeue(): T | undefined {
    if (this.head === this.tail) return undefined; // console.error("Queue is empty!!!")
    const item = this._storage[this.head];
    this.head = (this.head + 1) % (this._capacity + 1);
    return item;
  }
}

// Run
(function () {
  const queue = new Queue<string>(5);

  queue.enqueue("Hola1");
  queue.enqueue("Hola2");
  queue.enqueue("Hola3");
  console.log(queue.items); // [ 'Hola1', 'Hola2', 'Hola3' ]
  queue.dequeue()
  queue.enqueue("Hola4");
  console.log(queue.items); // [ 'Hola2', 'Hola3', 'Hola4' ]
  console.log("Actual Size: ", queue.size); // Actual Size:  3
  console.log("Head: ", queue.head); // Head:  1
  console.log("Tail: ", queue.tail); // Tail:  4
})();

Conclusion

Implementing a circular queue in TypeScript provides a versatile and efficient way to manage data structures, especially in scenarios where a fixed-size buffer is required. Understanding the principles behind circular queues and their TypeScript implementation can empower developers to make informed decisions about data structure choices in their applications.