Stacks

Stacks are impossible to escape in development. Fortunately, they're also incredibly easy! We'll implement the Stack abstract data type in JavaScript using TDD and get the rundown of how they work.

We're working on inlining examples! Until then, please find the examples here on GitHub.

Stacks

Stacks are one of those data structures that are fundamental to understanding how modern languages and computers work. It's a topic, much like Sets, that I can just sit and ramble off examples and usage for what may seem like several episodes. However, I'll leave most examples for you to Google. Instead, we're going to focus on what a stack is, and why it is useful.

Drawing Example

The Stack abstract data type is a collection of data, much like an array, but with a focused purpose. Let's think of a box holding a stack of papers. If you put a piece of paper on top, that will be the first piece of paper you take off to get to other pieces of paper. So if we put pieces of paper with 1, 2, 3 on it, we will get them back in reverse order - 3, 2, 1. This is commonly referred to as Last In, First Out, or LIFO for short. This is also representative of the two primary operations of a stack, push, which adds something to the top of the stack, and pop which removes the top-most item from a stack.

Some languages come with their own implementations of stacks, and some come with multiple. Much like sets or tuples, the underlying data structure and implementation can have many variations. In this lesson we're going to stick with a simple array-based implementation in JavaScript.

I've already created a test suite here which we can run through quickly to take another look at how our stack should operate.

Spec Write ups

In our comment at the top we can see the 6 pieces of functionality that our stack will have. The first three are there to help us construct and learn information about the stack. Create will simply be our constructor, size will let us know how many elements are in our stack, and empty tells us whether our stack has any elements or not.

The bottom three make up what it means to be a stack. Push will add a new element to the top of our stack as we mentioned before, pop will remove the top-most element and return it, and this new function peek will return the top-most element, but not remove it from the stack. This isn't necessary to create a stack, but you'll find most implementations support it because sometimes you want to know what the next element is without removing it and putting it back.

Specs

Okay so let's look at this first test. Our test subject, a newly created stack, is expected to have a size of 0, which means that it should be empty. This should be really straight forward to write. At the top on line 2 we can see that I'm importing Stack from index.js, so lets jump there quickly to see what our implementation currently has.

And here we can see that I've already defined the class Stack for us and I've created empty functions for each of the methods we need to implement. This is largely so that we can skip the test errors showing that we don't have a method defined so that we can get into more exciting things.

Size

Let's give our first spec a try... and we can see that while we expected the size to be 0, we got back undefined because we aren't returning anything from size. So up in the constructor I'm going to define a property on our object named entries and that will be an empty array, which we are going to use for the internal storage of our stack. Then down in size I am going to return the length of the entries array.

constructor() {
  this.entries = [];
}

size() {
  return this.entries.length;
}

Empty

Okay running the test again shows that we've made it past that assertion, but now empty is returning undefined rather than true or false. So we'll jump down to our empty function and return whether this.size() is equal to 0. Great, now that test is passing. The next test states that an empty stack should return undefined if we peek at the top entry since there is nothing there. Since we already return undefined implicitly from these two functions, we know these will already pass for the time being, so we'll wait to run them until the rest of the implementation is built.

empty() {
  return this.size() === 0;
}

Adding items

So let's jump down to our adding items block. Note here that before every test we are pushing a single entry onto a new test subject. This value is the string 'Hi'. The first test in this block states that the stack should know its size and that it is not empty. Let's run the tests to see how that goes currently. Okay we're seeing that while we expected the size to be one, it is actually 0. Let's fix that by jumping back over to index.js and implementing our push method. This one is easy, we'll tell our entries array to push the value onto the end. And then I guess for the sake of it we'll return this to allow for push to be chained. Rerunning the test shows that this is successful, so let's move onto the next.

push(x) {
  this.entries.push(x);
  return this;
}

Peek

Here we're testing that peek can look at the top value of a stack, and will not effect the size of the stack by doing so. We're verifying that it's the top-most value here by pushing a second value, 'Bye', onto the stack at the top of the spec.

Running this spec shows that subject.peek() is returning undefined rather than 'Bye', so we should implement our peek method next. Since the top of our stack is the end of our array, we are going to return the last element of our entries array, by indexing into it with the length of the array minus one. Rerunning the test shows this to be successful, so we can move on to our last test.

peek() {
  return this.entries[this.entries.length - 1];
}

Pop

This test is demonstrating that we can pop the top value of our stack, so we are pushing a second value on again, poping a value back off and storing it to val. Then we are asserting that val will equal Bye and the size will be 1. Let's run all the tests this time to make sure everything is still green and see if this one fails. Yup! And we can see that val is undefined rather than Bye, so lets implement Pop next.

First we will save the value of peek to the variable val. Next we are going to call splice on our entries array, and we will use -1 to specify the end of the array, and the second value will be 1 because we only want to remove one value. Finally we will then return val. Running the test shows that we pass, but I want to explain why this works and show a slight variation because JavaScript is weird. splice modifies the array directly, it mutates it. It removes however many elements we specified and returns them as an array. So another way we could write this is as a one-liner, returning the first element returned from our splice operation. Running the test shows that this still passes. While this is succinct, I'm going to leave the original implementation in place because it is very easy to look at this implementation and not notice that it is doing two different operations in one.

pop() {
  const val = this.peek();

  this.entries.splice(-1, 1);

  return val;
}

