Data Structures - Stack

1. Why Are Data Structures Important?

Data structures are the foundation of computer science. They help you write programs that are fast, efficient, and organized—no matter which programming language you're using.

• Help organize and store data efficiently in memory
• Provide a way to manage large amounts of data
• Enable faster access, insertion, and deletion of data
• Essential for solving complex programming problems
• Support the development of scalable applications

2. Data Type vs Data Structure

2.1 What is a Data Type?

A data type defines what kind of data a variable can hold. It tells the computer what type of value is stored and how much memory is needed.

• int – stores whole numbers like 10, -5, 0
• float – stores decimal numbers like 3.14, 2.5
• str – stores text like "Hello", "Python"
• bool – stores either True or False

Think of data types as basic building blocks. They help define the type and nature of a single piece of data.

2.2 What is a Data Structure?

A data structure is a way of organizing and storing a group of data so it can be used efficiently. It's like a container that holds multiple values, often of the same or different data types.

• List – stores a collection of values like [1, 2, 3]
• Tuple – stores fixed values like (10, 20)
• Dictionary – stores key-value pairs like {"name": "John"}
• Stack – special way to organize data for LIFO access
• Queue – special way to organize data for FIFO access

Think of data structures as containers or folders that store multiple values together in a specific format.

3. What is a Stack?

A stack is a data structure that follows the LIFO (Last In First Out) principle. The last element added to the stack is the first one to be removed.

3.1 Real-Life Analogy

Think of a stack of plates at a dinner party. Plates are always added or removed from the top of the pile:

• New plates are placed on top (push operation)
• When you need a plate, you take from the top (pop operation)
• The plate you added last is the first one you take

3.2 Other Real-Life Applications

• Undo feature in MS Word: Each action is pushed; Ctrl+Z pops the last action
• Browser back button: Each webpage is pushed; clicking back pops the previous page
• Function calls: Each function call is pushed onto call stack
• Redo/Undo operations: Maintains history of actions

3.3 LIFO Principle Visualization

Stack Operations:

Push 10    → Stack: [10]
Push 20    → Stack: [10, 20]
Push 30    → Stack: [10, 20, 30]  (30 is at top)
Pop        → Stack: [10, 20]       (30 is removed - last added, first removed!)
Pop        → Stack: [10]           (20 is removed)
Push 40    → Stack: [10, 40]
Pop        → Stack: [10]

4. Operations on Stack

4.1 Push Operation - Add Element

Push adds an element to the top of the stack. In Python, we use the append() method.

# Push Operation using append()
stack = []
stack.append(10)    # Push 10
stack.append(20)    # Push 20
stack.append(30)    # Push 30
print(stack)        # Output: [10, 20, 30]
print("Top element:", stack[-1])  # Output: 30

4.2 Pop Operation - Remove Element

Pop removes and returns the top element from the stack. In Python, we use the pop() method.

# Pop Operation
stack = [10, 20, 30]
top_element = stack.pop()  # Removes and returns 30
print("Popped:", top_element)  # Output: 30
print("Stack after pop:", stack)  # Output: [10, 20]

popped = stack.pop()       # Removes and returns 20
print("Popped:", popped)   # Output: 20
print("Stack:", stack)     # Output: [10]

4.3 Other Stack Operations

5. Implementation of Stack Using List

The implementation of stack using list in Python is the easiest of all programming languages. A list provides all necessary methods (append, pop) to implement a stack.

5.1 Why Use List for Stack?

• list.append() – Efficiently adds elements at the end (O(1) time)
• list.pop() – Efficiently removes from the end (O(1) time)
• Negative indexing – Easy to access top element using list[-1]
• Dynamic size – List grows automatically as needed

5.2 Basic Stack Implementation

# Simple Stack Implementation using List

# 1. Create (Initialize) Stack
stack = []

# 2. Push - Add elements to stack
stack.append(10)
stack.append(20)
stack.append(30)
print("Stack after pushes:", stack)  # [10, 20, 30]

