The Stack Data Structure

In computer science, data is information and a data structure is a way to store that information such that relationships between the values and any functions or operations that can be applied to the data are maintained.

A Stack Data Structure is a specific type of data structure that can be visualized with the values as building blocks, one on top of the other and only the topmost value is accessible. Data is added to the stack by ‘LIFO’ or last-in-first-out, ie you can only add a single value to the top of the stack and you can only remove a single value from the top of the stack.

A visualization of the stack data structure

Data is added to the top of the stack by a ‘push’ operation and similarly, data can be removed and returned from the top of the stack by a ‘pop’ operation. If the stack is empty then trying to perform ‘pop’ would result in something called ‘stack underflow’ (ie there is no data to return).

One implementation of this data structure which we will look at further on in the article is the call stack. This structure is assigned a static amount of memory and hence has a maximum size. If you try to push more data onto the stack when the size of the stack is already at maximum capacity then this would result in something called ‘stack overflow’.

Another stack operation is ‘peek’. This allows you to look at the item at the top of the stack without removing it. A peek operation is similar to pop but it does not change the size of the stack as we simply view the data.

Finally, we define the ‘isEmpty’ operation. This checks if the stack contains any data and returns a boolean.

How can we implement the Stack Data Structure?

Stack data structures are very common in computer science. For example, the undo function could utilize a stack data structure. Think of typing the word ‘String’, as we type each letter we can think of this as pushing each letter onto the stack. When we hit backspace we only delete the last letter added, one at a time. Typing a letter would be the push operation, hitting backspace would be the pop operation. The stack is the letters we see on the page.

Another simple implementation of this data structure is for string reversal. We can visualize pushing each letter of the string on to the stack as so:

Pushing ‘String’ to the stack

Once we have pushed all of the letters on to the stack we now simply pop all the letters back off the again:

Popping letters back off the stack.

Finally, as we pop off the last letter the stack is empty and our string reversal is complete:

Popping the last letter from the stack renders the stack empty.

The Stack Data Structure in JavaScript

Let’s look at how we might implement the stack data structure in JavaScript. We first define the class Stack with the methods we’ve defined above:

class Stack {
constructor() {
this.storedValues = {};
this.size = 0;
}
push(newValue) {
this.storedValues[this.size] = newValue;
this.size++;
}
pop() {
let topValue = this.storedValues[this.size - 1];
delete this.storedValues[this.size - 1];
this.size--;
return topValue;
}
peek() {
return this.storedValues[this.size - 1];
}
getSize() {
return this.size;
}
isEmpty() {
return this.getSize() === 0;
}
}

We add values to the object storedValues with the object key being the size of the stack at that moment. Each time we push to the stack we increase the size of the stack. A pop method decreases the size, returns the value at the top of the stack and decreases the size of the stack by one. A peek method returns just the top value of the stack. The getSize method checks the size of the stack, and isEmpty simply checks if the size of the stack is 0 or not.

With the Stack class now defined let’s return to the string reversal and see how we might implement this function using the Stack class we have defined above.

function reverseStr(str) {
let reversedStr = ""
const stack = new Stack()
for(let i = 0; i < str.length; i++){
stack.push(str[i]); //push all the letters onto the stack
}
for(let i = 0; i < str.length; i++){
reversedStr += stack.pop(); //pop all the letters off the stack
}
return reversedStr //return the resulting string
}
reverseStr("String") // => gnirtS

We use a for loop to push each character of the string to the stack and then another for loop to pop these values off again, we add these values cumulatively to a new string (reversedStr) and finally, we return this reversed string. We can examine the stack object via the console at each step of the process to get a more visual understanding of what is going on. Here is the console output of the stack for the beginning of the process:

Stack { storedValues: {}, size: 0 }

As we start to push the letters we can see them in storedValues:

Stack { storedValues: { '0': 'S' }, size: 1 }
Stack { storedValues: { '0': 'S', '1': 't' }, size: 2 }
Stack { storedValues: { '0': 'S', '1': 't', '2': 'r' }, size: 3 }
Stack {
storedValues: { '0': 'S', '1': 't', '2': 'r', '3': 'i' },
size: 4 }
Stack {
storedValues: { '0': 'S', '1': 't', '2': 'r', '3': 'i', '4': 'n' },
size: 5 }

