The Stack Data Structure in Javascript
So like, what’s a stack?
Asking this question you might hear answers like:
“A data structure that uses LIFO, Last In First Out”
Or
“Like a javascript array, the only thing you can do is to push and pop”
Or, if you’re on wikipedia…
“In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations, push and pop.” ¹
Or my personal favourite
“Do you even code bro?”
Yes I code bro, I code lots.
But what does all this mean and what sort of applications do data stacks have for me as a developer?
Let’s begin with an analogy.
You’re working in a shipping warehouse (not Amazon…) and you have an ever increasing amount of boxes. Not only that, these boxes are marked with a stern warning “FRAGILE, DO NOT STACK.”
But the boxes keep coming and you’re running out of room. So you and your coworkers come up with a system. Your system is simple but it has a few rules.
1. Boxes will be stacked and removed one at a time.
2. If a box near the bottom of the stack needs to be grabbed, every box above it will be removed one at a time.
3. Under NO circumstances, is anyone, EVER allowed to take any box from the stack unless it’s on the top.
4. Adding a box will be called a “PUSH. Removing a box will be called a “POP. You explain to your employees that this these terms should not be interpreted literally and careful attention should be paid to these fragile boxes.
The system works. You’re coworkers follow the rules and floor space triples at the warehouse. So it’s time to get back to coding…
In vanilla javascript quite a bit of this stack logic is written directly into the language.
Javascript has built in push and pop functions which work the same as any Last In, First Out data structure.
Here we have an array:
Let boxes = [“box1”, “box2”, “box3”]
//Let’s add a box to our stack.boxes.push(“box4)returns [“box1”, “box2”, “box3”, “box4”]
//And now let’s take it off.boxes.pop()
returns [“box1”, “box2”, “box3”]And again
boxes.pop()
returns [“box1”, “box2”]
You get the picture.
Note* The example below is simplified as Javascript arrays violate many of the rules of our box stacking system. An implementation that uses Javascript classes to strictly follow the stack structure can be found here:
https://blog.cloudboost.io/playing-with-data-structures-in-javascript-stack-a55ebe50f29d
So where can I use this as a javascript developer?
One implementation of the stack method can be used to transition between different modes inside a react app. Looking at the code we might think it looks very different from the code above but actually we are doing pretty much the same thing.
import { useState } from “react”;export default function useVisualMode(initial) {const [mode, setMode] = useState(initial);const [history, setHistory] = useState([initial]);function transition(mode, replace = false) { if (replace) { setMode(initial => (mode) ) setHistory([history[0], mode] } else { setMode(initial => (mode) ) setHistory([…history, mode])}}function back(mode) { if (history.length > 1) { history.splice(history.length -1) setMode(mode =>(history[history.length-1]))}}
return {mode, transition, back };
}
Here, our array is called history instead of boxes and we “push” into it using the SetHistory function instead of the “push” function we saw earlier. SetHistory is defined with help from the React’s useState function.
Further down in the code, we define the back function which uses “splice” instead of “pop” to remove the last item from our history array.
So what exactly is this history array doing for us?
Well, let’s go back to the warehouse. The box stacking system not only keeps all the fragile boxes unbroken, it also has unintended consequences. Anyone in the warehouse can now have a history of how the boxes were stacked based on each boxes position in the stack. This makes navigating backwards and forwards much easier and this is the logic we’re using in the above react example. Our react app can see the previous state of the component and navigate back to it if the user clicks the cancel button.
This is the same basic structure used in your web browser. Your web browser keeps a stack of the previous webpages you have visited. When you press the back button, your web browser pops your current page out of the stack, returning you to the page on the top of your stack, the last page you visited.
Stacks aren’t just used in arrays and React apps. Stacks are also used inside the call stack of Javascript. Javascript is a single threaded language, which means that it only has a single call stack when it executes code.
Doesn’t that sink our box stacking system?
Not quite.
When we write javascript code and execute it, the javascript call stack determines the structuring of the stack. When we call a function, we tell the compiler to add or “push” that function to the stack. When the function returns we “pop” it off the stack.
Without adding to our stacking rules, this makes for pretty boring stacking. When we execute our code we’re only adding one box to the stack then taking it away.
But what if we wanted to stack 3 boxes before unstacking them?
Well we could using more explicit instructions to get around our single threaded language.
So let’s go back to the warehouse...
Say we have an employee names Larry. Now Larry has seen a thing or two in his days in the warehouse and he’s skeptical of your new stacking system. He’s a lot like the Javascript call stack. Larry also has OCD and cannot violate the do not stack instructions written on each box. Rather than redesigning Larry, you decided to write a work around into your box stacking system.
You have 3 boxes:
You write on box one: stack, but do not unstack until box two has been stacked and unstacked.
You write on box two: stack, but do not unstack until box three has been stacked and unstacked.
You write on box 3: stack and do not unstack until order is ready to be shipped.
It works! Larry stacks the boxes exactly how you tell him too. In the process we learned about stacks in javascript, the javascript call stack and how we can use callbacks to manipulate it.
Now you should be able to avoid a situation like this.
DM me if you’d like to start a shipping company.
[1] Wikipedia “Stack: Abstract Data Type” https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
[2] Brian Dixon “Playing With Data Structures in Javascript” https://blog.cloudboost.io/playing-with-data-structures-in-javascript-stack-a55ebe50f29d
