Queue

Overview

A queue is a data structure that stores items according to the First In First Out (FIFO) principle. The item that has been in the queue the longest is the first one to be removed.

Operations	Complexity
Enqueue (insert end)	O(1)
Dequeue (delete first)	O(1)
Peek (view first)	O(1)

Implementation

In a queue, operations occur at both ends, so using an array is not efficient since removing the first element is costly. A linked list implementation is more suitable.

Queue

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enqueue(value) {
    const newNode = new QueueNode(value);

    if (this.head === null) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.size++;
  }

  dequeue() {
    if (this.head === null) {
      throw new Error('queue is empty');
    }

    const value = this.head.value;
    this.head = this.head.next;
    this.size--;

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

    return value;
  }

  peek() {
    if (this.head === null) {
      throw new Error('queue is empty');
    }

    return this.head.value;
  }
}

Usage:

const myQueue = new Queue();

myQueue.enqueue('One');
myQueue.enqueue('Two');
myQueue.enqueue('Three');

console.log(myQueue.peek()); // One

console.log(myQueue.dequeue()); // One
console.log(myQueue.dequeue()); // Two
console.log(myQueue.dequeue()); // Three

console.log(myQueue.peek()); // Error: queue is empty

Queue

Overview

Implementation

On this page