Stacks

Introduction to Stacks

A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. It’s essentially a linear collection of elements with two primary operations: push and pop.

Stacks are used to manage data in a way that ensures that the most recently added element is the first one to be removed.

Basic Operations:

• Push: This operation adds an element to the top of the stack.
• Pop: This operation removes and returns the top element of the stack.
• Peek or Top: It retrieves the top element without removing it from the stack.
• isEmpty: Checks whether the stack is empty.

Stack Applications

Recursive call stack
Stacks are crucial for managing function calls in programming languages. When a function is called, its execution context is pushed onto the stack, and it’s popped off when the function returns.

Expression Evaluation
Stacks are used to evaluate mathematical expressions, particularly converting infix expressions (e.g., 2 + 3) to postfix notation (e.g., 2 3 +) and then evaluating them efficiently.

Undo Functionality
Stacks can be employed to implement undo and redo functionality in software applications. Each action or state change is pushed onto the stack and popped when the user requests an undo.

Backtracking Algorithms
Algorithms like depth-first search (DFS) use stacks to keep track of choices made during exploration and backtrack when necessary.

Syntax Parsing
Stacks are used in parsing and interpreting programming languages. They help ensure that the syntax is correctly structured, especially for languages with nested constructs (e.g., parentheses, curly braces).

Memory Management
Stacks are used in memory management for tracking allocated memory blocks and managing function call frames.

Browser History
Web browsers use stacks to keep track of visited web pages, enabling users to navigate backward and forward through

Visualization

Have a play with this interactive stack demonstration.

Python Implementation

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return len(self.items) == 0
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
        else:
            raise IndexError("Pop from an empty stack")
    def peek(self):
        if not self.isEmpty():
            return self.items[-1]
        else:
            raise IndexError("Peek from an empty stack")
    def size(self):
        return len(self.items)

Resources

https://docs.google.com/presentation/d/1EfZ8DWskKChmuqmyXf9mqgT4mRTVOxbVZaUQ-OL7lcQ/edit?usp=sharing