Queue

Posted by Dustin Boston in Data Structures.

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

Time complexity for access and search is Linear, i.e. O(n)
Time complexity for insertion and deletion is Constant, i.e. O(n)
Space complexity is Linear

Source Code Listing

code.ts

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

code_test.ts

import {test, expect} from "bun:test";
import {Queue, printQueue} from "./code";

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

test("testEnqueue", () => {
  const queue = new Queue<number>(Array.from({length: 2}));
  queue.enqueue(1);
  queue.enqueue(2);

  expect(print(queue)).toBe(`{"head":0,"tail":0,"queue":[1,2]}`);
});

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

  queue.dequeue();
  queue.dequeue();
  queue.dequeue();

  expect(print(queue)).toBe(`{"tail":0,"queue":[null,null,null]}`);
});

test("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();

  expect(() => queue.dequeue()).toThrow();
});

Tags: