Queue

A linear collection following the First-In-First-Out (FIFO) principle, supporting operations like enqueue and dequeue, useful in task scheduling.

/**
 * @file Queue
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Represents a Queue data structure with basic operations such as enqueue and
 * dequeue.
 */
class Queue<T> {
  queue: Array<T | undefined>;

/** Index of next element to dequeue */
  head: number | undefined = undefined;

/** Index of next element to enqueue */
  tail = 0;

/**
   * Creates an instance of a Queue from an existing array.
   *
   * @param array - The initial array to be converted into a queue.
   */
  constructor(array: T[] = []) {
    this.queue = array;
  }

isEmpty(): boolean {
    return this.head === undefined;
  }

isFull(): boolean {
    return this.head === this.tail;
  }

/**
   * Adds an element to the end of the queue. O(1)
   *
   * @param value - The element to be added to the queue.
   */
  enqueue(value: T): void {
    if (this.isFull()) {
      throw new Error('Queue is already at capacity.');
    }

this.queue[this.tail] = value;

if (this.head === undefined) {
      this.head = this.tail;
    }

this.tail = this.tail === this.queue.length - 1 ? 0 : this.tail + 1;
  }

/**
   * Removes and returns the element at the front of the queue. O(1)
   *
   * @returns The element removed from the front of the queue.
   */
  dequeue(): T | undefined {
    if (this.head === undefined) {
      throw new Error('Cannot dequeue from an empty queue.');
    }

const value = this.queue[this.head];
    this.queue[this.head] = undefined;

this.head = this.head === this.queue.length - 1 ? 0 : this.head + 1;

if (this.head === this.tail) {
      this.head = undefined;
    }

return value;
  }
}

function printQueue<T>(queueToPrint: Queue<T>) {
  return {
    head: queueToPrint.head,
    tail: queueToPrint.tail,
    queue: queueToPrint.queue,
  };
}

// Usage
(() => {
  const queue = new Queue<number>(Array.from({length: 2}));
  queue.enqueue(1);
  queue.enqueue(2);
  console.log('Enqueued two items.');

if (!queue.isFull()) {
    console.error('Expected queue to be full.');
  }

console.log(JSON.stringify(printQueue(queue)));

queue.dequeue();
  queue.dequeue();
  console.log('Dequeued two items.');

if (!queue.isEmpty()) {
    throw new Error('Expected queue to be empty.');
  }

console.log(JSON.stringify(printQueue(queue)));
})();