Queues in JavaScript

In computer science a queue is a linear data structure. The description sounds a bit esoteric but the concept is actually easy to grasp. You can imagine a scenario like this being a queue: camping in line outside the Apple store for a new iPhone. If you are the first one in line, you get the first iPhone. There are no cuts in line. If you are the first in line then you are the first one serviced. First In, First Out you could say.

A queue is exactly that; First In, First Out. In JavaScript there is no native implementation of a queue data structure, so we have to implement it ourselves.

// queue.js

class Queue {
  constructor() {
    this.data = [];
  }

  // Also referred to as enqueueing; could be named enqueue
  add(n) {
    return this.data.unshift(n);
  }

  // Also referred to as dequeueing; could be named dequeue
  remove() {
    return this.data.pop();
  }
}

module.exports = Queue;

The code above is how you could implement a queue in JavaScript. We use an array to store data for instances of our class, but we do not use array methods when operating on the instance! Instead we define our own instance methods to be used with a queue, using array methods inside the instance methods’ blocks to implement our intended functionality.

// A simple jest test to ensure that the queue is functioning as expected
// test.js

const Queue = require('./index');

test('Order of elements is maintained', () => {
  const q = new Queue();
  q.add(1);
  q.add(2);
  q.add(3);
  expect(q.remove()).toEqual(1);
  expect(q.remove()).toEqual(2);
  expect(q.remove()).toEqual(3);
  expect(q.remove()).toEqual(undefined);
});

// Visual representation of the test

// q = []
// [1]         q.add(1)
// [2, 1]      q.add(2)
// [3, 2, 1]   q.add(3)

// [3, 2, 1]   q.remove(), returns 1
// [3, 2]      q.remove(), returns 2
// [3]         q.remove(), returns 3
// []          q.remove(), returns undefined (array is empty)

To meet the First In, First Out methodology, we must always add a new unit of data to the beginning of the queue. If we instead used this.queue.push(n) in our add method, the new value would be cutting in line. The value next up to be returned if we called remove() would be the newest one we added. This incorrect implementation would actually be a stack (First In, Last Out), not a queue.

But why not just use an array if we are already using an array under the hood in our Queue class? Why do all this extra work? The answer is likely we were told to solve a specific problem using a queue by our interviewer. In lower level languages there are better reasons than “because I was told to”, such as lower memory allocation. Some other languages also provide a library or interface for the queue data structure, so implementing it wouldn’t require you to code the functionality.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.