Implementing Queues with NodeJS and Javascript

Job queues, message buffers, fair processing — FIFO: first in, first out. push + shift works until the queue gets huge.

What you'll learn:

• enqueue / dequeue with an array
• Why shift() can hurt at scale
• When a linked list helps
• BFS (ep. 14) as a queue in the wild

Prerequisites: stacks (ep. 4) and linked lists (ep. 3).

Queue (FIFO): arrays in practice

Dealing with Sequential Data

Queues are one of the main data structures and one of the most used by a lot of softwares to deal with sequential processes and stuff like that. Queues follow the FIFO principle, which means, first in, first out. In other words the first element to get to the queue will be the first to be removed or processed.

Implementation

Queues like I said above have to be an structure that adds new elements as the last element and removes/processes starting from the first position (index).

Just like Stacks, queues can be implemented using arrays with NodeJS/Javascript. A basic implementation should have functions (or methods) such as: enqueue, dequeue, peak or get to check the first element and so on...e.g:

class Queue {
  constructor() {
    this.items = []
  }
 
  // Adds an element to the queue
  enqueue(element) {
    this.items.push(element)
  }
 
  // Removes the first element of the queue
  dequeue() {
    if (this.isEmpty()) return 'Underflow' // queue is empty
    return this.items.shift()
  }
 
  // Get the first element of the queue (without removing it)
  front() {
    if (this.isEmpty()) return 'No elements in Queue'
    return this.items[0]
  }
 
  // Check if the queue is empty
  isEmpty() {
    return this.items.length === 0
  }
 
  // Logs the queue
  printQueue() {
    let str = ''
    for (let i = 0; i < this.items.length; i++) str += this.items[i] + ' '
    console.log(str)
  }
}

Edge cases: shift() is O(n)

Each dequeue with shift() moves every element. At millions of items, use a head index, a linked list, or a library queue.

Why not pop(0)? Also O(n). FIFO at index 0 is the painful part of array-based queues.

TL;DR — Queue

Next steps

• Implementing Trees
• BFS and DFS

Before you go

Where have you used a real queue — Bull, SQS, or a home-grown array? Comment the gotcha that bit you.