Applications of Stack Data Structure in Programming

The key idea behind using a stack is that it allows for easy access to the most recently added element and easy removal of that element, which can be useful in situations where you need to keep track of a history of actions or reverse actions. So based on various use cases, there are several applications of stack in coding problem solving and computer programming:

Back and forward buttons in a web browser

When we are browsing the web, the back and forward buttons on our web browser can be really handy for navigating between pages. We can implement these buttons by maintaining two separate stacks of links to web pages. The back stack contains links to pages we have previously visited, and the forward stack contains links to 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. In this way, we can move back and forth through the pages we have visited without having to manually enter the URL of each page.

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 a stack by 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 choose to undo an action, the top record is removed from the undo stack and added to the redo stack, undoing the action in the document or image. Conversely, if we choose to redo an action, the top record is removed from the redo stack and added back to the undo stack, redoing the action in the document or image.

This is a common and efficient method to implement the undo/redo functionality, however, there are other methods that can be used such as using a more complex data structure like a linked list which allows for storing more data and the ability to go back multiple steps. Alternatively, we could save different versions of the document or image and switch between them.

Memory management in computer programming

A stack data structure can be used in systems where memory is allocated in a static way to manage memory allocation and track which memory blocks are in use. Additionally, it can 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.

The Java Virtual Machine (JVM) uses this concept in keeping track of the state of a running Java program, it uses two types of stacks, the Java Stack and the Native Stack. The Java Stack stores the state of Java method invocations, creating and adding a new frame to the stack each time a method is invoked, it contains information about the method's local variables, the current line of execution, and the return address. The Native Stack is used for method invocations written in languages other than Java such as C or C++, and it interacts directly with the underlying operating system and hardware.

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. The process is as follows:

  1. Initialize an empty stack.
  2. Iterate through each character in the string.
  3. When an opening delimiter (e.g., '(', '[', '{') is encountered, push it onto the stack.
  4. When a closing delimiter (e.g., ')', ']', '}') is encountered, check the top element of the stack. If it's a matching opening delimiter, pop the top element from the stack. If it's not a matching opening delimiter or the stack is empty, the string has an error.
  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 contains an error.

Implementation code C++

bool isBbalanced(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 correspond to it. If the delimiters match correctly, the opening and closing delimiters will be removed from the stack in the correct order. This is a simple way to implement delimiter checking, variations such as checking for specific delimiters with specific characteristics or ignoring certain delimiters in certain contexts are also possible.

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 and return points as the recursion takes place.

Each time a function is called, a new frame is added to the stack, which contains the function's local variables and return address. Once the base case is reached and the function returns a value, 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. It's important to note that this is a simplified explanation and 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.

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 the operators in-between operands (e.g. 1 + 2) are converted to postfix notation (e.g. 1 2 +) and then evaluated with the use of stack data structure.

Here are the general steps of this process:

  1. Initialize an empty stack.
  2. Iterate through each character in the infix expression.
  3. When an operand is encountered (e.g. a number or variable), add it to the postfix notation expression.
  4. When an operator is encountered (e.g +, -, *, /, etc), pop operators with higher or equal precedence from the stack and add them to the postfix notation expression. Then push the current operator onto the stack.
  5. When a left parenthesis is encountered, push it onto the stack.
  6. When a right parenthesis is encountered, pop operators from the stack and add them to the postfix notation expression until a left parenthesis is encountered. Pop and discard the left parenthesis.
  7. After iterating through the entire infix expression, pop any remaining operators from the stack and add them to the postfix notation expression.
  8. Now you have a postfix notation expression, you can evaluate it using a similar algorithm using stack to keep the operands, this time pop the last two operands and do the operation, then push the result back to the stack. 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 operator is in-between the operands. Stack keeps the track of the operands and operators during the conversion and evaluation process and thus ensures the correct order of operations in the postfix notation expression.

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 a stack data structure. 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. Initialize an empty stack.
  2. Iterate through each character in the HTML document.
  3. When an opening tag is encountered (e.g. ), push the tag name onto the stack.
  4. When a closing tag is encountered (e.g. ), pop the top element from the stack and compare it to the closing tag. If they match, 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.

This approach works because when a closing tag is encountered, the most recent opening tag on the stack should correspond to it. If the tags match, the opening and closing tags are removed from the stack in the correct order. Additionally, stacks are 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.

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.

Enjoy learning, enjoy algorithms!

More From EnjoyAlgorithms

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.