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!

Solution#

 1def reverse_string(text):
 2    stack = list(text)
 3    result = []
 4    while stack:
 5        result.append(stack.pop())
 6    return "".join(result)
 7
 8
 9class MinStack:
10    def __init__(self):
11        self.stack = []
12        self.mins = []  # tracks the minimum at each depth
13
14    def push(self, value):
15        self.stack.append(value)
16        if not self.mins or value <= self.mins[-1]:
17            self.mins.append(value)
18        else:
19            self.mins.append(self.mins[-1])
20
21    def pop(self):
22        self.mins.pop()
23        return self.stack.pop()
24
25    def top(self):
26        return self.stack[-1]
27
28    def get_min(self):
29        return self.mins[-1]
30
31
32class QueueUsingStacks:
33    def __init__(self):
34        self.inbox = []
35        self.outbox = []
36
37    def enqueue(self, value):
38        self.inbox.append(value)
39
40    def dequeue(self):
41        if not self.outbox:
42            while self.inbox:
43                self.outbox.append(self.inbox.pop())
44        return self.outbox.pop()
45
46
47print(reverse_string("stack"))  # kcats