TypeScript data structure: Queue

Queue

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.

The operation of adding an element to the rear of the queue is known as enqueue, and the operation of removing an element from the front is known as dequeue. Other operations may also be allowed, often including a peek or front operation that returns the value of the next element to be dequeued without dequeuing it.

The operations of a queue make it a first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. A queue is an example of a linear data structure, or more abstractly a sequential collection

Representation of a FIFO (first in, first out) queue

Implementation

Implement using built-in object as a map, with tail pointer. I came up with this approach to make sure the Big O notation for the dequeue operation. You can implement with the same approach using array instead of object. But to take one element out of an array could take O(n).

Completed Source code

You can find the source code in my TS data structure repo

trungk18/typescript-data-structures/tree/master/data-structures/queue

import { ObjectType } from '../model/objectType';

export class Queue<T> {
  private _queue: ObjectType<T>;
  private _head: number;
  private _tail: number;

  constructor() {
    this._queue = {};
    this._head = 0;
    this._tail = 0;
  }

  get isEmpty() {
    return this.size === 0;
  }

  get size() {
    return this._tail - this._head;
  }

  enqueue(value: T): void {
    this._queue[this._tail] = value;
    this._tail++;
  }

  dequeue(): T {
    if (this.isEmpty) {
      return undefined;
    }
    const value = this._queue[this._head];
    delete this._queue[this._head];
    this._head++;
    return value;
  }

  peek(): T {
    if (this.isEmpty) {
      return undefined;
    }
    return this._queue[this._head];
  }

  clear(): void {
    this._queue = {};
    this._head = 0;
    this._tail = 0;
  }

  print(): string {
    if (this.isEmpty) {
      return '';
    }
    let values = [];
    for (let i = this._head; i < this._tail; i++) {
      values.unshift(this._queue[i].toString());
    }
    return values.join(' -> ');
  }
}

Alternative Implementation

1. Trivial implementation using Array - Using arr.shift() for dequeuing, take O(n) time. That will not meet the requirement of O(1) for dequeuing.
2. Queue

References

• Wikipedia