The Algorithms logo
The Algorithms
AboutDonate

Queue

S
H
S
/* Queue
 * A Queue is a data structure that allows you to add an element to the end of
 * a list and remove the item at the front. A queue follows a FIFO (First In First Out)
 * system, where the first item to enter the queue is the first to be removed,
 * All these operation complexities are O(1).
 * This implementation following the linked list structure.
 */

class Queue {
  #size

  constructor() {
    this.head = null
    this.tail = null
    this.#size = 0

    return Object.seal(this)
  }

  get length() {
    return this.#size
  }

  /**
   * @description - Add a value to the end of the queue
   * @param {*} data
   * @returns {number} - The current size of queue
   */
  enqueue(data) {
    const node = { data, next: null }

    if (!this.head && !this.tail) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      this.tail = node
    }

    return ++this.#size
  }

  /**
   * @description - Removes the value at the front of the queue
   * @returns {*} - The first data of the queue
   */
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is Empty')
    }

    const firstData = this.peekFirst()

    this.head = this.head.next

    if (!this.head) {
      this.tail = null
    }

    this.#size--

    return firstData
  }

  /**
   * @description - Return the item at the front of the queue
   * @returns {*}
   */
  peekFirst() {
    if (this.isEmpty()) {
      throw new Error('Queue is Empty')
    }

    return this.head.data
  }

  /**
   * @description - Return the item at the tail of the queue
   * @returns {*}
   */
  peekLast() {
    if (this.isEmpty()) {
      throw new Error('Queue is Empty')
    }

    return this.tail.data
  }

  /**
   * @description - Return the array of Queue
   * @returns {Array<*>}
   */
  toArray() {
    const array = []
    let node = this.head

    while (node) {
      array.push(node.data)
      node = node.next
    }

    return array
  }

  /**
   * @description - Return is queue empty or not
   * @returns {boolean}
   */
  isEmpty() {
    return this.length === 0
  }
}

export default Queue
About this Algorithm

Description

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It is often compared to a real-world queue of people waiting in line. The element that is added first is the one that gets removed first. Queues are commonly used for various applications, such as task scheduling, managing requests, and more.

Queue Operations

  1. Enqueue (Push): This operation is used to add an item to the back or end of the queue. It's equivalent to "pushing" an item onto the queue. When you enqueue an item, it becomes the last item in the queue.

  2. Dequeue (Pop): Dequeue is the operation used to remove and return the front item from the queue. The item that has been in the queue the longest (the front item) is the one removed. After dequeuing an item, the next item in the queue becomes the new front.

  3. Peek (Front): This operation is used to view the front item in the queue without removing it. It provides a way to examine the item at the front of the queue without actually dequeuing it.

  4. isEmpty: This operation checks whether the queue is empty. If the queue contains no items, it returns true; otherwise, it returns false.

Source

Video URL

Implementation

  1. Queue Implementation Using Lists (Arrays)

In this approach, you can use a list (or array) to represent a queue. You will maintain two pointers, one pointing to the front of the queue and another pointing to the back. The front pointer keeps track of the element to be dequeued, and the back pointer keeps track of where new elements should be enqueued.

  1. Queue Implementation Using a Linked List

In this approach, you can use a linked list to implement a queue. You maintain two pointers, one pointing to the front (head) of the queue and another pointing to the back (tail). Enqueueing involves adding a new node at the tail, and dequeueing involves removing the node at the head.