Examples

So with all of our tests passing, let's take a minute to open a REPL, import our class, and try to do something interesting with it.

const Stack = require('./index')

A while ago I was asked to do a code challenge where I would take a string of JSON tokens, and detect whether the string had balanced all tokens. Let me define two consts so we can determine what is valid and what is invalid. A valid string with balanced tokens would look something like this [{()()()(){}[]}]. Ignoring the fact that semantically that's invalid JSON, the idea is that all of the tokens are balanced. An imbalanced string might look something like this, [{()]}, where I have closed the right bracket before I've closed the inner curly braces.

const validString = '[{()()()(){}[]}]';
const invalidString = '[{()]}';

A stack is particularly well-suited for for determining whether tokens are balanced because we can store each reference to a new nesting level as a new entry in the stack. First let me paste in our tokens for opening and closing nesting levels as two additional consts, OPEN_TOKENS and CLOSE_TOKENS. You'll notice that I've aligned opening and respective closing tokens by index in their arrays. Other than general clarity, the reason will become evident soon.

const OPEN_TOKENS =  ['[', '{', '('];
const CLOSE_TOKENS = [']', '}', ')'];

Now lets define a function, matchingToken, that takes the token we'd like to compare, followed by the challenging token that in order to return true, needs to be a matching closing token.

We'll use indexOf on our openTokens array and pass in token to see if it is in that list. And then we'll do the same for our challenger token by seeing if it inside of the closeTokens array. If the token is found inside of open tokens, meaning it is anything but -1, and if the challenger token index matches the tokenIndex, then that means that the opening token matches the challenger token and we can return true. Otherwise there is no token match and the function will return false.

function matchingToken(token, challenger) {
  const tokenIndex = OPEN_TOKENS.indexOf(token);
  const challengerIndex = CLOSE_TOKENS.indexOf(challenger);

  return tokenIndex !== -1 && tokenIndex === challengerIndex;
}

Let's test this out by passing in two characters that are not in the token lists - x and y. And it returns false as it should. Let's make sure x and x fails, and it does. Now let's try opening bracket [ and closing paren ). Yup, that is false. How about with closing bracket }. And that returns true. Great!

So now we can create the next function, isBalanced, which will take a string of tokens and tell us whether it is balanced or not. First we'll explode the string into an array of tokens. Next we'll create a new instance of our stack called openStack and that'll be used to track how many tokens we've opened so that we can track nesting level and match the pairs accordingly. Then at the bottom of this function, we're going to return whether the stack is empty. If so, great, then that means every opening token had a matching closing token. Otherwise it'll return false.

function isBalanced(str) {
  const openStack = new Stack();
  const tokens = str.split('')

  return openStack.empty();
}

Next we're going to loop over each of our tokens via a forEach. We'll define a const named lastOpen that will hold our top-most element in the stack via peek for this loop. Then we can check to see what kind of token we have. If OPEN_TOKENS includes this token, then we will log out to the console that we're pushing this token onto the stack, then we will do what we said below by using push on openStack. Otherwise we're going to see if it is a matching token for our lastOpen token. If it is, we're going to log that we've found the closing token for the last open token and then we'll pop that token off the stack. Else we're just going to throw an error declaring that we have mismatched tokens between lastOpen and token.

function isBalanced(str) {
  const tokens = str.split('')
  const openStack = new Stack();

  tokens.forEach(function(token) {
    const lastOpen = openStack.peek();

    if (OPEN_TOKENS.includes(token)) {
      console.log(`Pushing open token ${token} to stack`);
      openStack.push(token);
    } else {
      if (matchingToken(lastOpen, token)) {
        console.log(`Closing token found ${token} for ${lastOpen}`);
        openStack.pop()
      } else {
        throw new Error(`Token mismatch! ${lastOpen}, ${token}`);
      }
    }
  });

  return openStack.empty();
}

Okay let's give it a try. As a refresher, invalidString is defined as such, where the last two tokens are closing their pairs out of order. when we check to see if this invalidString is balanced, we see that we pushed 3 tokens onto the open stack, found one closing token, and then raised an error that we had mismatch between an opening curl and a closing bracket. Great!

Now let's print out our validString again so we can see how many pairs there are, and now we'll check to see if it's balanced...Okay we have our first 3 opening tokens, then we close the paren immediately and do this for all 4 sets, then the curlies, then the brackets, and then we close our two surrounding tokens, so everything worked!

Hopefully you can see how easy using a stack made this problem. Without using stack like concepts it's a good bit more involved to track state. Most programming languages utilize stacks to handle function scoping and execution order into something called a call stack. This is even true for assembly language.

You may have seen examples showing the existence of the call stack in many languages if you've accidentally gotten stuck in an infinite loop and continued calling functions over and over, or if you've recursed improperly. For example, if I define a function foo, and call foo inside of it, then I execute foo(), I've kicked off infinite recursion, which thankfully JS will detect and terminate if the call stack limit is reached.

Middleware for web frameworks such as Rails for Ruby, Laravel for PHP, or Express for NodeJS are also executed in terms of a stack. While they work more like a call stack than actually using push/pop manually, the concept is the same. So long as you understand stacks, you can understand how middleware works. And as an additional bonus, understanding stacks will make learning recursion a lot easier.

Take some time to play around with stacks and see what kind of uses you can find for them in your day-to-day work!