Understanding Stack Data Structures and The Call Stack
A Stack is a type of linear data structure that follows either a First In First Out (FIFO) or Last In First Out (LIFO) method, determining the order in which operations are performed. Another term for this type of structure is a pushdown store since the data is being “pushed down”, like filling up a buffet-style plate dispenser, pushing each new plate on top of the previous one. With both FIFO and LIFO, the top of the stack refers to the side or end of the data that can be modified.
Linear stacks are easy to implement, such as with a queue or linked list, and are quick and efficient at handling a large amount of input, as they support basic stack operations with a constant time complexity of O(1). Some real-world examples of a LIFO stack are the undo/redo functionality, email storage, as well as browsing history, where the most recent page you visited is removed from the top of the stack and displayed by clicking the back button. Examples of a queue or FIFO stack would be waiting in line for the bathroom, taking a number to be seen, or organizing groceries on the shelf so that the ones soonest to expire are at the front.
Information in a linear stack can be modified or manipulated while preserving the organization of the data. Unlike in an array where you can access an element by its index, stack elements are added or removed from the top of the stack. Therefore, to access an element further down the stack, all elements above it would need to be removed first. A stack generally supports three methods: push(), pop(), and peek() or top(). Push() and pop() are essential operations, whereas peek() or top() are considered non-essential, so these methods are not always implicitly defined. Lastly, there are helper methods that are associated with stack data structures. Common ones include isEmpty() and length() or size().
push()
push() adds, or pushes, an element to the top of the stack. This results in the stack size increasing by 1, and the top is now the newly added element. In the image below, the top of the stack shifts from B to C after push().
pop()
pop() removes the most recently added element that is still present, which is also the element that is currently at the top of the stack. As a result, the size of the stack is decreased by 1, and the top shifts to the next most recently added element. In the case of the image above, the top of the stack shifts from C to B after pop().
peek() Or top()
peek() or top() is used to return the element at the top of the stack without removing it. This will verify the top element without modifying the data, or return null if the stack is empty. An example of how to implement this in JavaScript would be to return the element at index length - 1 position, such as below:
peek() {
return stack[stack.length - 1];
}isEmpty()
isEmpty() returns true if the stack is empty. Checking this before a pop() method prevents stack underflow, a condition caused by attempting to remove an element from an empty stack. It is important to handle/prevent underflow as it can lead to unexpected behaviour in the program. JavaScript example:
isEmpty(stack) {
// return true if stack is empty
return stack.length === 0;
}length()
length() or size() returns the size of the stack. Some programming languages are vulnerable to security breaches because they use a shared stack for both data and procedure calls. If programs written in these languages do not check the length of data input, it exposes the code to a stack-smashing attack. This occurs when an oversized data input is provided to the program maliciously and successfully resets the return of the current procedure(s) to a location within the stack, allowing unauthorized operations to be carried out. Stack smashing is a type of stack buffer overflow and is a frequent source of software security breaches.
length(stack) {
// return size of the stack
return stack.length
}Stack Advantages
As mentioned above, linear stacks are easier to implement than other data structures, and they are expeditious at handling input, as represented by the O(1) time complexity. In addition to these advantages, stack data structures also support backtracking algorithms. Backtracking algorithms search for a solution to a problem among all available options. When a solution does not satisfy the constraints, it will be removed and the algorithm will backtrack to the previous state. Backtracking can be thought of as a form of recursion since the operation is repeated recursively until either no solution is found or the final state is achieved.
Stack Disadvantages
Since elements can only be added or removed from the top of the stack, accessing elements within the stack becomes difficult and time-consuming. Therefore, this data structure would not be suitable for some applications, such as those that involve searching or sorting algorithms.
As mentioned previously, stack data structures support recursive functions. Each time a recursive function calls itself, it uses up more of the stack memory. If the function is called enough times to use up all available memory, it will result in a stack overflow condition.
The Call Stack
Many languages make use of a call stack mechanism, which follows the LIFO principle of Last In, First Out. This mechanism allows a language interpreter to keep track of where it is in the script and what functions are being run. JavaScript is a single-threaded programming language, meaning it has a single call stack, also known as the execution stack. Whenever a function is called, a new stack frame is created and added to the top of the call stack. When we return from a function, we pop it off the top of the stack and move on to the next stack frame. In the example below, when doJob() is called, doJob(), printLog(), followed by console.log() are added to the call stack. They would then be removed according to LIFO starting with console.log(), printLog(), and finally doJob().
Disadvantages to Consider
The call stack is allocated a set amount of memory by the browser or operating system and can, therefore, only hold a fixed number of stack frames. Once that number is reached, adding new frames could result in a stack overflow. This risks exploiting security vulnerabilities regarding application data, as well as memory corruption, which can cause an application to crash or exhibit other unpredictable behaviour.
The Event Loop
Javascript handles asynchronous operations in the browser via the event loop, which leverages the single call stack with WebAPIs and the callback queue. WebAPIs are part of the environment of the browser which we can interact with using JavaScript, and therefore they do not block the call stack. Any callback functions as a result of a WebAPI request would be added to the callback queue. The callback queue is a FIFO data structure that stores the callback functions in the order they arrive. Finally, the event loop pushes functions from the callback queue to the call stack when the call stack is empty.
Summary
- Stacks are important fundamental data structures that are useful when the order of operations is important.
- Stacks are widely used in both software and hardware applications for their many advantages.
- Most programming languages have an interpretation of the call stack.
- JavaScript uses the call stack to keep track of several function calls and leverages this in the browser via the event loop.
If you are intrigued and would like to dive deeper into your understanding of stack data structures, visit the links below!