home bytes articles application of stack data structure

Data Science

Application of Stack in Data Structure

Last Updated: 4th August, 2024

Narender Ravulakollu

Technical Content Writer at almaBetter

Explore real world application of stack data structures, from function call management to undo/redo functions. Understand how stacks shape modern technology.

In the realm of computer science, data structures are the building blocks of efficient algorithms and software applications. Among these structures, the stack stands out as a simple yet powerful concept. A stack follows the "Last In, First Out" (LIFO) principle, making it a key player in various digital processes.

In this blog, we'll explore the applications of stack data structure, including the application of stack data structure in C, and we'll address questions like "What are the applications of stack in data structure". We'll journey through its basics, core operations, and practical uses, shedding light on how it's an essential tool for programmers and computer scientists. From function calls to undo/redo functionality, the stack plays a pivotal role. Join us in uncovering the application of stack in data structure.

What is a Stack?

At its core, a stack is a linear data structure that adheres to a simple yet powerful principle known as "Last In, First Out" (LIFO). This means that the last item added to the stack is the first to be removed, much like a physical stack of objects, where you can only add or remove items from the top.

Imagine a stack of plates: you can only add a plate to the top of the stack and remove a plate from the top. This intuitive analogy beautifully captures the essence of a stack data structure.

Example of Stack data structure

Basic Operations of a Stack

The stack data structure, with its Last In, First Out (LIFO) principle, is governed by a set of fundamental operations that enable it to manage and manipulate data efficiently. These basic operations are the building blocks of a stack:

1. Push:

The push operation is used to add an element to the top of the stack. This is akin to placing a new item on top of a physical stack.

When an element is pushed onto the stack, it becomes the new top, and all existing elements shift down one position.

// Example in C
#include <stdio.h>
#define MAX 1000

int stack[MAX];
int top = -1;

void push(int x) {
  if (top >= MAX - 1) {
printf("Stack Overflow\n");
  return;
}
stack[++top] = x;
printf("%d pushed onto stack\n", x);
}

int main() {
push(10);
push(20);
push(30);
  return 0;
}

2. Pop:

The pop operation is employed to remove the top element from the stack. This is similar to taking the top item from a stack of objects.

After popping an element, the stack size decreases, and the element that was beneath the removed item becomes the new top.

// Example in C
int pop() {
  if (top < 0) {
printf("Stack Underflow\n");
  return -1;
}
  return stack[top--];
}

int main() {
push(10);
push(20);
push(30);
printf("%d popped from stack\n", pop());
  return 0;
}

3. Peek (or Top):

The peek operation, also known as top, allows you to view the element at the top of the stack without removing it. This is useful for inspecting the current top element.

Peeking doesn't alter the stack's structure; it only provides information about the top element.

// Example in C
int peek() {
  if (top < 0) {
printf("Stack is Empty\n");
  return -1;
}
  return stack[top];
}

int main() {
push(10);
push(20);
printf("Top element is %d\n", peek());
  return 0;
}

These three operations are the core functionality of a stack and are implemented in various programming languages, including C.

Also Read: Searching in Data Structures and Traversing in Data Structure

Applications of Stack Data Structure

1. Function Call Stack:

In programming, the function call stack is an essential tool for managing function calls, including the application of stack data structure in C. When a function is invoked, its execution context is pushed onto the stack, including local variables and the return address. As the function completes, its stack frame is popped, allowing the program to resume execution in the calling function. This stack-based approach ensures that function calls are handled in the correct order, providing a structured way to manage program flow.

// Example in C
void functionA() {
printf("Function A\n");
}

void functionB() {
functionA();
printf("Function B\n");
}

int main() {
functionB();
return 0;
}

Here, calling functionB() pushes functionB onto the stack, which in turn calls functionA, pushing it onto the stack. Once functionA completes, it is popped off the stack, and control returns to functionB.

2. Undo/Redo Functionality:

Undo and redo functionalities are ubiquitous in software applications, from text editors to graphic design software. Stacks are employed to maintain a history of user actions, allowing for easy reversibility and exploration of past changes. When an action is performed, it's pushed onto the undo stack, and if the user wishes to undo it, the action is popped from the undo stack and pushed onto the redo stack, ensuring a seamless way to navigate through changes and correct mistakes.

# Example in Python
undo_stack = []
redo_stack = []

def perform_action(action):
undo_stack.append(action)
print(f"Performed: {action}")

def undo():
if undo_stack:
action = undo_stack.pop()
redo_stack.append(action)
print(f"Undo: {action}")

def redo():
if redo_stack:
action = redo_stack.pop()
undo_stack.append(action)
print(f"Redo: {action}")

perform_action("Type A")
perform_action("Type B")
undo()
redo()

3. Expression Evaluation:

Expression evaluation in a stack data structure involves using a stack to evaluate arithmetic expressions. When evaluating mathematical expressions, a stack can be employed to keep track of operators and operands, ensuring the correct order of operations. The LIFO property of stacks helps manage operator precedence, allowing for the accurate calculation of complex expressions.

The two main types of expressions that are evaluated using stacks are infix and postfix (Reverse Polish Notation, RPN) expressions. Here's a detailed explanation of how this works:

Infix Expressions

In infix expressions, operators are placed between operands (e.g., 3 + 5). Evaluating infix expressions using a stack involves converting the infix expression to a postfix expression using the Shunting Yard algorithm and then evaluating the postfix expression.

Postfix Expressions

In postfix expressions, operators follow their operands (e.g., 3 5 +). Postfix expressions are straightforward to evaluate using a stack.

Evaluation Process Using a Stack

Postfix Expression Evaluation

