Request a callback

or Chat with us on

# Understanding Real-World Applications of Stack in Data Structure

Basics of Python
5 Hrs. duration
9 Modules
1800+ Learners
Start Learning

Ever wondered how a browser keeps track of your history? Or how can your text editor undo multiple steps?

These are just a couple of real-world examples of the applications of stack in data structure.

Stacks are simple yet powerful. They follow the Last In, First Out (LIFO) principle. Imagine a stack of plates. You can only add or remove the top plate.

The same concept applies to stacks in computer science. We use stacks to solve problems where we need to access data in reverse order of its arrival.

In this blog we will come across some of the crucial applications of stack in data structure, so let’s start.

## Key Operations of Stack Data Structure

Before going into the applications of stack in data structure, it is important to understand the basic operations of a stack in the data structure.

Let’s break down the key operations:

### Push Operation: Adding Elements to the Stack

The push operation adds an element to the top of the stack. It’s like placing a new plate on top of a stack of plates.

Here’s a simple Python code example:

```# Function to push an element onto the stack def push(stack, item): stack.append(item) print(f"Element {item} pushed to stack") # Example usage stack = [] push(stack, 10) push(stack, 20) push(stack, 30) print("Stack:", stack) ```

Output:

```Element 10 pushed to stack Element 20 pushed to stack Element 30 pushed to stack Stack: [10, 20, 30] ```

### Pop Operation: Removing Elements from the Stack

The pop operation removes the top element from the stack. This is like removing the top plate from a stack.

```# Function to pop an element from the stack def pop(stack): if len(stack) == 0: return "Stack is empty" return stack.pop()  # Example usage print("Popped element:", pop(stack)) print("Stack:", stack) ```

Output:

```Popped element: 30 Stack: [10, 20] ```

### Peek Operation: Accessing the Top Element of the Stack

The peek operation allows us to see the top element without removing it.

```# Function to peek at the top element of the stack def peek(stack): if len(stack) == 0: return "Stack is empty" return stack[-1] # Example usage print("Top element:", peek(stack)) ```

Output:

```Top element: 20 ```

### Checking If the Stack is Empty or Full

To check if the stack is empty, we simply check its length.

```# Function to check if the stack is empty def is_empty(stack): return len(stack) == 0 # Example usage print("Is stack empty?", is_empty(stack)) ```

Output:

```Is stack empty? False ```

## Evaluating Arithmetic Expressions Using Stacks

Stacks are incredibly useful for evaluating arithmetic expressions, especially when dealing with different notations.

Understanding Different Notations: Infix, Prefix, and Postfix

• Infix Notation: Operators are between operands (e.g., A + B).
• Prefix Notation: Operators precede operands (e.g., +AB).
• Postfix Notation: Operators follow operands (e.g., AB+).

Step-by-Step Example: Evaluating a Postfix Expression

```Let’s evaluate the postfix expression 6 5 2 3 + 8 * + 3 + * using a stack. # Function to evaluate postfix expression def evaluate_postfix(expression): stack = [] for char in expression.split(): if char.isdigit(): stack.append(int(char)) else: b = stack.pop() a = stack.pop() if char == '+': stack.append(a + b) elif char == '-': stack.append(a - b) elif char == '*': stack.append(a * b) elif char == '/': stack.append(a / b) return stack.pop() # Example usage expression = "6 5 2 3 + 8 * + 3 + *" result = evaluate_postfix(expression) print(f"Result of postfix expression '{expression}' is {result}") ```

Output:

```Result of postfix expression '6 5 2 3 + 8 * + 3 + *' is 288 ```

## Utilising Stacks for Backtracking in Algorithms

Backtracking is an algorithmic approach to solving problems step by step. Stacks are significant in backtracking because they enable the storage and tracking of certain states of solutions.

Explanation of Backtracking Technique

Backtracking is a search technique in which all possible solutions to a problem are tried out until the correct solution is found. If a path is invalid, we return to the previous state.

Example: Solving a Maze Using Backtracking and Stacks

Let’s solve a simple maze using a stack.

```# Function to solve a maze using backtracking and stacks def solve_maze(maze, start, end): stack = [start] visited = set() while stack: position = stack.pop() if position == end: return True if position in visited: continue visited.add(position) x, y = position # Add valid moves to stack if x > 0 and maze[x-1][y] == 0: stack.append((x-1, y)) if x < len(maze)-1 and maze[x+1][y] == 0: stack.append((x+1, y)) if y > 0 and maze[x][y-1] == 0: stack.append((x, y-1)) if y < len(maze[0])-1 and maze[x][y+1] == 0: stack.append((x, y+1)) return False   # Example usage maze = [ [0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 0], [1, 1, 0, 1] ] start = (0, 0) end = (3, 2) print("Path exists:", solve_maze(maze, start, end)) ```

