How to implement queue data structure in JavaScript

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a queue, the first element added to the structure will be the first one to be removed. Think of it like people waiting in a line – the person who arrives first is the first to leave the line.

The basic operations associated with a queue are:

• Enqueue (Insertion): Adds an element to the end (rear) of the queue.
• Dequeue (Deletion): Removes the element from the front (head) of the queue.
• Front (Peek): Returns the element at the front of the queue without removing it.
• IsEmpty: Checks if the queue is empty.
• Size (or Length): Returns the number of elements in the queue.

These operations provide a way to manage data in a manner that respects the order of insertion. Queues are used in various applications like scheduling processes, managing tasks, and in scenarios where elements are processed in a sequential order.

There are several ways to implement a queue data structure in JavaScript. Each approach has its own advantages and disadvantages.

Using an array

Array-based implementation is straightforward and easy to understand. The built-in array methods make it convenient to perform queue operations.

Arrays provide constant-time access to elements by index, but in the context of a queue, this is not usually exploited as queues mainly involve adding and removing elements from the ends.

class Queue {
  constructor() {
    this.items = []; // Array to store queue elements
  }

  enqueue(item) {
    this.items.push(item);
    return item + " inserted";
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }
}

const queue = new Queue();
console.log(queue.enqueue(7));
console.log(queue.enqueue(2));
console.log(queue.enqueue(6));
console.log(queue.enqueue(4));
console.log(queue.dequeue());
console.log(queue.peek());

// Output:
// 7 inserted
// 2 inserted
// 6 inserted
// 4 inserted
// 7
// 2

When the array reaches its capacity, and you need to enqueue more elements, you may need to resize the array, which involves creating a new, larger array and copying elements. This operation takes O(n) time where n is the number of elements in the queue.

Using an object

Unlike arrays, objects in JavaScript can easily accommodate dynamic sizing without the need for resizing operations. You can add and remove properties (elements) without explicitly resizing.

class Queue {
  constructor() {
    this.items = {}; // Object to store queue elements
    this.frontIndex = 0; // Index of the front element
    this.backIndex = 0; // Index of the next available position
  }

  enqueue(item) {
    this.items[this.backIndex] = item;
    this.backIndex++;
    return item + " inserted";
  }

  dequeue() {
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }

  peek() {
    return this.items[this.frontIndex];
  }

  get printQueue() {
    return this.items;
  }
}

const queue = new Queue();
console.log(queue.enqueue(7));
console.log(queue.enqueue(2));
console.log(queue.enqueue(6));
console.log(queue.enqueue(4));
console.log(queue.dequeue());
console.log(queue.peek());
const str = queue.printQueue;
console.log(str);

// Output:
// 7 inserted
// 2 inserted
// 6 inserted
// 4 inserted
// 7
// 2
// { '1': 2, '2': 6, '3': 4 }

Keep in mind that in a real-world scenario, if you need more efficient enqueue and dequeue operations, you might consider using a linked list implementation for the queue.