Initialize an empty stack.
Scan the postfix expression from left to right.
- If the current token is an operand (number), push it onto the stack.
- If the current token is an operator, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.
After scanning the entire expression, the stack will contain the final result.

Example: Evaluate 3 4 + 2 * 7 /

Scan 3: push 3 onto the stack.
Scan 4: push 4 onto the stack.
Scan +: pop 4 and 3, compute 3 + 4 = 7, push 7 onto the stack.
Scan 2: push 2 onto the stack.
Scan *: pop 2 and 7, compute 7 * 2 = 14, push 14 onto the stack.
Scan 7: push 7 onto the stack.
Scan /: pop 7 and 14, compute 14 / 7 = 2, push 2 onto the stack.
The stack now contains 2, which is the result of the expression.

Infix to Postfix Conversion

Initialize an empty stack for operators and an empty list for the output.
Scan the infix expression from left to right.
- If the current token is an operand, add it to the output list.
- If the current token is an operator, pop operators from the stack to the output list until the stack is empty or the operator at the top of the stack has lower precedence. Then push the current operator onto the stack.
- If the current token is a left parenthesis, push it onto the stack.
- If the current token is a right parenthesis, pop from the stack to the output list until a left parenthesis is encountered. Discard the pair of parentheses.
After scanning the entire expression, pop any remaining operators from the stack to the output list.

Example: Convert 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 to postfix

Scan 3: add to output → 3.
Scan +: push onto stack → +.
Scan 4: add to output → 3 4.
Scan *: push onto stack → + *.
Scan 2: add to output → 3 4 2.
Scan /: pop *, push / → 3 4 2 * /.
Scan (: push ( → + (.
Scan 1: add to output → 3 4 2 * / 1.
Scan -: push - → + ( -.
Scan 5: add to output → 3 4 2 * / 1 5.
Scan ): pop to ( → 3 4 2 * / 1 5 -.
Scan ^: push ^ → + ^.
Scan 2: add to output → 3 4 2 * / 1 5 - 2.
Scan ^: push ^ → + ^ ^.
Scan 3: add to output → 3 4 2 * / 1 5 - 2 3.
Pop remaining operators: 3 4 2 * / 1 5 - 2 3 ^ ^ +.

The resulting postfix expression is 3 4 2 * 1 5 - 2 3 ^ ^ / +.

# Example in Python
def infix_to_postfix(expression):
precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
stack = []
output = ''
  for char in expression:
  if char.isalnum():
output += char
  elif char == '(':
stack.append('(')
  elif char == ')':
  while stack and stack[-1] != '(':
output += stack.pop()
stack.pop()
  else:
  while stack and precedence[char] <= precedence.get(stack[-1], 0):
output += stack.pop()
stack.append(char)
  while stack:
output += stack.pop()
  return output

expression = "3+5*2/(7-2)"
print(f"Postfix: {infix_to_postfix(expression)}")

4. Backtracking Algorithms:

Backtracking algorithms, such as depth-first search (DFS) in graph theory, depend on the stack data structure to systematically explore paths and make choices at each step. As the algorithm progresses, the current path and choices are pushed onto the stack. If a dead-end is encountered, the algorithm backtracks by popping elements from the stack, allowing it to explore alternative paths and find solutions to problems like pathfinding and puzzles.

# Example in Python
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}

def dfs(graph, start):
stack = [start]
visited = set()
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex)
visited.add(vertex)
stack.extend(set(graph[vertex]) - visited)

dfs(graph, 'A')

5. Browser History:

Web browsers utilize stacks to manage users' browsing history efficiently, demonstrating the application of stack and queue in data structure. Every time a user visits a new web page, the current page is pushed onto the forward stack, while the previous page is pushed onto the back stack. This approach enables users to navigate backwards and forward through their browsing history using the browser's "Back" and "Forward" buttons, providing a seamless and intuitive web browsing experience.

# Example in Python
back_stack = []
forward_stack = []

def visit(page):
back_stack.append(page)
print(f"Visited: {page}")

def back():
if back_stack:
page = back_stack.pop()
forward_stack.append(page)
print(f"Back to: {page}")

def forward():
if forward_stack:
page = forward_stack.pop()
back_stack.append(page)
print(f"Forward to: {page}")

visit("Page 1")
visit("Page 2")
back()
forward()

6. Memory Management:

In programming languages like C and C++, the stack plays a critical role in memory management, illustrating the application of stack ADT in data structure. It is used to store function call information, local variables, and execution-related data. The stack segment of a program's memory is typically allocated for this purpose. As functions are called and return, memory is efficiently allocated and deallocated from the stack, ensuring effective memory management and resource optimisation in software development, particularly in low-level programming.

// Example in C
void function() {
int localVariable = 10; // This variable is stored on the stack
printf("Local Variable: %d\n", localVariable);
}

int main() {
function();
return 0;
}

Conclusion

In computer science, the stack data structure is a versatile workhorse, serving diverse application of stack data structure with its LIFO principle and three core operations. From managing function calls and powering undo/redo functions to ensuring precision in expression evaluation and enabling backtracking algorithms, stacks are pivotal. They underpin efficient browsing history in web browsers and are vital in low-level memory management.

The stack's adaptability and real-world importance are undeniable. Mastering the applications is essential for programmers and computer scientists alike. So, as you embark on your journey through the world of technology, remember that stacks, like the unsung heroes, quietly make remarkable contributions, and they are yours to harness.

With stacks in your toolkit, you're well-equipped to navigate the digital landscape and build solutions that stand the test of time.

If you enjoyed this article and want to expand your knowledge in Data Science, check out our in-depth courses, such as Data Science Training and Masters in Data Science.