The stack data structure — What is it and how is it used in JavaScript?

In this article we are going to explore a very common data structure in programming — the stack. We will look into what it is and some common applications for it. I will then go on to provide some context into how it is used in the run-time of JavaScript.

Data Stack Structure

A stack is a linear data structure, elements are stacked on top of each other. Only the last element added can be accessed, i.e the element at the top of the stack. That is, a stack is a Last In First Out (LIFO) structure. This is the opposite of a queue which is First in First out (FIFO). We will see later on that the JavaScript run-time makes use of both of these.

A common analogy of a data stack is a pile (or stack!) of plates in a canteen; plates are stacked on top of each other. A customer takes a plate from the top. If for some reason they wanted to access the second plate, they would have to remove the top one first.

Visualization of the data stack structure

Data stacks work in the same way. They have three main operations:

• Push() — A new element is added to the top of the stack
• Pop() — Removes and returns the element at the top of the stack
• Top()/peek() — Look into the stack and return the last element pushed onto the stack. This operation does not alter the stack.

A stack will have a maximum size; when this limit is exceeded it is termed “Stack overflow”. This can often be caused when calling a recursive function without properly defining the base or terminating case.

Implementation

1. Array
2. Linked list

Applications

Stack data structures are useful when the order of actions is important. They ensure that a system does not move onto a new action before completing those before. Here are some common examples where a stack is used:

• Reversing — By default a data stack will reverse whatever is input. For example, if we wanted to reverse the string “Hello World”. We would push() each character onto the stack, and then pop() each character off.
• Undo/redo — This approach can be used in editors to implement the undo and redo functionality. The state of the program can be pushed to a stack each time a change is made. In order to undo, use pop() to remove the last change.
• Backtracking — This can be used when writing an algorithm to solve a problem involving choosing paths, for example a maze. A path is chosen and if it results in a dead end this latest branch in the path must be removed (pop()) and another route chosen. Each time a path is chosen it is pushed to the stack.
• Call stack — Programming languages use a data stack to execute code. When a function is called it is added to the call-stack and removed once completed.

The rest of this article will look at the call stack example in greater depth.

JavaScript & the Call Stack

A call stack is a mechanism for an interpreter (like the JavaScript interpreter in a web browser) to keep track of its place in a script that calls multiple functions.

JavaScript is a single-threaded language, this means that it can only do one thing at a time, and thus it has one call stack. The process is laid out below:

1. A script calls a function
2. The function is added to the call stack and function is carried out
3. If another function is called within, this is added to the top of the call stack and carried out until completed.
4. Once finished the current function is taken off the stack and the original function resumes execution.

Visual representation of the call stack at different parts of the run-time

From the image above we can see that the call stack records where in the program you are at any point. If there is an error in the code we are given the stack trace as a part of the error message. The lines below the error message “error in thirdFunc” show the current state of the call stack when the error occurred. An understanding of this can be incredibly useful in debugging and getting a better understanding as to how your code is being executed.

Execution Context

We are now going to dive a little deeper into what actually happens when a function is added to the stack. To understand this we need to know about ‘execution context’. The execution context is each element on the call stack.

When code is run in JavaScript, it can be executed in one of three environments:

1. Global context — this is the default environment that code is executed in at the start of a program
2. Function context— when the interpreter enters a function body
3. Eval context — text to be executed inside the internal eval function (not used very often)

There is always only one global context but there can be any number of function/eval contexts. As we saw above, each function call creates a new function context (even a call to itself).

There are two stages when creating a new execution context:

1. Creation — an execution context object is created. It contains three keys:

• Variable Object — Create the variables, functions, and arguments. Variables are declared and initialized to undefined (they are not assigned their values at this stage). Function declarations are stored by their name which has a reference pointer to the function in memory. **
• Scope chain — a collection of the current context’s variable object and all it’s parent’s lexical variable object. This is how a function has access to it’s parents variables.
• This — Determine the value of “this” inside the context

2. Execution

• Assign values to variables
• Interpret & execute the code

**This is why a function declaration can be ‘hoisted’. It is assigned during the creation phase whereas a function expression has no value assigned to it until the execution phase.

To help explain this follow the code example below where we will look at the execution context object for each stage for the following code:

Execution context object in the creation stage:

Execution context object in the execution stage:

Hopefully this provides a deeper understanding of the process when each execution context is added to the call stack in JavaScript.

A problem with a single threaded process is that if a particular function takes a long time, no other code can execute until it is complete. This is termed “blocking”. When used in the browser this can lead to unresponsive pages.

A solution to this within JavaScript is to use asynchronous callbacks which essentially put aside blocks of code to be run once the asynchronous process has completed, but continue to run the rest of the code in the meantime. But how does this work with the call stack?

The Event Loop

The event loop is responsible for executing the code, collecting and processing events, and executing queued sub-tasks.

The JavaScript run-time uses a message queue to line-up ‘messages’ containing the callback functions once an asynchronous process has completed. This process is FIFO (First in, First out), so if there are multiple asynchronous operations, the fastest will be first in the queue, and the first to be invoked.

When an asynchronous process goes on the stack it is moved to the event table, all other synchronous functions are processed through the stack. When the asynchronous process completes it gets moved to the message queue. Once the stack is empty the event loop starts handling the messages in the queue; it takes the first and the callback function is called. This creates a frame on the stack. The function completes and is removed from the stack. The stack is now empty again so the event loop checks for the next item in the message queue. This process continues until the stack and message queue are empty.

The event loop gives priority to the call stack, it processes everything it finds in the call stack, once empty it goes to the message queue to pick up any messages.

Below is an animation to show the previous example, which now includes an asynchronous process:

The Event Loop sequence of events

Conclusion

Hopefully this article helped you to gain a better understanding of the inner workings of JavaScript and how your code is actually run. For more information, take a look at some of the resources below.

Key takeaways:

• A stack is a First In, Last Out data structure
• Elements can only be pushed and popped from the top
• A major use of the data stack is for a JavaScript interpreter to keep track of function calls — this is a call stack
• Each element on the call stack is an execution context (global, function, eval). There can only be one global context, but many function contexts.
• JavaScript only has one call stack but optimizes asynchronous operations using the message queue and event loop.

Resources:

Stack Data Structure | Studytonight

Data Structures/Stacks and Queues

What is the Execution Context & Stack in JavaScript?