The key idea behind using a stack is that it allows for easy access and removal of the most recently added element, which can be useful in situations when we need to keep track of a history of actions or reverse actions. So based on various use cases, there are several applications of the stack in programming and DSA problem-solving.
Here are some examples of popular applications of the stack in data structures and algorithms.
The back and forward buttons on browser can be really handy for navigating between pages. We can implement these buttons by maintaining two separate stacks. Here, we use one stack (back stack) to track links to the previously visited pages, and another stack (forward stack) to track links to the pages we have navigated away from but may want to revisit.
The UNDO/REDO functionality in text editors and image editing software can be implemented using two separate stacks: one for undo and one for redo. Every time we perform an action on the document or image, a new record containing information about the action is created and added to the top of the undo stack.
This is a common and efficient method to implement the undo/redo functionality. But there are other methods that can be used such as using a doubly linked list. Think and explore!
Stack can be used in systems where memory is allocated in a static way to manage memory allocation or track which memory blocks are in use. It can also be used to keep track of function calls in a program and ensure that the program returns to the correct location when a function is complete. For example, the Java Virtual Machine (JVM) uses this concept in keeping track of the state of a running Java program.
Delimiter checking is a process that verifies if a string of characters has matching pairs of delimiters, such as parentheses, brackets, and curly braces. One way of accomplishing this is by using a stack data structure and keeping track of the delimiters encountered while parsing the string.
This algorithm works as follows:
bool delimiterChecking(string str)
{
stack<char> s;
for (int i = 0; i < str.length(); i = i + 1)
{
if (str[i] == '(' || str[i] == '[' || str[i] == '{')
s.push(str[i]);
else if (str[i] == ')' || str[i] == ']' || str[i] == '}')
{
if (s.empty() == true)
return false;
char top = s.top();
if ((top == '(' && str[i] == ')') || (top == '[' && str[i] == ']') || (top == '{' && str[i] == '}')) {
s.pop();
else
return false;
}
}
if(s.empty() == true;
return true;
else
return false;
}
This approach works because when a closing delimiter is encountered, the most recent opening delimiter should be present on the top of the stack. If the delimiters match correctly, the opening delimiters will be removed from the top of the stack in the correct order.
Recursion is a technique where a function calls itself in order to solve a problem. To manage this, a call stack is used to keep track of the function calls as the recursion takes place.
Each time a function is called, a new frame is added to the stack, which contains function's local variables and return address. Once the base case is reached, the corresponding frame is popped off the stack and the return value is passed up to the next level. This process continues until the original call has returned the final value and all the frames have been popped off the stack.
To understand this idea better, explore this blog: How recursion works in programming?
This is a simplified explanation, but in practice, the process may differ, but the main concept remains the same. Additionally, some languages have tail-recursion optimization, which allows the compiler to optimize the recursion process.
Stacks are commonly used in the process of evaluating mathematical expressions written in infix notation (e.g., (1 + 2) * 3) by converting them to postfix notation (e.g., 1 2 + 3 * ). This process is known as expression conversion or evaluation, where we first convert the expression written in infix notation (e.g. 1 + 2) to postfix notation using stack (e.g. 1 2 +). After this, we evaluate the expression in postfix notation using the stack data structure.
Here are the general steps of this process:
This method works because postfix notation has the operator applied to the operands immediately before it, unlike infix notation where the operator is in-between the operands. The stack keeps the track of the operands and operators during the conversion and evaluation process and ensures the correct order of operations in the postfix notation expression.
We highly recommend designing and writing complete working code for this algorithm.
In web development, it's important to ensure that the opening and closing tags of an HTML document match correctly. This can be done using stack. The basic idea is to use a stack to keep track of the opening tags as they are encountered in the HTML document, and then match them with the corresponding closing tags as they are encountered.
Here's a general overview of how this process works:
Stacks are also used in some HTML parsing libraries to parse HTML and generate a tree-like structure. This method can provide more information about the structure of the HTML and can be useful for tasks such as creating a table of contents or modifying the style of specific elements on a page.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.