DEV Community: Matt Popovich

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

Matt Popovich — Wed, 08 Apr 2020 15:49:27 +0000

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

What's a Queue?
Why Might We Want to Use a Queue?
Implementing a Basic Queue
Head to Head Performance Battle: Queue vs. Array
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.

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.

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.

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.

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!

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

// 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'));

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.

# Further Thoughts

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

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?
How might we add other basic queue methods, like .length() or .peek() (return the head of the queue without removing it)?

Understanding Closures in JavaScript

Matt Popovich — Fri, 13 Mar 2020 22:49:44 +0000

What's a Closure?
Uses for Closures
How Might This Trip Us Up?

# What's a Closure?

When you declare a function inside another function, a closure is the new environment created by combining the inner function with references to all variables available to it from outer scopes (this concept of all scopes accessible from a certain area is known as the lexical environment).

In other words, in a closure, all variables accessible to the inner function -- including variables declared outside the function itself -- remain accessible to it, even when that inner function is removed and called in some other context. The inner function remembers all the stuff it has access to at the time of its declaration.

Let's look at an example:

let makeSayFullNameFunction = () => {
  let lastName = `Skywalker`;
  return (firstName) => {
    return `${firstName} ${lastName}`;
  };
};

let sayFullName = makeSayFullNameFunction();
sayFullName(`Luke`); // Luke Skywalker

Here, lastName is locally scoped to makeSayFullNameFunction. So it might seem that when we pull out the returned function as sayFullName and call it, we'll get an error, because it relies internally on lastName, but lastName isn't accessible from the global scope.

But in fact, this works just fine. When the inner function is created, lastName is enclosed (or closed over) into the closure of the inner function, so it is considered in scope no matter where the function is called.

For the purposes of calling the inner function, this:

let makeSayFullNameFunction = () => {
  let lastName = `Skywalker`;
  return (firstName) => {
    return `${firstName} ${lastName}`;
  };
};

...is equivalent to this:

let makeSayFullNameFunction = () => {
  return (firstName) => {
    let lastName = `Skywalker`;
    return `${firstName} ${lastName}`;
  };
};

The main benefit of closures is that they allow us to compose more modular programs. We don't have to stuff everything a function needs into that function to ensure it'll be able to access everything it needs in another environment, as we're about to see.

# Uses for Closures

1. When a Function Returns a Function

Let's look at our example from above again:

let makeSayFullNameFunction = () => {
  let lastName = `Skywalker`;
  return (firstName) => {
    return `${firstName} ${lastName}`;
  };
};

let sayFullName = makeSayFullNameFunction();
sayFullName(`Luke`); // Luke Skywalker

Even though lastName doesn't appear to be in scope when sayFullName is called, it was in scope when the function was declared, and so a reference to it was enclosed in the function's closure. This allows us to reference it even when we use the function elsewhere, so that it's not necessary to stuff everything we need in scope into the actual function expression.

2. When a Module Exports a Function

// sayName.js

let name = `Matt`;

let sayName = () => {
  console.log(name);
};

export sayName;

// index.js

import sayName from '/sayName.js';

sayName(); // Matt

Again, we see that even though name doesn't appear to be in scope when sayName is called, it was in scope when the function was declared, and so a reference to it was enclosed in the function's closure. This allows us to reference it even when we use the function elsewhere.

3. Private Variables and Functions

Closures also allow us to create methods that reference internal variables that are otherwise inaccessible outside those methods.

Consider this example:

let Dog = function () {
  // this variable is private to the function
  let happiness = 0;

  // this inner function is private to the function
  let increaseHappiness = () => {
    happiness++;
  };

  this.pet = () => {
    increaseHappiness();
  };

  this.tailIsWagging = () => {
    return happiness > 2;
  };
};

let spot = new Dog();
spot.tailIsWagging(); // false
spot.pet();
spot.pet();
spot.pet();
spot.tailIsWagging(); // true

This pattern is only possible because references to happiness and increaseHappiness are preserved in a closure when we instantiate this.pet and this.tailIsWagging.

# How Might This Trip Us Up?

One big caveat is that we have to remember we're only enclosing the references to variables, not their values. So if we reassign a variable after enclosing it in a function...

