How To Implement a Queue in JavaScript—and Beat Arrays at Their Own Game
Tags: queue, datastructures, javascript, computerscience
Published: 2020-04-08 15:49:27

---
title: How To Implement a Queue in JavaScript—and Beat Arrays at Their Own Game
published: true
description: Learn about the Queue abstract data type, learn how to implement one in JavaScript, and see how it makes adding and removing items even faster than native JavaScript arrays.
tags: queue, data structures, javascript, computer science
canonical_url: https://popovich.io/2020/2020-04-07-queue-javascript/
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/vdc8kke6o6xofzp6x6u4.jpg
---

***

## A note about browsers, before we begin

Firefox and Safari handle `shift`/`unshift` in a much more performant way under the hood than Chromium, so the performance test at the end is best viewed in Chrome or Edge! Otherwise the browser optimizes the operations so that both data structures are about even. (See [here](https://lannonbr.com/blog/2020-01-27-shift-optimizations/) for more on how they were able to optimize slow array methods.)

***

1. [What's a Queue?](#what)
2. [Why Might We Want to Use a Queue?](#why)
3. [Implementing a Basic Queue](#how)
4. [Head to Head Performance Battle: Queue vs. Array](#performance)
5. [Further Thoughts](#further)

<a name="what"></a>

## [#](#what) What's a Queue?

In computer science, a **queue** is a data structure, and one of the [abstract data types](https://en.wikipedia.org/wiki/Abstract_data_type). Specifically, it's a type of [collection](<https://en.wikipedia.org/wiki/Collection_(abstract_data_type)>) (meaning a list of items, similar to an array). What makes a queue distinct is that it's constrained by specific rules governing how items can be added and removed, much like a stack. _(If you're not sure what a stack is, check out my previous post, [How (and Why) To Implement a Stack in JavaScript](https://dev.to/mattpopovich/how-and-why-to-implement-a-stack-in-javascript-227b).)_

While a stack enforces a Last In, First Out (LIFO) order, where items can only be added to or removed from a _single end_ of the stack, a queue enforces a **First In, First Out (FIFO)** order, where items can only be inserted into one end of the queue (the **tail**) and only removed from the _other_ end of the queue (the **head**).

<br />

![Balls being added and removed in a Last In, First Out order to a stack, and balls being added removed in a First In, First Out order to a queue](https://dev-to-uploads.s3.amazonaws.com/i/vdc8kke6o6xofzp6x6u4.jpg)

<br />

Inserting an item into a queue is called an **enqueue** operation, and removing an item is called a **dequeue** operation.

<a name="why"></a>

## [#](#why) Why Might We Want to Use a Queue?

[As we learned](https://dev.to/mattpopovich/how-and-why-to-implement-a-stack-in-javascript-227b), a stack doesn't provide much of a performance benefit over a native JavaScript array, because the `Array.prototype.push()` and `Array.prototype.pop()` methods have already been optimized to provide a stack-like [nearly-**O(1)** efficiency](https://stackoverflow.com/questions/697918/what-does-o1-access-time-mean). This means that no matter how large the array is, push and pop operations should take around the same amount of time.

On the other hand, `Array.prototype.shift()` and `Array.prototype.unshift()` are closer to **O(n)** efficient, meaning the greater the length of the array, the longer they will take:

<br />

![Two charts showing push performance barely changing over time and unshift performance increasing exponentially over time](https://dev-to-uploads.s3.amazonaws.com/i/0n9jcpic3xcyg2cs39nw.png)
_The performance of `.push()` doesn't change much as the array grows, but `.unshift()` gets substantially slower. [Chart by le_m on StackOverflow](https://stackoverflow.com/questions/44031591/performance-of-array-push-vs-array-unshift)_

<br />

This is because every single item in the array must have its index incremented when an item is added to, or removed from, the front of an array. With a new `array[0]`, the item previously at `array[0]` becomes `array[1]`, the item previously at `array[1]` becomes `array[2]`, etc. _(Technically, [this isn't strictly speaking true in JavaScript due to some clever optimizations](https://stackoverflow.com/questions/44031591/performance-of-array-push-vs-array-unshift), but it's how it works conceptually)_.

A queue provides an intriguing alternative: by limiting ourselves to a First In, First Out method of interacting with a list, could we reduce that **O(n)** to an **O(1)** efficiency?

Let's find out.

<a name="how"></a>

## [#](#how) How to Implement a Basic Queue

Conceptually, a stack allowed us to keep its add/remove operations efficient by keeping track of the index of the item at one end of the list. So with a queue, since we're interacting with _both_ ends of the list, we'll need to keep track of _both_ ends' indices.

Let's start by creating a function with a hash table (another term for an object) to store the data in the queue, and the indices for the queue's tail and head.

```js
function Queue() {
  let data = {};
  let head = 0;
  let tail = 0;
}
```

### Implementing `.enqueue()`

To add an item to the queue, we'll simply add it as a property on the data object at the next tail index, and then increment our tail index integer.

```js
function Queue() {
  let data = {};
  let head = 0;
  let tail = 0;

  this.enqueue = function(item) {
    data[tail] = item;
    tail++;
  };
}
```

### Implementing `.dequeue()`

Similarly, to remove an item from the queue, we'll simply retrieve and delete it from the data object at the head index, and then increment our head index integer and return the item.

```js
function Queue() {
  let data = {};
  let head = 0;
  let tail = 0;

  this.enqueue = function(item) {
    data[tail] = item;
    tail++;
  };

  this.dequeue = function() {
    let item = data[head];
    delete data[head];
    head++;
    return item;
  };
}
```

### Trying it out

Okay! Let's see if our queue works properly.

```js
let queue = new Queue();
queue.enqueue('one');
queue.enqueue('two');
queue.dequeue(); // one
queue.enqueue('three');
queue.dequeue(); // two
queue.dequeue(); // three
```

Lookin' good! We can add items and remove them, and even when those operations are intermingled, the items come out in the same order they were added. Time to put it to the test!

<a name="performance"></a>

## [#](#performance) Head to Head Performance Battle: Queue vs. Array

This is it. The big show. The match you've been waiting for. The Battle of the Lists.

In one corner: the native JavaScript array. One list to rule them all, a Swiss army knife of methods -- but is it just too big and slow to compete against a lean young upstart?

And in the other corner: the challenger, a basic queue we wrote in only 17 lines of code. Is is it too small to go toe-to-toe with the defending champ? We're about to find out.

In the code below, we will:

- Declare our Queue function
- Set up a `testList` function that will enqueue onto, and then dequeue from, a given list a certain number of times, using `performance.now()` to determine how long the operations took.
- Build a small React component that allows us to input the number of times to enqueue/dequeue, allows us to click a button to start tests using both a native JavaScript array and our `Queue`, and then displays the time in milliseconds to enqueue/dequeue the given number of items.

```jsx
// set up our Queue
function Queue() {
  let data = {};
  let head = 0;
  let tail = 0;

  this.enqueue = function(item) {
    data[tail] = item;
    tail++;
  };

  this.dequeue = function() {
    let item = data[head];
    delete data[head];
    head++;
    return item;
  };
}

// test a list structure's enqueue and dequeue functions a certain number of times
function testList(count, enqueueFn, dequeueFn) {
  let startTime = performance.now();
  for (var i = 0; i < count; i++) {
    enqueueFn();
  }
  for (var i = 0; i < count; i++) {
    dequeueFn();
  }
  let endTime = performance.now();
  return endTime - startTime;
}

// React component to display test controls and results
const TestArea = props => {
  const [count, setCount] = React.useState(500);
  const [resultQueue, setResultQueue] = React.useState(0);
  const [resultArray, setResultArray] = React.useState(0);

  const runTest = () => {
    let queue = new Queue();
    let array = [];

    let nextResultQueue = testList(
      count,
      () => queue.enqueue(1),
      () => queue.dequeue()
    );

    let nextResultArray = testList(
      count,
      () => array.unshift(1),
      () => array.pop()
    );

    setResultQueue(nextResultQueue);
    setResultArray(nextResultArray);
  };

  return (
    <div style={{ padding: `0 20px 40px` }}>
      <h3 style={{ color: 'steelblue' }}>Performance Battle</h3>

      <div>
        Number of enqueues / dequeues:
        <input
          type="number"
          value={count}
          onChange={e => setCount(e.target.value)}
        />
      </div>

      {count > 99999 && (
        <div style={{ color: 'red' }}>
          Warning! This many enqueues / dequeues may slow or crash your browser!
        </div>
      )}

      <button style={{ margin: `0 0 20px` }} onClick={runTest}>
        Run test
      </button>

      <div>Queue: {resultQueue}ms</div>
      <div>Array: {resultArray}ms</div>
    </div>
  );
};

ReactDOM.render(<TestArea />, document.querySelector('#app'));
```

{% codepen https://codepen.io/mattpopovich/pen/xxwKywe %}

Try running the test with 5000 enqueues/dequeues, then 20000, and finally 50000, and see what happens.

.

.

.

.

.

Did you try it?

.

.

.

.

.

Neat, huh?

Even increasing the number by _orders of magnitude_ barely budges the time it takes for the queue operations to finish, while the array operations start neck-and-neck with the queue at a low number, but quickly start to balloon as it gets larger.

Can you believe it? We beat native JavaScript arrays at their own game.

It's official: Queues are FIFO World Champs.

<a name="further"></a>

## [#](#further) Further Thoughts

...left, as they say, as an exercise to the reader:

1. With this implementation, we're incrementing the head / tail indexes indefinitely. What problems might this eventually cause? How might we deal with them in the most runtime-efficient (smallest Big O) way?

2. How might we add other basic queue methods, like `.length()` or `.peek()` (return the head of the queue without removing it)?