Raul Melo

Posted on Aug 26, 2020 • Edited on Jul 6, 2021 • Originally published at raulmelo.dev

Data Structure with JavaScript: Stacks

#computerscience #javascript #introduction #datastructure

Hello, devs.

This is the first article of many I want to write to document my studies of algorithms and data structure.

After I failed in an interview because of a sorting algorithm, I've decided to dive deep into some computer science concepts I've learned in the college.

Today's posts will be about the data structure Stack. I hope you can learn what's it and mainly how to implement this data structure in JS.

Table of Content

What is a Stack
- Last In, First Out (LIFO) order
- Methods
Implementation
- Stack
- Stack.push
- Stack.pop
- Stack.peek
- Stack.isEmpty
- Stack.size
- Stack.clear
Usage
Conclusion
References

What is a Stack

As I already told you before, Stack is a data structure which represents... guess what? a regular stack of things.

Imagine you're working in a kitchen as a kitchen porter and unfortunately, the washing machine just broke. Now you have to wash all plates by hand 😢.

The waiters and waitresses are bringing the client's plates to the kitchen and you have to gather all of them and organize in a way to make it easier to wash.

The best way to do that is stacking one plate on top of each other:

How are you going to start this duty?

Yes, that's correct, with the first plate on the top of the stack.

After finish that, you create another stack of clean plates until your task is done.

Last In, First Out (LIFO) order

The problem you just solved in the kitchen had a well-known sequence called LIFO, or Last In, First Out. Still, in the example, the last plate you stack is the first one you're gonna wash.

In that sense, the data structure Stack can be used in any problem you might solve that you need to create a list of things in a specific sequence and then removing them from the last added to the first.

Later in this article, we'll implement 2 exercises, one script to wash the plates for us and another (a bit more practical) that converts numbers to binary.

Methods

The Stack methods are divided by essential and non-essential:

Essential

These two methods are a must in any Stack implementation, does not matter what programming language you're using:

push - to add an element;
pop - to remove the latest added element.

Non-essential

Also, there are a couple of nice-to-have methods which can be different across other languages, especially in the naming. They are:

peek - to get what is the element on top of our stack (does not remove it though);
isEmpty - to check if our stack is empty;
size - to check how many elements we have there;
clear - to completely clean up the stack.

It does not seem complex, right? And trust me, it isn't. Let's check now how we would implement that.

Implementation

To implement a Stack we'll be using our old friend Array, after all, a Stack is just a vertical list of things, right?

To get some encapsulation, I'll use regular functions but in a Factory way so that any instance of the stack will have direct access to the items.

It can be also be written using class syntax our the old school function + its scope, but again, doing in that way the instances will have access to the items list which isn't the desired behavior unless you're reading this article in the future and private attributes in class are already in the language (or just using a babel preset).

https://github.com/tc39/proposal-class-fields#private-fields

At the end of this article, I'll write those 2 other versions if you're curious about it.

Stack (basic structure)

So let's start by creating our function:

function Stack() {
  let items = [];

  return {};
}

Pretty simple. We:

creates our function Stack (camel case because it represents a class);
creates an array called items where all our data will be stored.
return an (temporary) empty object but which exposes the Stack methods we want to make public.

Stack.push

Let's start one of the required methods Stack.push method.

Since we're using an array to control our stack elements, we can just use the native array method push:

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  return {
    push,
  };
}

Very forwarded. We:

create an internal function called push which accepts an element and push it into the items list;
make this function publicly available so we can do myStack.push(<element>).

Stack.pop

Time to implement the other required method: Stack.pop.

Here we'll also be using the native Array.prototype.pop, that removes the last element in a list and return this removed value:

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  function pop() {
    return items.pop();
  }

  return {
    push,
    pop,
  };
}

Stack.peek

Now it's time for the nice-to-have-methods. Let's start by implementing the Stack.peek method.

Here we want to return the element on top of our stack, or, the last element in our list WITHOUT removing it. It's just for a matter of knowing what's on the top.

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  function pop() {
    return items.pop();
  }

  function peek() {
    return items[items.length - 1];
  }

  return {
    push,
    pop,
    peek,
  };
}

If you are still learning JS, keep in mind that array indexes start at 0. If we have a list ['A', 'B', 'C'], it'll be represented by:

index 0: 'A'
index 1: 'B'
index 2: 'C'

However, list.length will be 3. If we want to pick the latest, we always need to get the length (3) and subtract 1 so then we respect the index 0-base from a JS list.

Stack.isEmpty

Next is the method Stack.isEmpty that will just evaluate if our stack (aka array) has a length equals zero:

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  function pop() {
    return items.pop();
  }

  function peek() {
    return items[items.length - 1];
  }

  function isEmpty() {
    return items.length === 0;
  }

  return {
    push,
    pop,
    peek,
    isEmpty,
  };
}