# 3. Check if Empty
if len(stack) == 0:
    print("Stack is empty")
else:
    print("Stack is not empty")

# 4. Peek - View top element without removing
print("Top element (Peek):", stack[-1])  # 30

# 5. Pop - Remove top element
popped_item = stack.pop()
print("Popped:", popped_item)  # 30
print("Stack after pop:", stack)  # [10, 20]

# 6. Display all elements
print("\nStack contents (bottom to top):")
for element in stack:
    print(element)

5.3 Complete Stack Class Implementation

class Stack:
    def __init__(self, max_size=None):
        """Initialize the stack"""
        self.items = []
        self.max_size = max_size
    
    def push(self, data):
        """Add element to stack"""
        if self.max_size is not None and len(self.items) >= self.max_size:
            print("Stack Overflow! Cannot push more elements")
            return False
        self.items.append(data)
        return True
    
    def pop(self):
        """Remove and return top element"""
        if self.is_empty():
            print("Stack Underflow! Cannot pop from empty stack")
            return None
        return self.items.pop()
    
    def peek(self):
        """View top element without removing"""
        if self.is_empty():
            print("Stack is empty")
            return None
        return self.items[-1]
    
    def is_empty(self):
        """Check if stack is empty"""
        return len(self.items) == 0
    
    def is_full(self):
        """Check if stack is full (for bounded stack)"""
        if self.max_size is None:
            return False
        return len(self.items) >= self.max_size
    
    def size(self):
        """Return number of elements"""
        return len(self.items)
    
    def display(self):
        """Display all elements in stack"""
        if self.is_empty():
            print("Stack is empty")
            return
        print("Stack (top to bottom):")
        for i in range(len(self.items)-1, -1, -1):
            print(self.items[i])

# Using the Stack class
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
stack.display()
print("Top element:", stack.peek())
print("Popped:", stack.pop())
stack.display()

5.4 Practical Example - Undo Feature

# Simulating Undo feature using Stack

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
    
    def type_text(self, new_text):
        """Add text and save to undo stack"""
        self.undo_stack.append(self.text)  # Save current state
        self.text += new_text
        print(f"Current text: '{self.text}'")
    
    def undo(self):
        """Undo last action"""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.text = self.undo_stack.pop()
        print(f"After undo: '{self.text}'")

# Usage
editor = TextEditor()
editor.type_text("Hello")     # "Hello"
editor.type_text(" World")    # "Hello World"
editor.type_text("!")         # "Hello World!"
editor.undo()                 # "Hello World"
editor.undo()                 # "Hello"

6. Stack Overflow and Underflow

6.1 Stack Overflow

• Meaning: Trying to add (push) an element to a stack that is already full
• Happens when: Stack has a fixed size and no more space left
• Result: Error – "Stack Overflow"
• Prevention: Check if stack is full before pushing

6.2 Stack Underflow

• Meaning: Trying to remove (pop) an element from an empty stack
• Happens when: Stack is empty and pop operation is performed
• Result: Error – "Stack Underflow"
• Prevention: Check if stack is empty before popping

# Demonstrating Overflow and Underflow

# Stack Overflow (with bounded stack)
max_stack_size = 3
stack = []

for i in range(1, 6):
    if len(stack) < max_stack_size:
        stack.append(i)
        print(f"Pushed {i}: {stack}")
    else:
        print(f"Cannot push {i} - Stack Overflow!")

# Stack Underflow
for i in range(1, 6):
    if len(stack) > 0:
        popped = stack.pop()
        print(f"Popped {popped}: {stack}")
    else:
        print("Cannot pop - Stack Underflow!")

7. Applications of Stack

• Undo/Redo operations: Text editors, image editors save state in stack
• Backtracking: Solving puzzles (Sudoku), mazes, N-Queens problem
• Function call management: Recursion uses call stack internally
• Expression evaluation: Converting infix to postfix (Reverse Polish Notation)
• Browser navigation: Back button maintains visited pages in stack
• Syntax checking: Matching parentheses, brackets, braces