📦 Data Structures — Stack

🌐 1. Introduction to Data Structures

Think of a data structure like a super-organised school bag 🎒. When everything has its own compartment — books in one pocket, pencils in another — you find things in seconds. Without organisation, you're rummaging forever!

Data Structure = A systematic way of organising, managing, and storing data in a computer so it can be accessed and modified efficiently.

Why Do Computers Need Data Structures?

Imagine you have 10 million student records. Without proper organisation:

• 🔴 Searching takes hours
• 🔴 Inserting new records causes chaos
• 🔴 Deleting safely becomes impossible

With the right data structure:

• ✅ Search in milliseconds
• ✅ Insert efficiently
• ✅ Delete safely without breaking anything

🔷 Types of Data Structures

• 📘 Linear Data Structure — Data elements are arranged one after another in a straight sequence, like people standing in a queue.

  • Examples: Array, Stack, Queue, Linked List
  • Each element has exactly one predecessor and one successor (except the first and last)
  • Memory is usually continuous and easy to traverse

• 📗 Non-Linear Data Structure — Data elements are NOT arranged in a straight line — they branch out in a hierarchy or network.

  • Examples: Tree, Graph
  • Like a family tree 🌳 or a city road map 🗺️
  • Relationships are complex and multi-directional

📚 2. What is a Stack?

🍽️ The Plate Analogy — Your Best Friend!

Picture a spring-loaded plate dispenser at a restaurant buffet:

       ↑ You can ONLY add here
  ┌─────────────────┐
  │  🍽️  Plate 4  │  ← TOP (Added LAST, Removed FIRST)
  ├─────────────────┤
  │  🍽️  Plate 3  │
  ├─────────────────┤
  │  🍽️  Plate 2  │
  ├─────────────────┤
  │  🍽️  Plate 1  │  ← BOTTOM (Added FIRST, Removed LAST)
  └─────────────────┘
       ↑ You can ONLY remove from here

The golden rules of this dispenser:

• ✅ You can ONLY add a plate on TOP
• ✅ You can ONLY remove a plate from TOP
• ❌ You CANNOT take a plate from the middle or bottom

This is EXACTLY how a Stack data structure works in Python!

🔄 LIFO in Action — Simple Step-by-Step Visualisation

Let's push letters A → B → C, then Pop:

flowchart LR
    A1["Step 1 — PUSH 'A'\nTOP = 0\n \n[ 'A' ] ← TOP"]

    A2["Step 2 — PUSH 'B'\nTOP = 1\n \n[ 'B' ] ← TOP\n[ 'A' ]      "]

    A3["Step 3 — PUSH 'C'\nTOP = 2\n \n[ 'C' ] ← TOP\n[ 'B' ]      \n[ 'A' ]      "]

    A4["Step 4 — POP\nReturns 'C'\n \n[ 'B' ] ← TOP\n[ 'A' ]      "]

    A1 --> A2 --> A3 --> A4

    classDef tryNode fill:none;
    classDef exceptNode fill:none;
    classDef elseNode fill:none;
    classDef normalNode fill:none;

    class A1,A2 normalNode;
    class A3 elseNode;
    class A4 exceptNode;

🌍 Real-World Examples of Stack

• 🍽️ Stack of plates — Buffet dispenser: add/remove only from top
• ↩️ Ctrl+Z (Undo) in Word/Photoshop — Last action is undone first
• 🌐 Browser Back button — Last visited page is the one you go back to first
• 📞 Function calls in Python — Last called function finishes and returns first
• 📚 Stack of books on a desk — You naturally pick up the topmost one first
• 🏷️ Pile of laundry — Last washed clothes sit on top and are used first

🔤 3. Stack Terminology — Know These Cold!

• 📘 TOP — A variable/pointer that always tracks the index of the topmost element in the stack.

  • Empty stack: TOP = -1 (nothing inside!)
  • After first push: TOP = 0
  • PUSH → TOP goes up by 1 | POP → TOP goes down by 1

• 📗 PUSH — The operation to add / insert an element at the TOP of the stack.

  • Like placing a new plate on top of the pile
  • Formula: TOP = TOP + 1 → stack[TOP] = new_element
  • Always check for OVERFLOW before PUSH!