let name = `Steve`;

let sayHiSteve = () => {
  console.log(`Hi, ${name}!`);
};

// ...many lines later...

name = `Jen`;

// ...many lines later...

sayHiSteve(); // Hi, Jen!

...we might be left with an unwanted result.

In ES5, this often tripped up developers when writing for loops due to the behavior of var, which was then the only way to declare a variable. Consider this situation where we want to create a group of functions:

var sayNumberFunctions = [];

for (var i = 0; i < 3; i++) {
  sayNumberFunctions[i] = () => console.log(i);
}

sayNumberFunctions[0](); // Expected: 0, Actual: 3
sayNumberFunctions[1](); // Expected: 1, Actual: 3
sayNumberFunctions[2](); // Expected: 2, Actual: 3

Though our intention is to enclose the value of i inside each created function, we are really enclosing a reference to the variable i. After the loop completed, i's value was 3, and so each function call from then on will always log 3.

This bug arises because var (unlike let) can be redeclared in the same scope (var a = 1; var a = 2; is valid outside strict mode) and because var is scoped to the nearest function, not the nearest block, unlike let. So each iteration was just changing the value of a single global-scope variable i, rather than declaring a new variable, and that single variable was being passed to all of the created functions.

The easiest way to solve this is to replace var with let, which is block-scoped to each iteration's version of the loop block. Every time the loop iterates, i declared with let will be a new, independent variable scoped to that loop only.

var sayNumberFunctions = [];

for (let i = 0; i < 3; i++) {
  sayNumberFunctions[i] = () => console.log(i);
}

sayNumberFunctions[0](); // 0
sayNumberFunctions[1](); // 1
sayNumberFunctions[2](); // 2

But what if for some reason we can't use let? Alternatively, we could work around this problem by changing what's being enclosed:

var sayNumberFunctions = [];

for (var i = 0; i < 3; i++) {
  let newFunction;

  (function(iInner){
    newFunction = () => console.log(iInner);
  })(i);

  sayNumberFunctions[i] = newFunction;
}

sayNumberFunctions[0](); // 0
sayNumberFunctions[1](); // 1
sayNumberFunctions[2](); // 2

We can't use let, so we have to find a new way to enclose a unique value into newFunction. Since var is function-scoped, we'll need to declare another function and then immediately invoke it. Since we're declaring and invoking a new function on each iteration, our variable iInner is being redeclared as a unique variable each time, so we're now enclosing a unique variable with its own unique value on each pass, preserving the value we want.

As you've probably noticed, forcing the developer to use closures to detangle local variables from the global state is less than ideal. This was a major impetus for the behavior of let in ES6.

But it's still good idea to understand how closures work, and to keep in mind that they don't freeze the lexical environment's values; they only preserve references to variables that are in scope.

How (and Why) To Implement a Stack in JavaScript

Matt Popovich — Thu, 12 Mar 2020 23:02:37 +0000

What's a Stack?
Implementing a Basic Stack
Preventing Stack Underflows & Overflows
Why Would We Want to Use a Stack?

# What's a Stack?

In computer science, a stack is a data structure, specifically an abstract data type. It's a type of collection (meaning a list of items, similar to an array). What makes a stack distinct is that it's constrained by specific rules governing how items can be added and removed.

A stack only allows items to be added to, or removed from, one end of the list (the top of the stack). This is known as Last In, First Out. Items are added with a push() operation and removed with a pop() operation.

Think of it like a stack of pancakes:

You can push a pancake onto the top end of the stack...

...and you can pop a pancake off of the top end of the stack...

...but you can't add pancakes to, or remove pancakes from, the middle of the stack or the bottom end of the stack. Otherwise they'll go flying.

# Implementing a Basic Stack

In its most basic implementation, a stack has to keep track of two internal variables:

A number representing the size of the stack, and
A hash table (in other words, an object) representing the data in the list.

To begin implementing our stack, we'll need to set these:

function Stack () {
  this.size = 0;
  this.data = {};
}

Implementing `.push()`

Because the hash table is zero-indexed, the size value is always one greater than the last value that was added to the hash table. Whenever we push a new value onto the hash table, we'll add the data to the hash table, keyed by current size, and then increment the size value.

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }
}

