Applications of Stack in Data Structures and Algorithms

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.

1. Back and forward buttons in a web browser

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.

• If we want to go back to a page we have previously visited, we can use the back button. This removes the current page from the top of the back stack and stores it on the forward stack.
• If we want to move forward again, we can use the forward button, which retrieves the page from the top of the forward stack and pushes the current page onto the back stack.

2. UNDO/REDO functionality in text editors and image editing software

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.

• If we perform undo action, the top record is removed from the undo stack and added to the redo stack.
• If we perform redo action, the top record is removed from the redo stack and added to 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!

3. Memory management in computer programming

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.

4. Delimiter checking

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:

1. We initialize an empty stack.
2. We iterate through each character in the string.
3. When an opening delimiter (e.g., '(', '[', '{' ) is encountered, we push it onto the stack.
4. When a closing delimiter (e.g., ')', ']', '}') is encountered, we check the top element of the stack. If it's a matching opening delimiter, we pop the top element from the stack. If it's not a matching opening delimiter or stack is empty, the string has an error.
5. After iterating through the entire string, if stack is empty, then the delimiters in the string are balanced. If stack is not empty, the string contains an error.

Implementation code C++

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.

5. Implementing recursion in programming

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.

6. Expression conversion and evaluation

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:

1. We initialize an empty stack.
2. We iterate through each character in the infix expression.
3. When an operand is encountered (e.g. a number or variable), we add it to the postfix notation expression.
4. When an operator is encountered (e.g +, -, *, /, etc), we pop operators with higher or equal precedence from the stack and add them to the postfix notation expression. Then we push the current operator onto the stack.
5. When a left parenthesis is encountered, we push it onto the stack.
6. When a right parenthesis is encountered, we pop operators from the stack and add them to the postfix notation expression until a left parenthesis is encountered. Here we pop and discard the left parenthesis.
7. After iterating through the entire infix expression, we pop any remaining operators from the stack and add them to the postfix notation expression.
8. Now we have a postfix notation expression. We can evaluate it using a similar algorithm using the stack. This time, we pop the last two operands and do the operation, then push the result back to the stack. We repeat the process until the stack only has the final result.

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.

7. Matching HTML tags in web development

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:

1. We initialize an empty stack.
2. We iterate through each character in the HTML document.
3. When an opening tag is encountered, we push the tag name onto the stack.
4. When a closing tag is encountered, we pop the top element from the stack and compare it to the closing tag. If they match, we continue iterating through the document. If they don't match, then the HTML document contains an error.
5. After iterating through the entire document, the stack should be empty. If it's not, then the HTML document contains an error.

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.

8. We can solve a lot of coding problems using stack!

• Implementing the depth-first search algorithm for traversing a graph or tree.
• Reversing the order of items in a list or string.
• Finding a topological sorting of a directed acyclic graph (DAG)
• Designing iterative backtracking algorithms, which involve navigating through a series of choices, and then backtracking if a particular choice does not satisfy a constraint. Examples of problems that can be solved using backtracking include the Knight-Tour problem, the N-Queen problem and finding a path through a maze.
• Next greater element: Find the next greater element for each element in the array.
• Sort stack: Given a stack, sort the elements in the stack in ascending order. You may not use any additional data structures or make any copies of the elements.
• Implement stack using queue: Design a stack that is implemented using one or more queues.
• Implement queue using stack: Design a queue that is implemented using one or more stacks.
• Min stack: Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time
• Largest rectangle in histogram: Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.
• Reverse stack elements: Given a stack, reverse the order of the elements in the stack.
• Implement two stack using single array: Design a data structure that allows for two stacks to be used with a single array, with both stacks having O(1) time complexity for push and pop operations.

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!