How To Implement a Queue in JavaScript -- and Beat Arrays at Their Own Game

April 7th, 2020

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 for more on how they were able to optimize slow array methods.)

1. What's a Queue?
2. Why Might We Want to Use a Queue?
3. Implementing a Basic Queue
4. Head to Head Performance Battle: Queue vs. Array
5. Further Thoughts

# What's a Queue?

In computer science, a queue is a data structure, and one of the abstract data types. Specifically, it's a type of collection (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.)

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).

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

# Why Might We Want to Use a Queue?

As we learned, 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. 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:

The performance of .push() doesn't change much as the array grows, but .unshift() gets substantially slower. Chart by le_m on StackOverflow

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, 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.

# 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.

Copy
1function Queue() {
2  let data = {};
3  let head = 0;
4  let tail = 0;
5}

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.

Copy
1function Queue() {
2  let data = {};
3  let head = 0;
4  let tail = 0;
5
6  this.enqueue = function(item) {
7    data[tail] = item;
8    tail++;
9  };
10}

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.

Copy
1function Queue() {
2  let data = {};
3  let head = 0;
4  let tail = 0;
5
6  this.enqueue = function(item) {
7    data[tail] = item;
8    tail++;
9  };
10
11  this.dequeue = function() {
12    let item = data[head];
13    delete data[head];
14    head++;
15    return item;
16  };
17}

Trying it out

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

Copy
1let queue = new Queue();
2queue.enqueue('one');
3queue.enqueue('two');
4queue.dequeue(); // one
5queue.enqueue('three');
6queue.dequeue(); // two
7queue.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!

# 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.

The below code block is live-rendering React (scroll to below the code block to see our test component -- it's the white rectangle stuck to the bottom of the code block).

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.

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;
  };
}
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;
}
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>
  );
};
render(<TestArea />);

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 maginitude 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.

# 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)?