Now, we can push values onto the stack, and view its size:

let stackOfOnes = new Stack();
stackOfOnes.push(1);
stackOfOnes.push(1);
stackOfOnes.push(1);
console.log(stackOfOnes.size); // 3

Implementing `.pop()`

To pop off the last value, we access it from the hash table using the size value to determine its key, delete it from the hash table, decrement the size value, and return the retrieved value.

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Now, we've got a basic functional stack: we can push values onto the stack, pop them off the stack, and view its size.

let fruitStack = new Stack();
fruitStack.push('apple');
fruitStack.push('banana');
fruitStack.push('orange');
console.log(fruitStack.size); // 3
let lastFruit = fruitStack.pop();
console.log(lastFruit); // 'orange'
console.log(fruitStack.size); // 2

# Preventing Stack Underflows & Overflows

Now, you're probably already starting to realize that we could run into some issues here. What happens, for example, if we try to to .pop() a value off an empty stack?

Attempting to pop an empty stack is called a stack underflow. You've probably also heard of a stack overflow, which is when a stack's size exceeds a certain limit. Stacks usually set a predetermined bound in order to prevent infinite-loop bugs that attempt to push items onto the stack over and over indefinitely.

To make our stack more resilient, let's add some guardrails against underflows and overflows.

First, we'll add a check in .pop() to ensure we aren't popping an empty stack:

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    if (this.size === 0) {
      console.log(`Stack underflow!`);
      return;
    }
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Next, we'll set an internal bound variable when the stack is created, and add a check in .push() to ensure we aren't exceeding that bound.

function Stack (bound = 10) {
  this.size = 0;
  this.bound = bound;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    if (this.size >= this.bound) {
      console.log(`Stack overflow!`);
      return;
    }
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    if (this.size === 0) {
      console.log(`Stack underflow!`);
      return;
    }
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Now we've got a more resilient structure that will prevent invalid pushes and pops:

let nsync = new Stack(5);
nsync.pop(); // Stack underflow!
nsync.push(`Justin Timberlake`);
nsync.push(`Lance Bass`);
nsync.push(`Joey Fatone`);
nsync.push(`JC Chasez`);
nsync.push(`Chris Kirkpatrick`);
nsync.push(`Michael Bublé`); // Stack overflow!

We don't like that dirty pop.

# Why Would We Want to Use a Stack?

1. Performance? (Probably not)

In some languages, a stack has the advantage of being more performant than alternative data structures like arrays. However, JavaScript arrays are optimized so that you're not likely to be able to beat them at efficiency.

Array.prototype.push() and Array.prototype.pop() are already O(1) efficient. So no matter the size of the array, it won't take any longer to push items onto or pop them off of the array.

However, this isn't true about other array methods. When we're not only appending to and removing from one end of an array, we lose the stack-like O(1) efficiency. For example, .shift()ing an item to the front of an array -- analogous to the bottom of the stack here -- is only O(n) efficient, because every single item in the array must have its index incremented. With a new array[0], the item previously at array[0] becomes array[1], the item at array[1] becomes array[2], etc. (Technically, this isn't strictly speaking true in JavaScript due to clever optimizations, but it's how it works conceptually, and the optimizations don't change the O(n) efficiency.)

2. Enforcing LIFO

Okay, so arrays' .push() and .pop() methods are pretty efficient in JavaScript. But that doesn't mean stacks are useless. They could be the right choice in situations where you only care about the value most recently added to a list, and you want to enforce that only that value can be accessed.

Say you're building an undo functionality into your drawing web app. Every time a user makes a change to their artwork, you need to push the previous state of the artwork onto a list. Every time a user undoes an action, you need to pop that previous state off the list, so that it becomes the active state of the artwork again.

In this case, it's likely we don't care about accessing artwork states other than the most recently added one. We don't care about needing to access the initial state of the artwork, a blank canvas (this would be the bottom of the stack). And the user isn't ever going to ask us to jump directly to the state it was exactly thirty-seven actions back (so we don't need to access by index, i.e. undoStates[37]). Only the last action ever matters.

A stack could be the right choice for this use case because it enforces the Last In, First Out (LIFO) access order, preventing less efficient O(n) array methods.