Stack.size

Then we have the Stack.size method that will be returning the length of our array.

The only difference between length and size is the naming convention commonly used in other languages (at least I couldn't find a good explanation, if you know, please leave a comment).

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  function pop() {
    return items.pop();
  }

  function peek() {
    return items[items.length - 1];
  }

  function isEmpty() {
    return items.length === 0;
  }

  function size() {
    return items.length;
  }

  return {
    push,
    pop,
    peek,
    isEmpty,
    size,
  };
}

Stack.clear

Next is Stack.clear that will simply throw away the current stack and replace it with an brand-new and empty one:

function Stack() {
  let items = [];

  function push(element) {
    items.push(element);
  }

  function pop() {
    return items.pop();
  }

  function peek() {
    return items[items.length - 1];
  }

  function isEmpty() {
    return items.length === 0;
  }

  function size() {
    return items.length;
  }

  function clear() {
    items = [];
  }

  return {
    clear,
    push,
    pop,
    peek,
    isEmpty,
    size,
  };
}

The reason I created items using let was to make this process easier. We could have some functional approach here but I don't see anything wrong with reassigning values in a controlled scope.

And that's it. Our data structure is done.

If you're curious to see this code using class or function this, check it here:

old school function scope syntax

function Stack() {
  this.items = [];

  this.push = function (element) {
    this.items.push(element);
  };

  this.pop = function () {
    return this.items.pop();
  };

  this.peek = function () {
    return items[this.items.length - 1];
  };

  this.isEmpty = function () {
    return this.items.length === 0;
  };

  this.size = function () {
    return this.items.length;
  };

  this.clear = function () {
    this.items = [];
  };
}

const stack = new Stack();

Be aware that items will not be private in stack instance, which means that doing stack.items will be possible to manipulate the list out of our "predefined rules".

class syntax

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

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

  isEmpty() {
    return this.items.length === 0;
  }

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

const stack = new Stack();

It has the same problem described in the old school function scope syntax, items will be available publicly.

There are a couple of ways to try to guarantee that until we don't have private fields natively but I won't dive deep into that in this post.

Usage

Now we have our Stack data implemented, let's try it out:

const stack = Stack(); // create a new stack (new instance of it)

console.log(stack.isEmpty()); // true
console.log(stack.size()); // 0

// Pushing up some values
stack.push("Zilmira");
stack.push("John");
stack.push("Joel");

console.log(stack.isEmpty()); // false
console.log(stack.size()); // 3
console.log(stack.peek()); // Joel

const removedElement = stack.pop();

console.log(removedElement); // Joel

console.log(stack.isEmpty()); // false
console.log(stack.size()); // 2
console.log(stack.peek()); // John

stack.clear();
console.log(stack.isEmpty()); // true
console.log(stack.size()); // 0

Nice, now we have a new type (custom) in our application where we can use it.

Examples

Ok, now we already now what is a Stack and have it implemented. Let's apply it into some problem solution.

Washing plates program

Imagine that now you're tired of washing plates by hand and will create a robot to do this duty for you.

Time to grasp our new data structure to solve that.

First, let's create our barebone function washPlates that receive a list of plates:

function washPlates(plates) {}

Then, we create a variable that hold how long it takes to wash a single plate (to avoid magical numbers) and also a stack of plates:

function washPlates(plates) {
  const timeToWashAPlateInMilliseconds = 2000; // Long but descriptive
  const plateStack = Stack();
}

Now, we have to fill our plateStack with all plates received. So let's iterate through it and add them to the stack:

function washPlates(plates) {
  const timeToWashAPlateInMilliseconds = 2000;
  const plateStack = Stack();

  plates.forEach((plate) => stack.push(plate));
}

Note that this logic could be implemented in many ways, like using the regular for or for...of loop for instance.

Then, let's just add some console messages to make easy to understand what's going on and start an iteration through our stack:

function washPlates(plates) {
  const timeToWashAPlateInMilliseconds = 2000;
  const plateStack = Stack();

  plates.forEach((plate) => stack.push(plate));

  console.log(`I have ${platesStack.size()} plates to wash!`);
  console.log("Starting the duty!");

  while (!platesStack.isEmpty()) {
    // do something
  }
}

Note that in our while will keep doing until the stack has items.

Now, we need to take the plate we're gonna wash and do the job.

To emulate that and make it easier to make this code runnable, I'll create a self-implemented sleep utility that will represent the act of washing the plate. But don't pay much attention to that.

// A code to block the execution after X time
function sleep(timeout) {
  return new Promise((resolve) => setTimeout(resolve, timeout));
}

