Dustin Boston

/**
 * @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.
 */
export 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;
  }
}

export 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)));
})();

import {Queue, printQueue} from "../../../../data/algorithms/src/queue.ts";
import {assertEquals, assertThrows} from "$assert";

function print(queue: Queue<number>) {
  return JSON.stringify(printQueue(queue));
}

test(function testEnqueue() {
  const queue = new Queue<number>(Array.from({length: 3}));

  assertEquals(print(queue), `{"head":null,"tail":0,"Q":[null,null,null]}`);

  queue.enqueue(1);
  assertEquals(print(queue), `{"head":0,"tail":1,"Q":[1,null,null]}`);

  queue.enqueue(2);
  assertEquals(print(queue), `{"head":0,"tail":2,"Q":[1,2,null]}`);

  queue.enqueue(3);
  assertEquals(print(queue), `{"head":0,"tail":0,"Q":[1,2,3]}`);
});

test(function testOverflow() {
  const queue = new Queue<number>(Array.from({length: 3}));
  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);
  assertThrows(() => {
    queue.enqueue(4);
  });
});

test(function testDequeue() {
  const queue = new Queue<number>(Array.from({length: 3}));
  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);

  queue.dequeue();
  assertEquals(print(queue), `{"head":1,"tail":0,"Q":[null,2,3]}`);

  queue.dequeue();
  assertEquals(print(queue), `{"head":2,"tail":0,"Q":[null,null,3]}`);

  queue.dequeue();
  assertEquals(print(queue), `{"head":null,"tail":0,"Q":[null,null,null]}`);
});

test(function testUnderflow() {
  const queue = new Queue<number>(Array.from({length: 3}));
  queue.enqueue(1);
  queue.enqueue(2);
  queue.enqueue(3);
  queue.dequeue();
  queue.dequeue();
  queue.dequeue();

  assertThrows(() => queue.dequeue());
});