Output:

```Path exists: True ```

## Reversing Data with the Help of Stack

How can we reverse a string or a list efficiently? This is a common question we face when dealing with data manipulation. Stacks offer a straightforward solution.

By leveraging the Last In, First Out (LIFO) property, we can reverse data quickly and effectively.

Let’s dive into a simple example. We will reverse a string using a stack.

```# Function to reverse a string using a stack def reverse_string(input_string): stack = [] for char in input_string: stack.append(char) reversed_string = '' while stack: reversed_string += stack.pop() return reversed_string   # Example usage input_string = "Data structures are fun" reversed_string = reverse_string(input_string) print("Reversed string:", reversed_string) ```

Output:

```Reversed string: nuf era serutcurts ataD ```

This method is not limited to strings. We can use the same concept to reverse lists, queues, and other data structures.

## Checking for Balanced Parentheses in Expressions

Have you ever wondered how to check if the parentheses in an expression are balanced? This is a crucial task in compilers and interpreters. Stacks provide an efficient way to handle this problem.

Here’s a Python example to check for balanced parentheses:

```# Function to check for balanced parentheses def are_parentheses_balanced(expression): stack = [] opening = "({[" closing = ")}]" matching = {')': '(', '}': '{', ']': '['}  for char in expression: if char in opening: stack.append(char) elif char in closing: if not stack or stack[-1] != matching[char]: return False stack.pop() return not stack  # Example usage expression = "{[a+b]*(c-d)/e}" print("Are parentheses balanced?", are_parentheses_balanced(expression)) ```

Output:

```Are parentheses balanced? True ```

This approach ensures that every opening parenthesis has a matching closing parenthesis in the correct order.

Internship Assurance
DevOps & Cloud Engineering

## Managing Function Calls and Recursion with Stacks

How do we keep track of function calls and recursive calls? Stacks are essential for managing these operations. They store return addresses, local variables, and other important information.

Let’s look at a simple recursive function to calculate the factorial of a number, using a stack to track function calls.

```# Recursive function to calculate factorial def factorial(n): if n == 0: return 1 return n * factorial(n - 1)  # Example usage number = 5 print("Factorial of", number, "is", factorial(number)) ```

Output:

```Factorial of 5 is 120 ```

In this example, each call to factorial is pushed onto the call stack until it reaches the base case. Then, the stack unwinds as each call returns its result.

## Implementing Queues Using Two Stacks

Can we implement a queue using stacks? Yes, we can. By using two stacks, we can mimic the behaviour of a queue, which follows the First In, First Out (FIFO) principle.

Here’s how we can do it:

1. Push elements onto the first stack.
2. To dequeue, pop elements from the first stack and push them onto the second stack.
3. Pop the top element from the second stack.

Let’s see this in action with a Python example.

```class QueueUsingStacks: def __init__(self): self.stack1 = [] self.stack2 = []  def enqueue(self, item): self.stack1.append(item) print(f"Element {item} enqueued")  def dequeue(self): if not self.stack2: while self.stack1: self.stack2.append(self.stack1.pop()) if not self.stack2: return "Queue is empty" return self.stack2.pop()  # Example usage queue = QueueUsingStacks() queue.enqueue(10) queue.enqueue(20) queue.enqueue(30) print("Dequeued element:", queue.dequeue()) print("Dequeued element:", queue.dequeue()) ```

Output:

```Element 10 enqueued Element 20 enqueued Element 30 enqueued Dequeued element: 10 ```
```Dequeued element: 20 ```

Using two stacks, we have successfully implemented a queue. This method ensures that the queue operations remain efficient.

Undo and Redo Operations in Text Editors

When we use text editors like Microsoft Word or Google Docs, the undo and redo functionality relies on stacks. Every action is pushed onto a stack. If we press undo, the last action is popped from the stack.

Here’s a simple example:

```# Function to demonstrate undo functionality using stacks def undo_example(actions): undo_stack = [] redo_stack = []  for action in actions: undo_stack.append(action) print(f"Action performed: {action}")  print("nUndo operations:") while undo_stack: last_action = undo_stack.pop() redo_stack.append(last_action) print(f"Undone: {last_action}")  print("nRedo operations:") while redo_stack: action = redo_stack.pop() undo_stack.append(action) print(f"Redone: {action}")  # Example usage actions = ["type 'Hello'", "type 'World'", "delete 'World'", "type 'Python'"] undo_example(actions) ```