• 📕 POP — The operation to remove / delete the topmost element from the stack.

  • Like lifting the top plate off the pile
  • Formula: val = stack[TOP] → TOP = TOP - 1 → return val
  • Always check for UNDERFLOW before POP!

• 📙 PEEK — The operation to view / read the topmost element without removing it.

  • Like reading the title of the top book without picking it up 👀
  • Returns stack[TOP] or stack[-1] — TOP does NOT change
  • Also called: "Top value", "Front", or just "Look"

• 📓 isEmpty() — A function that checks if the stack has zero elements.

  • Returns True if TOP == -1 (or len(stack) == 0)
  • Returns False otherwise
  • MUST be called before every POP and PEEK!

• 📒 isFull() — A function that checks if the stack has reached its maximum capacity.

  • Returns True if len(stack) == MAX
  • Only applies to fixed-size stacks (unlimited in Python lists by default)
  • MUST be called before every PUSH!

⚙️ 4. Implementation of Stack in Python

Python makes stack implementation incredibly simple because Python lists already behave like stacks — we just need to use them correctly!

🔧 Method 1 — Simple Stack (No Size Limit)

# ====================================================
# STACK IMPLEMENTATION — Method 1 (Simple, Unlimited)
# ====================================================

stack = []    # An empty list is our empty stack!

# ── PUSH ──────────────────────────────────────────
def push(stack, item):
    stack.append(item)        # append() adds to end = TOP
    print(f"Pushed: {item}  |  Stack now: {stack}")

# ── POP ───────────────────────────────────────────
def pop(stack):
    if len(stack) == 0:       # isEmpty check first!
        print("Stack Underflow! Stack is empty. Cannot pop.")
        return None
    item = stack.pop()        # pop() removes from end = TOP
    print(f"Popped: {item}  |  Stack now: {stack}")
    return item

# ── PEEK ──────────────────────────────────────────
def peek(stack):
    if len(stack) == 0:
        print("Stack is empty! Nothing to peek at.")
        return None
    return stack[-1]          # -1 = last element = TOP

# ── isEmpty ───────────────────────────────────────
def isEmpty(stack):
    return len(stack) == 0    # True if empty, False if has elements

# ── SIZE ──────────────────────────────────────────
def size(stack):
    return len(stack)         # Count of elements in stack

# ── TESTING ───────────────────────────────────────
push(stack, 10)
push(stack, 20)
push(stack, 30)
print("Top element:", peek(stack))    # 30
print("Stack size :", size(stack))    # 3
pop(stack)                            # Removes 30
pop(stack)                            # Removes 20
pop(stack)                            # Removes 10
pop(stack)                            # ERROR: Underflow!

🔧 Method 2 — Fixed-Size Stack ⭐ (CBSE Exam Standard)

# ====================================================
# STACK IMPLEMENTATION — Method 2 (Fixed Size, CBSE)
# ====================================================

MAX = 5        # Maximum capacity of our stack
stack = []     # Start with empty stack

# ── PUSH (with Overflow protection) ───────────────
def push(stack, item):
    if len(stack) == MAX:             # Check if FULL
        print("Stack Overflow! Cannot add. Stack is full.")
    else:
        stack.append(item)
        print(f"Pushed: {item} successfully!")

# ── POP (with Underflow protection) ───────────────
def pop(stack):
    if len(stack) == 0:               # Check if EMPTY
        print("Stack Underflow! Cannot remove. Stack is empty.")
        return None
    else:
        item = stack.pop()
        print(f"Popped: {item} successfully!")
        return item

# ── PEEK ──────────────────────────────────────────
def peek(stack):
    if len(stack) == 0:
        print("Stack is empty! Nothing at top.")
        return None
    return stack[len(stack) - 1]      # Same as stack[-1]

# ── isEmpty ───────────────────────────────────────
def isEmpty(stack):
    return len(stack) == 0

# ── isFull ────────────────────────────────────────
def isFull(stack):
    return len(stack) == MAX

