MV's blog

Queues

A queue is a data structure that stores a collection of values T. It has FIFO mechanics, i.e the first item that was added is the first item to be returned(removed).

A queue implements the following API:

interface IQueue<T> {
  /**
   * Adds an item in the queue
   * @param  {T} value
   */
  enqueue(value: T): void;

  /**
   * Removes and returns an item from the queue
   * @returns T
   */
  dequeue(): T;

  /**
   * Returns the number of items in the queue
   * @returns number
   */
  size(): number;

  /**
   * Returns whether the queue is empty
   * @returns boolean
   */
  isEmpty(): boolean;
}

Sample typescript implementation that uses a doubly linked list for storing the values. For linked lists refer here.

class ListNode<T> {
  value: T;
  prev: ListNode<T>;
  next: ListNode<T>;
}

export class Queue<T> implements IQueue<T> {
  private first: ListNode<T> = null;
  private last: ListNode<T> = null;
  private count: number = 0;

  public enqueue(value: T): void {
    if (value == null) throw new Error('Invalid value');

    const node = new ListNode<T>();
    node.value = value;
    node.next = this.first;
    node.prev = null;

    if (this.isEmpty()) {
      this.last = node;
    } else {
      this.first.prev = node;
    }

    this.first = node;
    this.count++;
  }

  public dequeue(): T {
    if (this.isEmpty()) throw new Error('Invalid operation');

    const value = this.last.value;

    this.last = this.last.prev;
    this.count--;

    if (this.isEmpty()) {
      this.first = null;
    } else {
      this.last.next = null;
    }

    return value;
  }

  public isEmpty(): boolean {
    return this.count === 0;
  }

  public size(): number {
    return this.count;
  }
}

Alternatively it can be implemented with an array, either a predefined one or with resizing; depending on the use case.

The time cost for the enqueue() and dequeue() operations is O(1).

Image taken from: https://www.coursera.org/learn/algorithms-part1/