Output:

```Action performed: type 'Hello' Action performed: type 'World' Action performed: delete 'World' Action performed: type 'Python'  Undo operations: Undone: type 'Python' Undone: delete 'World' Undone: type 'World' Undone: type 'Hello'  Redo operations: Redone: type 'Hello' Redone: type 'World' Redone: delete 'World' Redone: type 'Python' ```

## Browser History Management with Stacks

When we navigate web pages, browsers use stacks to manage history. Each visited page is pushed onto a stack. Clicking the back button pops the last page and loads the previous one.

Here’s a simple way to visualise this:

```# Function to manage browser history using stacks def browser_history_example(visited_pages): history_stack = []  for page in visited_pages: history_stack.append(page) print(f"Visited: {page}")  print("nBack button pressed:") while history_stack: last_page = history_stack.pop() print(f"Back to: {last_page}")  # Example usage visited_pages = ["google.com", "facebook.com", "herovired.com", "growthtrack.com"]```

browser_history_example(visited_pages)

Output:

```Visited: google.com Visited: facebook.com Visited: herovired.com Visited: growthtrack.com Back button pressed: Back to: growthtrack.com Back to: herovired.com Back to: facebook.com Back to: google.com ```

## Expression Conversion in Compilers

Compilers use stacks to convert expressions from infix to postfix notation. This helps in evaluating expressions more efficiently.

Here’s an example to illustrate this:

```# Function to convert infix expression to postfix using stack def infix_to_postfix(expression): precedence = {'+':1, '-':1, '*':2, '/':2, '^':3} stack = [] postfix = ''  for char in expression: if char.isalnum(): postfix += char elif char == '(': stack.append(char) elif char == ')': while stack and stack[-1] != '(': postfix += stack.pop() stack.pop() else: while stack and precedence.get(char, 0) <= precedence.get(stack[-1], 0): postfix += stack.pop() stack.append(char)  while stack: postfix += stack.pop()  return postfix  # Example usage expression = "A+B*(C^D-E)" print("Postfix expression:", infix_to_postfix(expression)) ```

Output:

```Postfix expression: AB+CD^E-*+ ```

Stacks have their strengths and weaknesses. Let’s break them down.

### Benefits of Stack Data Structure

• Simplicity: Easy to implement and use.
• Efficiency: Push and pop operations are fast (O(1)).
• Memory Management: Helps in managing function calls and recursion.
• Reversibility: Excellent for undo/redo operations in applications.
• Order Preservation: Maintains the sequence of operations which is crucial for certain tasks.
• Resource Management: Helps in managing resources like memory and processor time efficiently.

### Limitations and Potential Drawbacks

• Limited Access: Only the top element is accessible.
• Fixed Capacity: Stacks can overflow if not managed properly.
• Not Suitable for Random Access: You can’t access elements in the middle directly.
• Potential for Underflow: If we pop from an empty stack, it can cause errors.
• Sequential Nature: Operations are sequential, which can be a limitation for certain applications.
• Capacity Constraints: In static stacks, the maximum size needs to be defined, which may not be flexible.

## Conclusion

Stacks are a fundamental part of data structures. They simplify complex tasks like expression evaluation, function call management, and undo operations.

In this blog, we explored various applications of stack in data structure. We learned how stacks help in reversing data, checking balanced parentheses, managing function calls, and implementing queues.

We also saw how stacks are used in real-world scenarios, such as undo/redo operations in text editors, browser history management, and expression conversion in compilers.

Stacks provide simplicity, efficiency, and effective memory management. They are essential tools for solving complex problems.

By understanding their applications, we can build more robust and efficient programs.

FAQs
A stack uses LIFO (Last In, First Out), while a queue uses FIFO (First In, First Out).
Stacks keep track of function calls, storing return addresses and local variables.
Yes, stacks can be implemented using linked lists, providing dynamic memory management.
Text editor undo/redo, browser history, and expression evaluation in compilers.
Stack overflow happens when too much data is pushed onto the stack. It can be prevented by managing stack size and using proper memory management techniques.

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

## Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles
View all
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies

Certificate Program in Financial Analysis, Valuation and Risk Management

Management

Certificate Program in Strategic Management and Business Essentials

Executive Program in Product Management

Certificate Program in Product Management

Certificate Program in Technology-enabled Sales

Future Tech

Certificate Program in Gaming & Esports

Certificate Program in Extended Reality (VR+AR)

Professional Diploma in UX Design

Blogs
Reviews
Events
In the News