As we now pop these values back off the stack we can examine the reversedStr element as it grows:

g
gn
gni
gnir
gnirt
gnirtS

Now let’s look at a more complex example. We can use the stack data structure to check if a string of brackets is matched correctly. That is, if each opening bracket has a closing bracket and it closes in the right place. For example:

a_valid-string = "({})"
a_non-valid-string = "({)}"

We can check these conditions using the stack data structure. Here is a possible implementation of this function in JavaScript:

function checkBrackets(str) {
const stack = new Stack()
const bracketLookup = {
'(': ')',
'{': '}',
'[': ']'
}
for(let i = 0; i < str.length; i++){

if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) {
stack.push(str[i]);
console.log(stack)
}
else { 
let lastValue = stack.pop()
console.log(`str[${i}]:`, str[i])
if(bracketLookup[lastValue]!== str[i])
return false
}
}
if(!stack.isEmpty()) {
console.log(stack)
return false
}
return true
}

We create a new stack from the class defined above. We also create an object ‘bracketLookup’ which we will use to check the matching of pairs of brackets. We loop through the elements of the string and push all open brackets to the stack in order. When we encounter a closing bracket we pop the last element off the stack and check if it matches the closing bracket, if not we return false from the function. Finally, we have to check if the stack is empty once we have looped through all the string elements. If it is not, that means we have an extra bracket with no matching bracket and we return false.

If we output the stack to the console as we loop through the string we can visualize better what is happing inside the stack:

checkBrackets("({})") //a valid string
Stack { storedValues: { '0': '(' }, size: 1 }
Stack { storedValues: { '0': '(', '1': '{' }, size: 2 }
str[2]: }
str[3]: )
true

For the non-valid string, we see it fails as we check the first non-opening bracket ):

checkBrackets("({)}") // a non-valid string
Stack { storedValues: { '0': '(' }, size: 1 }
Stack { storedValues: { '0': '(', '1': '{' }, size: 2 }
str[2]: )
false

Looking at a more complicated non-matching example, {({({)}})){{}}:

checkBrackets("{({({)}})){{}}") //another non-valid string
Stack { storedValues: { '0': '{' }, size: 1 }
Stack { storedValues: { '0': '{', '1': '(' }, size: 2 }
Stack { storedValues: { '0': '{', '1': '(', '2': '{' }, size: 3 }
Stack {
storedValues: { '0': '{', '1': '(', '2': '{', '3': '(' },
size: 4 }
Stack {
storedValues: { '0': '{', '1': '(', '2': '{', '3': '(', '4': '{' },
size: 5 }
str[5]: )
false

We see it fails at the fifth string element as we expected.

Finally, let’s look at one more example using this structure with the string [{{{}}}. We see here why we need the final condition after looping through the string values to check if the stack is empty:

checkBrackets("[{{{}}}") //another non-valid string
Stack { storedValues: { '0': '[' }, size: 1 }
Stack { storedValues: { '0': '[', '1': '{' }, size: 2 }
Stack { storedValues: { '0': '[', '1': '{', '2': '{' }, size: 3 }
Stack {
storedValues: { '0': '[', '1': '{', '2': '{', '3': '{' },
size: 4 }
str[4]: }
str[5]: }
str[6]: }
Stack { storedValues: { '0': '[' }, size: 1 } 
false

The Call Stack in JavaScript

Now we will leave these simple implementations of the stack data structure and move on to something called the JavaScript call stack. The call stack is a stack data structure and is used whenever a file is run. JavaScript is interpreted which means it executes code line-by-line. The call stack is used to keep track of which part of the function the interpreter is in and which functions have yet to be executed. Whenever a function is called it is pushed to the top of the stack and when it is executed it is popped off the stack again. Let’s look at a simple example:

const timesTen = function(n) {
return n * 10
}
console.log(timesTen(2));

Here we have a function that returns the input multiplied by 10 and a console.log of that function called with the value 2.

We first define the timesTen function on line 1.

On line 4 the call stack receives the first function call to execute. This is passed to the call stack. JavaScript reads this line and sees a call to the function timesTenwith the value 2.