async function washPlates(plates) {
  const timeToWashAPlateInMilliseconds = 2000;
  const plateStack = Stack();

  plates.forEach((plate) => stack.push(plate));

  console.log(`🤖 says: I have ${platesStack.size()} plates to wash!`);
  console.log("🤖 says: Starting the duty!");

  while (!platesStack.isEmpty()) {
    const currentPlate = platesStack.pop(); // Get the plate on the top
    console.log("🤖 says: Start washing plate:", currentPlate);
    await sleep(TIME_TO_WASH_A_PLATE_IN_MILLISECONDS); // Wash it
    console.log(`🤖 says: Plate ${currentPlate} done.`); // We're done with this plate
  }

  console.log("🤖 says: All plates are cleaned!");
}

To pause this function execution using sleep, I needed to make this function async and explicitly await until it's done.

So here we get the plate on the top of our platesStack to wash it using the pop method.

Now if we run this program passing 5 plates, we'll have:

washPlates([1, 2, 3, 4, 5]);

// 🤖 says: I have 5 to wash!
// 🤖 says: Starting
// 🤖 says: Start washing plate: 5
// 🤖 says: Plate 5 done.
// 🤖 says: Start washing plate: 4
// 🤖 says: Plate 4 done.
// 🤖 says: Start washing plate: 3
// 🤖 says: Plate 3 done.
// 🤖 says: Start washing plate: 2
// 🤖 says: Plate 2 done.
// 🤖 says: Start washing plate: 1
// 🤖 says: Plate 1 done.
// 🤖 says: All plates are cleaned!

Cool, right?

Of course, we could solve this problem in various ways but since our problem fits perfectly the Stack data structure, why not just give it a shot?

Decimal to binary problem

Ok, time to solve a more (not much) realistic problem. Let's implement a function that converts a decimal number and returns a string with the binary representation of it.

There are a few methods to do that and the one we're going to use is by division and it fits perfectly using Stack to solve that because we need to store the result operation in a LIFO sequence (it'll be clearer later).

If you want to learn in-depth how it works you can watch the following video:

In a nutshell, we'll divide the received decimal number by 2 using the Remainder operator (%) and store the rest (0 or 1) in a Stack until the number is zero.

After that we'll compose our binary popping out our stack.

Ok, let's starting by creating the function:

function decimalToBinary(decimal) {}

Then, let's create a new Stack and a few variables of control:

function decimalToBinary(decimal) {
  const binaries = Stack();

  let nextNumber = decimal;
}

Here:

binaries a stack which will hold the binary value from each division;
nextNumber will hold the next number we need to divide.

Then, let's vary a bit and use a do...while loop with the implementation:

function decimalToBinary(decimal) {
  const binaries = Stack();

  let nextNumber = decimal;

  do {
    let remainder = nextNumber % 2;
    binaries.push(remainder);

    nextNumber = Math.floor(nextNumber / 2);
  } while (nextNumber !== 0);
}

Here we:

creates a variable to hold the remainder of this operation (it could be done in a single line within the push);
pushes the remainder to our binary stack;
divides nextNumber by 2 (bi...nary) ignoring floating points with Math.floor

This loop will happen until nextNumber is something but 0, we don't want to divide 0, right?

Last part will be looping through our stack of binaries and create our result:

function decimalToBinary(decimal) {
  const binaries = Stack();

  let binaryResult = "";
  let nextNumber = decimal;

  do {
    let remainder = nextNumber % 2;
    binaries.push(remainder);

    nextNumber = Math.floor(nextNumber / 2);
  } while (nextNumber !== 0);

  while (!binaries.isEmpty()) {
    binaryResult += binaries.pop();
  }

  return binaryResult;
}

Here we:

create the variable binaryResult. I just moved it to the top to put together if all other variables;
loop through our stack until it becomes empty and concatenate all elements using the Assign addition operator (+=);
finally return the result.

Let's test it out:

console.log(decimalToBinary(123)); //> 1111011
console.log(decimalToBinary(332112)); //> 1010001000101010000

Real-world use cases

Both problems still seem a bit vague, I mean, when we need to implement a binary converter or fake software to washing plates, right?

While reading the real examples of Stack use, I found a common problem I believe a lot of people need to solve or already thought how to solve: "Undo" action.

Imagine you have a stack of elements and the user could simply remove them. A possible implementation would be pop the last element and hold it for a couple of sections. If the user clicks in a undo button, you just push this element again on top of your stack.

Another nice and advanced use case is in Redux dev tools. Every single action you dispatch is put into a stack. So if you want to go back and forth in a replay mode is just a matter of pushing and popping elements from the stack.

Conclusion

In this article, we learned what is a Stack, how to implement it in JavaScript, and most importantly using it to solve problems.

Think data structure as tools. As much bigger it's your toolbox, as much easier will be to solve a specific problem.

I hope Stack is in your toolbox now.

Thanks if you read until this point.

DEV Community