Introduction to Stacks #

Welcome to Day 11 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore stacks, a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle.

What is a Stack? #

A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). Real-life examples include a stack of plates or a pile of books.

Basic Operations of a Stack #

1. Push: Adds an element to the top of the stack
2. Pop: Removes the top element from the stack
3. Peek or Top: Returns the top element of the stack without removing it
4. isEmpty: Returns true if the stack is empty, else false

Implementing a Stack in Python #

We can implement a stack using a Python list or create a custom class. Let’s implement both:

Using a Python List #

 1class Stack:
 2    def __init__(self):
 3        self.items = []
 4
 5    def is_empty(self):
 6        return len(self.items) == 0
 7
 8    def push(self, item):
 9        self.items.append(item)
10
11    def pop(self):
12        if not self.is_empty():
13            return self.items.pop()
14        else:
15            raise IndexError("Stack is empty")
16
17    def peek(self):
18        if not self.is_empty():
19            return self.items[-1]
20        else:
21            raise IndexError("Stack is empty")
22
23    def size(self):
24        return len(self.items)

Using a Custom Node Class #

 1class Node:
 2    def __init__(self, data):
 3        self.data = data
 4        self.next = None
 5
 6class Stack:
 7    def __init__(self):
 8        self.top = None
 9
10    def is_empty(self):
11        return self.top is None
12
13    def push(self, item):
14        new_node = Node(item)
15        new_node.next = self.top
16        self.top = new_node
17
18    def pop(self):
19        if self.is_empty():
20            raise IndexError("Stack is empty")
21        popped = self.top.data
22        self.top = self.top.next
23        return popped
24
25    def peek(self):
26        if self.is_empty():
27            raise IndexError("Stack is empty")
28        return self.top.data
29
30    def size(self):
31        count = 0
32        current = self.top
33        while current:
34            count += 1
35            current = current.next
36        return count

Time Complexity #

• Push operation: O(1)
• Pop operation: O(1)
• Peek operation: O(1)
• Search operation: O(n) in the worst case

Applications of Stacks #

1. Function Call Stack: Used by compilers to manage function calls
2. Expression Evaluation: Used to evaluate prefix, infix, and postfix expressions
3. Backtracking Algorithms: Used in backtracking problems like finding maze paths
4. Undo Mechanism: Implementing undo functionality in text editors
5. Balanced Parentheses: Checking for balanced parentheses in expressions

Example: Balanced Parentheses #

Let’s implement a function to check if parentheses in an expression are balanced:

 1def is_balanced(expression):
 2    stack = []
 3    opening = "({["
 4    closing = ")}]"
 5    pairs = {")": "(", "}": "{", "]": "["}
 6    
 7    for char in expression:
 8        if char in opening:
 9            stack.append(char)
10        elif char in closing:
11            if not stack or stack.pop() != pairs[char]:
12                return False
13    
14    return len(stack) == 0
15
16# Test the function
17print(is_balanced("({[]})"))  # True
18print(is_balanced("([)]"))    # False
19print(is_balanced("(("))      # False

Exercise #

1. Implement a function to reverse a string using a stack.
2. Create a MinStack class that supports push, pop, top, and retrieving the minimum element in constant time.
3. Implement the Queue data structure using two stacks.

Summary #

Today, we explored the stack data structure, its implementation, and a practical application. Stacks are crucial in many algorithms and real-world applications due to their LIFO nature. Understanding stacks will help you solve various problems efficiently and is essential for topics like depth-first search and expression parsing.

Tomorrow, we’ll dive into queues, another fundamental data structure that follows the First-In-First-Out (FIFO) principle. Stay tuned!