# ── DISPLAY (show from Top to Bottom) ─────────────
def display(stack):
    if len(stack) == 0:
        print("Stack is Empty!")
    else:
        print("\n  Stack (Top to Bottom):")
        print("  +-----------+")
        for i in range(len(stack) - 1, -1, -1):   # Reverse loop
            label = " <- TOP" if i == len(stack) - 1 else ""
            print(f"  | {str(stack[i]):^9} |{label}")
        print("  +-----------+")

# ── TESTING ───────────────────────────────────────
push(stack, 'A')
push(stack, 'B')
push(stack, 'C')
display(stack)
print("Top element:", peek(stack))
pop(stack)
display(stack)

🔄 5. Operations on Stack — with Algorithms

📥 PUSH Operation — Inserting an Element

flowchart TD
    A["START\nCALL push(element)"]
    B{"Is Stack FULL?\nlen(stack) == MAX"}
    C["Print OVERFLOW\nStack is Full!\nEXIT — Do Nothing"]
    D["stack.append(element)\nTOP = TOP + 1"]
    E["Element Added\nSuccessfully!"]
    F["END"]

    A --> B
    B -->|"YES — Full!"| C
    B -->|"NO — Space available"| D
    D --> E
    E --> F

    classDef tryNode fill:none;
    classDef exceptNode fill:none;
    classDef elseNode fill:none;
    classDef normalNode fill:none;

    class B tryNode;
    class C exceptNode;
    class D,E elseNode;
    class A,F normalNode;

📤 POP Operation — Removing an Element

flowchart TD
    A["START\nCALL pop()"]
    B{"Is Stack EMPTY?\nlen(stack) == 0\nTOP == -1"}
    C["Print UNDERFLOW\nStack is Empty!\nEXIT — Return None"]
    D["val = stack[TOP]\nval = stack.pop()"]
    E["TOP = TOP - 1\nElement Removed!"]
    F["Return val\nto Caller"]
    G["END"]

    A --> B
    B -->|"YES — Empty!"| C
    B -->|"NO — Has elements"| D
    D --> E
    E --> F
    F --> G

    classDef tryNode fill:none;
    classDef exceptNode fill:none;
    classDef elseNode fill:none;
    classDef normalNode fill:none;

    class B tryNode;
    class C exceptNode;
    class D,E,F elseNode;
    class A,G normalNode;

👁️ PEEK Operation — Viewing the Top

# PEEK — The "look but don't touch" operation!
def peek(stack):
    if len(stack) == 0:           # Safety check first
        print("Stack is empty! Nothing to peek at.")
        return None
    return stack[-1]              # Return TOP element — NO removal!

📊 Complete Stack Trace — Master This for Exams!

Given operations: Push(5) → Push(10) → Push(15) → Pop() → Push(20) → Peek()

🖥️ Complete Menu-Driven Stack Program ⭐ (Board Exam 5 Marks)

# ========================================================
# COMPLETE MENU-DRIVEN STACK PROGRAM — CBSE BOARD STANDARD
# ========================================================

MAX = 10
stack = []

def push(stack, item):
    if len(stack) == MAX:
        print("Stack Overflow! Cannot add. Stack is full.")
    else:
        stack.append(item)
        print(f"'{item}' pushed successfully onto the stack.")

def pop(stack):
    if len(stack) == 0:
        print("Stack Underflow! Stack is empty. Nothing to pop.")
        return None
    else:
        item = stack.pop()
        print(f"'{item}' popped successfully from the stack.")
        return item

def peek(stack):
    if len(stack) == 0:
        print("Stack is empty! No top element.")
        return None
    else:
        print(f"Top element is: {stack[-1]}")
        return stack[-1]

def display(stack):
    if len(stack) == 0:
        print("Stack is empty! Nothing to display.")
    else:
        print("\n--- Stack (Top to Bottom) ---")
        for i in range(len(stack) - 1, -1, -1):
            print(f"  {stack[i]}")
        print("----------------------------")

# Main Program Loop
while True:
    print("\n======= STACK MENU =======")
    print("  1. Push an element")
    print("  2. Pop an element")
    print("  3. Peek (view top)")
    print("  4. Display stack")
    print("  5. Exit")
    print("==========================")
    choice = int(input("Enter your choice (1-5): "))

    if choice == 1:
        item = input("Enter element to push: ")
        push(stack, item)
    elif choice == 2:
        pop(stack)
    elif choice == 3:
        peek(stack)
    elif choice == 4:
        display(stack)
    elif choice == 5:
        print("Goodbye! Happy Coding! 👋")
        break
    else:
        print("Invalid choice! Please enter 1–5.")

