The stack is one of the most commonly used data structures in computer science and the basis for many of our favourite programming languages, JavaScript being a major one. As developers we need to be aware of the way it works behind the scenes and the nuances behind working with stacks.
The Stack Data Structure
A stack is a type of data structure that puts data in a sequential order, known as a linear data structure. Stacks also follow a Last in, First Out (LIFO) principle where only the last element added to the stack can be accessed.
A good way to imagine this is like putting plates away in a cupboard. We put each plate away one by one and on top of each other and when we want to take a plate we can only take the top one. In technical terms, adding to the stack is called pushing and removing the top element is called popping.
Here is a good diagram showing the stack data structure and how only the top most element can be interacted with.
An important aspect of this structure is the stack frame which is the amount of memory allocated to the stack. In our plate analogy, we can think of this as the size of the cupboard itself; we can only put in as many plates as will fit in the cupboard. Similarly, there is a maximum number of elements that can be pushed onto a stack. If you were to push more than was allowed, a stack overflow error occurs as we have exceeded the allocated memory. This typically happens in endless for/while loops and is the stack’s way of stopping these infinite loops.
Stack Applications
One of the most prevalent stack applications is found in expression evaluation. Thinking back to our knowledge of arithmetic expressions, we learned that there was a certain order we needed to consider when evaluating these expressions: Brackets, indices, division, multiplication, addition, and subtraction. Additionally, these expressions are read left to right with arithmetic operators in between the operands.
However, there is another form of arithmetic expression known as the Polish Notation where arithmetic operators are placed before operands as such, only the order which the elements are written is important. For example, instead of A + B, you would write +AB.
We can see how the stack data structure could be used here. Instead of having to worry about the hierarchy of arithmetic operators, we can focus on just the order of the expression.
For example: ( 2 + 3 ) * ( 6 - 1 ) would be written as * + 2 3 - 7 2
Another important application of the stack data structure involves the idea of backtracking. This is where an algorithm may need to revert steps and go backwards in order to get the correct outcome.
The best example of this is in depth-first tree traversal where an algorithm will follow node children to traverse all of the nodes in a tree. Since each leaf node represents a “dead end” in the traversal, algorithms need a way to go backwards to continue traversing the tree.
In this tree diagram, the order in which each node is visited is displayed showing the algorithm backtracking to nodes it has already visited. Stacks can be used here to capture the route we take to traverse the tree. We can see that node 1, 2, 3, and 4 are pushed onto the stack before the algorithm cannot find any more children. It then pops node 4 off of the stack and pushes node 5 on before repeating.
The stack data structure is also used in memory allocation in most modern computer systems. To understand this, we need to know how computers allocate memory and processing power.
Modern computers are multi-threaded meaning there are many threads, each of which have its own individual stack. This means that, even if the stack data structure dictates that we interact only with the top most element at a given time, multiple threads can be working on their own individual processes at the same time. In stack-based memory allocation, each thread is allocated memory known as its stack and the computer system will add processes to this stack.
JavaScript Call Stack: Synchronous
JavaScript’s call stack is also based on the stack data structure. A key property of JavaScript call stack is that it is single threaded, meaning things happen one at a time. Sometimes we can see this happening if we define a particular function that takes a while to process, holding up the rest of the code from executing.
When executing JavaScript code, the engine will go through two phases, the global execution phase and the function execution phase. In the first phase, the JavaScript engine will define global variables and functions. This is put on the top of the call stack as the first element denoted as global() or main(). In the second phase, JavaScript will execute function calls making use of the defined variables and functions in the first phase. This is where functions are pushed and popped from the stack.
Another key property of the JavaScript engine is that, unless specified, JavaScript will execute code synchronously. What this means is that, all of the code executes block by block, as you’ve written it.
Here is an example to show the single-threaded, block by block nature of the JavaScript call stack.
We can see that despite calling the third function first, JavaScript does not execute the console log “Third function” until the first and second function have executed.
Thinking from the perspective of the call stack, we can see how it changes when each function is called.
We see that the JavaScript call stack begins with the global execution phase, denoted by main (). We then add thirdFunction to the stack when it is called and subsequently secondFunction and firstFunction since they are contained within thirdFunction. Once firstFunction is on the stack, the engine can begin executing the element and popping it from the stack, one by one until no more elements remain.
In Summary
The call stack in JavaScript can be daunting at first, but remembering its key properties and nuances can make it easier to visualize code execution.
The key takeaways from this topic are:
- The JavaScript call stack is single-threaded
- It uses the LIFO data structure
- JavaScript code executes synchronously, most of the time