This timesTen function call gets pushed on to the top of the call stack. JavaScript then goes to line 1 again but this time with the value of n = 2. It goes into the timesTen function and returns the value 20.

This value then gets passes back to the console.log and the timesTen function is popped off the call stack.

Finally, the console.log is passed the value 20, we see 20 on the console and the console.log is popped off the call stack too.

The call stack is once again empty and the program is complete. Here is a visualization of this simple program:

Visualization of the call stack with a simple function composition.

Now let’s look at how we might reach that overflow condition mentioned in the introduction. The call stack is allocated a certain amount of memory and if too many calls are made and we will exceed the maximum size of the stack it throws an error. This size limitation prevents an infinite loop from using all the memory of the computer. Instead, the process is terminated and we safely see an error on the console. Let’s see an example of this in javascript with a simple recursion gone wrong:

const increaseN = function(N) {
N = N+1
return increaseN(N)
}
increaseN(1);

Here we have a simple recursion that adds one to the input and then calls itself with the new value. Watching the console if we output the value of N we quickly see this explode up to 12501 before we get the error:

RangeError: Maximum call stack size exceeded

Another visualization of the call stack helps to understand what is going on:

The stack quickly overflows with function calls to increaseN(N)

When the maximum stack size is reached we cannot push any more function calls to the stack and we see the stack overflow error.

How about a function that takes a long time to execute? As we know JavaScript is single-threaded, ie it can only do one thing at a time. Suppose we are trying to load a page and we need to make an ajax request. Something like this can take some time to process and if it gets stuck in the call stack while it executes then the rest of the page would be blocked from rendering until it completes, which can ruin the user experience. The solution is to use an asynchronous callback.

Asynchronous Call Backs and the JavaScript Event Loop

In the gif below using the Loupe tool created by Philip Roberts from &yet we can see the Javascript call stack in action. When we pass an asynchronous request to the call stack, for example an ajax request or a request to a setTimeout function, this gets popped back off the stack and onto web APIs, once the callback is completed it gets pushed onto something called the callback queue, where it waits to be passed to the call stack. The event loop will push the task onto the call stack as soon as the stack is empty. Here is an example to visualize this process:

Gif created using the Loupe event loop visualizer tool

Here we have a simple set timeout call, and within that, we log ‘in set timeout’ to the console. After that, we log Hi to the console. We see that even though the console.log(‘Hi’) comes later in the file, due to the setTimeout, the call stack passes this over to the web APIs and this frees up the stack for the other console.log and so we first see Hi in the console.

After the timer has completed, the in set timeout console log is put on the callback queue and since the stack is now empty it is pushed on and then popped back off and we see ‘in set timeout’ in the console.

This makes some sense but what if we call setTimeout with a timer of 0? You may think it would stay on the stay on the stack and execute there since there is no timer to wait for, however, we see that actually it still gets passed onto the web APIs. This is because any call to setTimeout is passed to the web APIs in order to free up the call stack for synchronous code. The setTimeout is immediately completed and the inner function is put onto the callback queue Once the call stack is empty, it gets pushed onto the stack. Using setTimeout with 0 seconds is a nice way to defer some slow code while synchronous code executes. Below you can see this example in the Loupe visualizer:

Loupe visualization for setTimeout call with no delay

This may seem strange at first but this means that even when we have tasks that take time to complete we don’t block the render of our page because they can be pushed onto web APIs, freeing up the call stack for fast, synchronous code. This clever mechanism improves user experience as they do not have to wait for every line of code to run before they can see anything on a page. Even though JavaScript is single-threaded this allows the browser to do several things concurrently.

Here is one more example with several asynchronous callbacks, using the Loupe visualization we see the order in which the functions are executed:

A Loupe visualization of the event loop with multiple asynchronous callbacks

Conclusion

In this article, we have looked in detail at the Stack Data Structure and how we may implement this structure in JavaScipt and use it for some simple operations. We have also considered the call stack and the event loop and looked at how JavaScript executes slower code. For more information and to play around with the Loupe tool I encourage you to check out this link, from CEK.io, where you can watch the original video for the talk given by Phillip Roberts about the JavaScript event loop and this link for the Loupe visualization tool.