Алгоритмы. Очередь (Queue).

queue.md

Queue implementation using TypeScript

A queue is an abstract data type that serves as a collection of elements, with two principal operations: enqueue, which adds an element to the collection, and dequeue, which removes the earliest added element. The order in which elements are dequeued is First In First Out aka. FIFO. The term queue takes it name from the real world queues e.g. "a queue at the ticket counter". A good target is to implement these operations with a time complexity of O(1).

We could naively, implement it using a JavaScript array.

export class Queue<T> {
  private data: T[] = [];

  /** Enqueues the item in O(1) */
  enqueue(item: T): void {
    this.data.push(item);
  }

  /**
   * Dequeues the first inserted item in O(1)
   * If there are no more items it returns `undefined`
   */
  dequeue(): T | undefined {
    return this.data.shift();
  }
}

However, this implementation is incorrect because in JavaScript array's implementations, shift requires changing the index of any remaining elements in the array. Therefore this implementation has an average runtime of O(n) and thus does not meet our O(1) operation cost requirement.

To deal with it we simply use a null prototype object as our map.

export class Queue<T> {
  private data: { [index: number]: T } = Object.create(null);
  private nextEnqueueIndex = 0;
  private lastDequeuedIndex = 0;

  /** Enqueues the item in O(1) */
  enqueue(item: T): void {
    this.data[this.nextEnqueueIndex] = item;
    this.nextEnqueueIndex++;
  }

  /**
   * Dequeues the first inserted item in O(1)
   * If there are no more items it returns `undefined`
   */
  dequeue(): T | undefined {
    if (this.lastDequeuedIndex !== this.nextEnqueueIndex) {
      const dequeued = this.data[this.lastDequeuedIndex];
      delete this.data[this.lastDequeuedIndex];
      this.lastDequeuedIndex++;
      return dequeued;
    }
  }
  
  /**
   * Returns the number of elements in the queue
   */
  size(): number {
    return this.nextEnqueueIndex - this.lastDequeuedIndex;
  }
}