🌍 6. Applications of Stack

• 🔄 Function Call Management (Call Stack) — Every time Python calls a function, the current state (line number, local variables) is PUSHED onto an internal call stack. When the function finishes, its state is POPPED and Python continues from where it left off.

  • This is exactly how recursion works under the hood!
  • Too many nested calls → Stack overflows → Python gives RecursionError!
  • Use sys.setrecursionlimit() to control this

• ↩️ Undo / Redo Operations — MS Word, Photoshop, VS Code — every action you perform is PUSHED onto an undo stack. Ctrl+Z POPS the last action and reverses it. Ctrl+Y uses a second stack for redo!

  • Undo = POP from undo stack
  • Redo = POP from redo stack

• 🌐 Browser Navigation — Every webpage you visit is PUSHED onto a history stack. The Back button POPS the current page, revealing the previous one. A separate stack handles the Forward button.

  • This is exactly why "Back" takes you to the LAST visited page!

• 🔡 Expression Conversion & Evaluation — Compilers use stacks to convert human-readable Infix expressions like A+B*C into Postfix ABC*+ which is much easier for computers to evaluate without confusion about operator precedence.

• 🔤 String Reversal — Push every character of a string onto a stack, then pop them all — they come out in perfect reverse order because of LIFO!

  • "PYTHON" pushed char-by-char → pop → "NOHTYP"

• 🔢 Balanced Parentheses Checking — Every compiler/interpreter checks if your code has balanced brackets ( ) { } [ ]. They use a stack — push every opening bracket, pop when a closing bracket is found, check for mismatch!

💻 Application Code 1 — Reverse a String Using Stack

# ================================================
# APPLICATION: String Reversal Using Stack
# (Very easy to understand — perfect for exams!)
# ================================================
def reverse_string(text):
    stack = []

    # STEP 1: PUSH all characters one by one
    print(f"Original string: '{text}'")
    print("\nPUSHING characters:")
    for char in text:
        stack.append(char)
        print(f"  Pushed '{char}'  ->  Stack: {stack}")

    # STEP 2: POP all characters (they come out reversed!)
    reversed_text = ""
    print("\nPOPPING characters:")
    while len(stack) > 0:
        char = stack.pop()
        reversed_text += char
        print(f"  Popped '{char}'  ->  Stack: {stack}")

    return reversed_text

# Test it!
original = "PYTHON"
result = reverse_string(original)
print(f"\nOriginal : {original}")
print(f"Reversed : {result}")

# OUTPUT:
# Original : PYTHON
# Reversed : NOHTYP

💻 Application Code 2 — Check Palindrome Using Stack

# ================================================
# APPLICATION: Palindrome Check Using Stack
# ================================================
def is_palindrome(text):
    stack = []
    text = text.upper()           # Ignore case

    # Push all characters
    for char in text:
        stack.append(char)

    # Pop all characters to get reversed string
    reversed_text = ""
    while len(stack) > 0:
        reversed_text += stack.pop()

    if text == reversed_text:
        print(f"'{text}' is a PALINDROME ✅")
    else:
        print(f"'{text}' is NOT a palindrome ❌")

# Test cases
is_palindrome("MADAM")     # PALINDROME ✅
is_palindrome("RACECAR")   # PALINDROME ✅
is_palindrome("LEVEL")     # PALINDROME ✅
is_palindrome("PYTHON")    # NOT a palindrome ❌

📋 Board Exam Questions (Previous Year Style)

📌 1 Mark Questions

1. Define Stack. Name the principle it follows.
2. What is LIFO? Give one real-life example.
3. What is Stack Overflow? When does it occur?
4. What is Stack Underflow? When does it occur?
5. What is the initial value of TOP in an empty stack?
6. Write the Python statement to add element x to stack S.
7. Write the Python statement to remove the top element from stack S.
8. What does the PEEK operation do? How is it different from POP?
9. Name any two real-world applications of Stack.
10. What will happen if pop() is called on an empty Python list?

