Real-life Applications of Stack Data Structure

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 data or actions. So based on various use cases, there are several applications of the stack in programming. Here are some popular real life applications of the stack.

1. Back and forward buttons in a web browser

• If we want to go back to a page we have previously visited, we can use the back button. This removes the page from the top of 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 push it 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. 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 like parentheses, brackets, curly braces, etc. One idea is to do this using a stack by keeping track of the delimiters encountered while parsing the string. Here are the steps:

1. We initialize an empty stack.
2. We iterate through each character in the string.
3. When we encounter an opening delimiter e.g., '(', '[', '
4. When we encounter a closing delimiter e.g., ')', ']', '>', 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 the stack is empty, the string is not balanced.
5. After iterating through the entire string, if the stack is empty, then the delimiters in the string are balanced. If the stack is not empty, the string is not balanced.

Implementation pseudocode

bool delimiterChecking(string str, int n)  stackchar> s for (int i = 0; i  n; 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 we encounter a closing delimiter, the most recent opening delimiter should be present on the top of the stack. If the delimiters match correctly, we remove opening delimiters from the top of the stack in the correct order.

5. Implementing recursion in programming

Recursion is a technique where a function calls itself to solve a problem. To execute such a process, the compiler uses a call stack to keep track of the history of function calls.

Each time a function is called during recursion, a new frame is added to the stack, which contains the function's local variables and return address. Once recursion reaches the base case, the corresponding frame is popped off the stack and the return value is passed up to the previous caller. 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. In practice, the process may differ, but the main concept remains the same. Some languages have tail-recursion optimization, which allows the compiler to optimize the recursion.

6. Expression conversion and evaluation

Stacks are used in 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 and evaluation, where we first convert the infix expression to postfix expression using stack (e.g. 1 2 +). After this, we evaluate the postfix expression using the stack.

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 we encounter an operand (e.g. a number or variable), we add it to the postfix expression.
4. When we encounter an operator (e.g +, -, *, /, etc), we pop operators with higher or equal precedence from the stack and add them to the postfix expression. Then we push the current operator onto the stack.
5. When we encounter a left parenthesis, we push it onto the stack.
6. When we encounter a right parenthesis, we pop operators from the stack and add them to the postfix expression until we encounter a left parenthesis. 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 expression.

Now we have a postfix 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 process and ensures the correct order of operations in the postfix 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.
• 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 or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!