JavaScript Data Structures: Queue

A queue is a data structure where items come out in the same order they went in. You add at one end, and you remove from the other end. We can implement one in JavaScript with a class that wraps an array.

Queues are similar to stacks, except the insertion point is different from the removal point.

This ordering is called First In, First Out (FIFO). Like any queue you can think of, for example at the restaurant, disco or when you’re waiting to enter into a concert hall. The first person to arrive is the first person served.

You reach for a queue whenever things must be processed in arrival order: jobs to run, messages to handle, requests to serve. The data structure guarantees nobody skips the line.

The implementation

Here is a possible implementation of a queue in JavaScript using private class fields, using an array as the internal storage:

class Queue {
  #items = []
  enqueue = (item) => this.#items.splice(0, 0, item)
  dequeue = () => this.#items.pop()
  isempty = () => this.#items.length === 0
  empty = () => (this.#items.length = 0)
  size = () => this.#items.length
}

The #items array is private, so nothing outside the class can reach in and reorder the items. That’s the whole point: the only way in is enqueue(), the only way out is dequeue().

enqueue() uses splice(0, 0, item) to insert the new item at the start of the array. dequeue() uses pop() to remove the item at the end, which is the oldest one. Oldest in, first out.

Using the queue

Here’s how to use it: you first initialize an object from the class, then you call its methods:

• enqueue() to add items
• dequeue() to get an item out of the queue

Example:

const queue = new Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.size() //3

queue.dequeue() //1
queue.dequeue() //2
queue.dequeue() //3

We added 1 first, and 1 came out first. FIFO in action.

Watch out for the empty queue

Calling dequeue() on an empty queue does not throw. It returns undefined, because that’s what pop() returns on an empty array.

If undefined is a value you could legitimately store, that’s a source of bugs. Check with isempty() before pulling:

if (!queue.isempty()) {
  const job = queue.dequeue()
}

One more note. Inserting at index 0 with splice() shifts every existing item, so it gets slower as the queue grows. For a few hundred items you’ll never notice. For a queue with millions of items, you’d want a linked list instead.