📌 2 Mark Questions

1. Write a Python function to PUSH an element into a stack (MAX = 5). Handle overflow.
2. Write a Python function to POP an element from a stack. Handle underflow.
3. Trace the following operations (MAX = 4). Show stack state and TOP after each step: Push(3), Push(7), Push(1), Pop(), Push(9), Peek()
4. Differentiate between Stack Overflow and Stack Underflow with examples.
5. Write Python functions isEmpty(stack) and isFull(stack) for a stack of MAX size 5.
6. Convert the Infix expression A + B * C to Postfix. Show steps.
7. Convert (A + B) * C to both Prefix and Postfix notation.

📌 3 Mark Questions

1. Write a Python program implementing a stack with PUSH, POP, and PEEK operations.
2. Write a Python function to reverse a string using a stack. Trace with "INDIA".
3. Explain the LIFO principle with an example showing at least 4 stack operations.
4. Write a Python function to check balanced parentheses in a given expression.
5. Convert the following to Postfix:
   • A * B + C * D
   • (A + B) * (C - D)
   • A + B * C - D / E

📌 4–5 Mark Questions

1. Write a menu-driven Python program for a stack with: Push, Pop, Peek, Display, Exit. Handle Overflow and Underflow. (5 marks)
2. Write a Python function to check balanced parentheses using a stack. Show output for 3 test cases. (4 marks)
3. Explain any four applications of Stack with real-world examples. (4 marks)
4. What is a Stack? Explain PUSH and POP operations with algorithms and Python code. (5 marks)

🧩 Practice Problems

🎯 Problem 1 — Trace Exercise (Draw It Yourself First!)

Perform the following operations on a stack (MAX = 4). Show stack state and TOP after each step:

Push(10), Push(20), Pop(), Push(30), Push(40), Push(50), Push(60), Pop()

Solution:

🎯 Problem 2 — Find the Output

What is the output of this Python code?

stack = []
stack.append(5)
stack.append(10)
stack.append(15)
print(stack[-1])         # Line A
stack.pop()
stack.append(20)
print(stack)             # Line B
print(len(stack))        # Line C

Answer with explanation:

🎯 Problem 3 — Write This Function!

Write a Python function display_stack(stack) that prints the stack from Top to Bottom with neat formatting.

def display_stack(stack):
    if len(stack) == 0:
        print("Stack is Empty!")
    else:
        print("\n  +------------+")
        for i in range(len(stack) - 1, -1, -1):   # Top to Bottom
            label = " <- TOP" if i == len(stack) - 1 else ""
            print(f"  | {str(stack[i]):^10} |{label}")
        print("  +------------+")

# Test it
my_stack = [1, 2, 3, 4]
display_stack(my_stack)

🎯 Problem 4 — Error Spotting

Find the error(s) in this PUSH function:

def push(stack, item):
    stack.append(item)    # Line 1
    if len(stack) == MAX: # Line 2
        print("Overflow") # Line 3

Answer: The Overflow check (Line 2) must happen BEFORE append() (Line 1), not after! Appending first and then checking means you've already added to a full stack. The correct order is: check first → then append if safe.

✅ Last-Minute Exam Checklist

• [ ] 📌 I can define Stack and explain LIFO in one sentence
• [ ] 📌 I know 4 real-world examples of LIFO / Stack applications
• [ ] 📌 I know that empty stack = [] OR TOP = -1
• [ ] 📌 I know PUSH algorithm: check full → TOP+1 → insert
• [ ] 📌 I know POP algorithm: check empty → save val → TOP−1 → return val
• [ ] 📌 I can write PEEK: return top without removing
• [ ] 📌 I can write isEmpty() and isFull() functions
• [ ] 📌 I know Python: append() = PUSH, pop() = POP, [-1] = TOP
• [ ] 📌 I can perform a stack trace and show state after every operation
• [ ] 📌 I can show OVERFLOW and UNDERFLOW in my trace/code
• [ ] 📌 I can write the string reversal code using a stack
• [ ] 📌 I can write the balanced parentheses checking code