Stack Data Structures: A brief overview
How are stack data structures an important part of modern programming languages?
As I was going through a bootcamp this winter, the one term that constantly came up and seemed to be ubiquitous irrespective of the programming language is data structures.
Simply put , data structures are used to store data in an organized fashion such that it makes it efficient and conducive to access and modify the said data as and when required. Now there are a number of data structures out there such as lists, linked lists, tree etc. The one we are going to talk about is the stack data structure.
Stack Data Structures
A Stack is a widely used linear data structure in modern computers in which insertions and deletions of an element can occur only at one end, i.e., top of the Stack. It is used in all those applications in which data must be stored and retrieved in the last.
Now, for me when I hear the word “stack” the first image that comes to my mind is a stack of pancakes, and the stack data structure works very similar to a stack of pancakes……Well, somewhat!
Just like a stack of pancakes where the pancake on top is the first to be eaten , a stack follows a Last In First Out (LIFO) approach where an element that was last to be added to the stack is executed or processed first.
Applications of stack data structure
Some of the applications of the stack data structure are as follows:
- Evaluation of Arithmetic Expressions
The stack is used to evaluate arithmetic operations by converting infix expressions to postfix expressions which is then evaluated based on the precedence of arithmetic expressions.
Using the postfix notation the expression is then evaluated until there is a single value in the stack , which can be illustrated as follows:
- Reverse Data
The stack can also be used to reverse a string. Because of the First In Last Out property of the stack , the string can be reversed by adding (PUSH) the characters of strings in order to the stack which can then be removed (POP) from the stack in the reverse order.
- Undo/Redo/ Back functionalities
The undo or back functionalities that are present in almost all applications make use of the stack to revert back to the previous state. Every time you undo an action it is popped from the stack.
- Recursive Functions
When a recursive function is executed a function calls itself with an incremented/modified parameter a number of times until a certain condition is met . The stack is used to organize the order in which functions are being called and executed in a given instance as there may be a several of them.
- Processing Function Calls
Another application of the stack is the processing of the function calls. The functions or blocks are added to the stack in the order that they were called in and then executed in the first in last out order. This is can be further elaborated by explaining the call stack in javascript.
Call Stack In Javascript
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 — what function is currently being run and what functions are called from within that function, etc.
To elaborate the above explanation by MDN a call stack adds functions to the stack as and when that particular function is called and then it is executed. If that function calls another function then that function is added to “top” of the stack. When the second function returns a value it is removed from the stack and continues the execution of the previous function. The stack also has limited memory space, hence if functions exceed the memory space of the stack it results in a “Stack overflow”.
- When the code above is executed initially the global execution context function which is denoted by main() or global() is added to the stack.
- Then the greeting function is called which is added to the stack.
- The greeting function is executed, which in turn calls the hello function.
- Once hello function completes its execution it is popped from the stack.
- Then the greeting function completes its execution and is removed form the stack.
- And finally, the main function is removed form the stack and the program completed.
- This is also an example of synchronous javascript.
Conclusion
- The stack data structure uses First In Last Out principle to execute functions/ processes.
- The push and pop methods are used to add and remove functions to stack
- Some of the applications of the stack are execution of recursive functions, arithmetic expressions and reversing data.
- The Javascript interpreter in the browser uses the call stack mechanism to keep track of functions being called in a program.
References
