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
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
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.
82.9%
of professionals don't believe their degree can help them get ahead at work.
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.
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:
- Push elements onto the first stack.
- To dequeue, pop elements from the first stack and push them onto the second stack.
- 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-*+
Advantages and Disadvantages of Using Stacks
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.
What is the primary difference between a stack and a queue?
How does a stack handle function calls in programming?
Can a stack be implemented using linked lists?
What are some common real-world examples of stack usage?
How does stack overflow occur, and how can it be prevented?
Updated on August 13, 2024