DSA Stacks

Welcome to TheCodingCollege.com! In this post, we’ll dive into stacks in Data Structures and Algorithms (DSA). Stacks are fundamental data structures that form the backbone of many algorithms and problem-solving techniques.

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element added to the stack is the first to be removed. Think of it like a stack of plates—plates are added on top and removed from the top.

Key Concepts of Stacks

  1. Push Operation: Add an element to the top of the stack.
  2. Pop Operation: Remove the top element from the stack.
  3. Peek (or Top): Retrieve the top element without removing it.
  4. IsEmpty: Check if the stack is empty.
  5. IsFull: (For fixed-size stacks) Check if the stack is full.

Applications of Stacks

Stacks are used in various scenarios, such as:

  • Expression evaluation (infix to postfix, postfix evaluation).
  • Backtracking (e.g., solving mazes, undo operations in text editors).
  • Function calls (maintained in the call stack).
  • Parsing (e.g., checking balanced parentheses).
  • Depth-First Search (DFS) in graphs.

Implementation of Stacks

Stacks can be implemented using:

  1. Arrays
  2. Linked Lists

1. Stack Implementation Using Arrays

class Stack:
    def __init__(self, size):
        self.stack = []
        self.size = size

    def push(self, data):
        if len(self.stack) < self.size:
            self.stack.append(data)
        else:
            print("Stack Overflow!")

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            print("Stack Underflow!")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            print("Stack is Empty!")

    def is_empty(self):
        return len(self.stack) == 0

# Example Usage
s = Stack(5)
s.push(10)
s.push(20)
print(s.peek())  # Output: 20
s.pop()
print(s.peek())  # Output: 10

2. Stack Implementation Using Linked Lists

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.is_empty():
            popped_data = self.top.data
            self.top = self.top.next
            return popped_data
        else:
            print("Stack Underflow!")

    def peek(self):
        if not self.is_empty():
            return self.top.data
        else:
            print("Stack is Empty!")

    def is_empty(self):
        return self.top is None

# Example Usage
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.peek())  # Output: 20
stack.pop()
print(stack.peek())  # Output: 10

Advantages of Stacks

  1. Simple and easy to implement.
  2. Efficient memory usage in linked list implementation.
  3. Supports dynamic sizing in linked list-based stacks.

Disadvantages of Stacks

  1. Fixed size in array-based stacks (stack overflow is possible).
  2. Limited operations (e.g., random access is not allowed).

Time Complexity of Stack Operations

OperationTime Complexity
PushO(1)
PopO(1)
PeekO(1)
IsEmptyO(1)

Common Problems and Use Cases

1. Balancing Parentheses

def is_balanced(expression):
    stack = []
    for char in expression:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack or not is_matching_pair(stack.pop(), char):
                return False
    return len(stack) == 0

def is_matching_pair(opening, closing):
    pairs = {')': '(', '}': '{', ']': '['}
    return pairs[closing] == opening

# Example Usage
expression = "{[()]}"
print(is_balanced(expression))  # Output: True

2. Reverse a String Using a Stack

def reverse_string(string):
    stack = []
    for char in string:
        stack.append(char)
    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    return reversed_str

# Example Usage
string = "Hello"
print(reverse_string(string))  # Output: "olleH"

3. Evaluate Postfix Expressions

def evaluate_postfix(expression):
    stack = []
    for char in expression:
        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[0]

# Example Usage
expression = "23*54*+"
print(evaluate_postfix(expression))  # Output: 26

Conclusion

Stacks are versatile and widely used in computer science and programming. Their simplicity and efficiency make them ideal for various applications. Understanding stacks will enhance your problem-solving skills and prepare you for advanced DSA concepts.

Visit TheCodingCollege.com for more tutorials, problem-solving techniques, and coding tips to boost your programming journey!

Leave a Comment