# 📦 Data Structures — Stack
::: grid
::: card 🌐 | Introduction | What are Data Structures and why computers need them | Linear, Non-Linear
::: card 📚 | What is a Stack? | LIFO principle explained with fun real-world analogies | LIFO, TOP
::: card 🔤 | Stack Terminology | TOP, PUSH, POP, PEEK, Overflow, Underflow — all key terms | Concepts
::: card ⚙️ | Implementation | Stack using Python list — Simple & Fixed Size (CBSE Style) | list, append, pop
::: card 🔄 | Operations | PUSH, POP, PEEK with step-by-step algorithms & flowcharts | Algorithm, Code
::: card 🌍 | Applications | Undo, Browser, String Reversal, Balanced Brackets & more! | Real World
:::
---
## 🌐 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**.
> [!NOTE]
> **Memory Trick 🧠:** Data Structure answers the question: **"HOW is data arranged in memory?"**
> Just like a bookshelf can be arranged alphabetically or by subject — the **arrangement itself** is the data structure!
### 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
> [!TIP]
> **Study Strategy 💡:** For CBSE Class 12, you are primarily tested on **Stack**. These topics carry **3–4 marks** in board exams — master them thoroughly!
---
## 📚 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!**
> [!IMPORTANT]
> **Board Exam Hotspot 📋:** A **Stack** is a **linear data structure** that follows the **LIFO** (Last In, First Out) principle.
>
> **LIFO = The element inserted LAST is the element removed FIRST.**
### 🔄 LIFO in Action — Simple Step-by-Step Visualisation
Let's push letters A → B → C, then Pop:
```mermaid
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;
```
> [!NOTE]
> **Memory Trick 🧠:**
> - **LIFO** = **L**ast **I**n **F**irst **O**ut
> - Easy way to remember: *"The last book you placed on your desk is the first one you pick up!"* 📚
> - Or think of a gun magazine — the last bullet loaded is the first one fired! 🔫
### 🌍 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!
> [!WARNING]
> **Common Mistake ⚠️ — Overflow vs Underflow Confusion!**
>
> | Condition | What It Means | When It Happens |
> |-----------|--------------|-----------------|
> | **OVERFLOW** | Stack is **FULL** — can't PUSH any more | Pushing into a full stack |
> | **UNDERFLOW** | Stack is **EMPTY** — can't POP anything | Popping from an empty stack |
>
> 🧠 Simple trick: **"Over"** = too much on top (full) | **"Under"** = nothing underneath (empty)
---
## ⚙️ 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!
> [!RULE]
> **Key Rule 🔑 — Python ↔ Stack Mapping Table:**
>
> | Stack Operation | Python Code | What It Does |
> |----------------|-------------|-------------|
> | Create empty stack | `stack = []` | Initialises empty list |
> | PUSH element | `stack.append(item)` | Adds to the END (= TOP) |
> | POP element | `stack.pop()` | Removes from END (= TOP) |
> | PEEK (view top) | `stack[-1]` | Reads last element without removing |
> | isEmpty check | `len(stack) == 0` | True if list is empty |
> | isFull check | `len(stack) == MAX` | True if list has MAX elements |
> | Size of stack | `len(stack)` | Number of elements currently |
### 🔧 Method 1 — Simple Stack (No Size Limit)
```python
# ====================================================
# 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)
```python
# ====================================================
# 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)
```
> [!TIP]
> **Study Strategy 💡:** Some CBSE exam questions show `TOP` as an integer variable (`TOP = -1` for empty). Both styles give the same result. In Python, using `len(stack) - 1` is simpler and less error-prone. Practice both — you may see either style in your question paper!
---
## 🔄 5. Operations on Stack — Deep Dive with Algorithms
### 📥 PUSH Operation — Inserting an Element
> [!RULE]
> **Key Rule 🔑 — PUSH Algorithm:**
> 1. **Check** if stack is FULL → If YES, print "**Overflow**" and STOP ❌
> 2. If NOT full → increment TOP: `TOP = TOP + 1`
> 3. Place element at new TOP: `stack[TOP] = element`
> 4. **Done!** Element successfully added ✅
```mermaid
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
> [!RULE]
> **Key Rule 🔑 — POP Algorithm:**
> 1. **Check** if stack is EMPTY (TOP == -1) → If YES, print "**Underflow**" and STOP ❌
> 2. If NOT empty → save top: `val = stack[TOP]`
> 3. Decrement TOP: `TOP = TOP - 1`
> 4. **Return** `val` ✅
```mermaid
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
```python
# 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!
```
> [!NOTE]
> **Memory Trick 🧠 — POP vs PEEK:**
> - 🤏 **POP** = "Take the top plate away" — element is **GONE** from stack
> - 👀 **PEEK** = "Look at the top plate" — element **STAYS** in stack
>
> The key difference: After POP, the stack CHANGES. After PEEK, stack is UNCHANGED!
### 📊 Complete Stack Trace — Master This for Exams!
**Given operations:** `Push(5) → Push(10) → Push(15) → Pop() → Push(20) → Peek()`
| Step | Operation | Stack (Bottom → Top) | TOP | Returns | Notes |
|------|-----------|----------------------|-----|---------|-------|
| 0 | (Start) | `[ ]` | -1 | — | Empty stack |
| 1 | Push(5) | `[5]` | 0 | — | 5 added ✅ |
| 2 | Push(10) | `[5, 10]` | 1 | — | 10 on top ✅ |
| 3 | Push(15) | `[5, 10, 15]` | 2 | — | 15 on top ✅ |
| 4 | Pop() | `[5, 10]` | 1 | 15 | 15 removed ✅ |
| 5 | Push(20) | `[5, 10, 20]` | 2 | — | 20 on top ✅ |
| 6 | Peek() | `[5, 10, 20]` | 2 | 20 | Stack unchanged! 👀 |
> [!IMPORTANT]
> **Board Exam Hotspot 📋:** Stack trace questions carry **2–3 marks** and appear in almost every board exam! Golden rules for full marks:
> 1. Show the **complete stack state** after EVERY single operation
> 2. Show **TOP value** at each step
> 3. Explicitly mention **OVERFLOW / UNDERFLOW** when it occurs
> 4. Show the **return value** of Pop() and Peek()
---
## 🖥️ Complete Menu-Driven Stack Program ⭐ (Board Exam 5 Marks)
```python
# ========================================================
# 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
```python
# ================================================
# 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
```python
# ================================================
# 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 ❌
```
---
## ⚡ Quick Revision — Everything on One Page!
> [!IMPORTANT]
> **Board Exam Hotspot 📋 — Memorise These Key Points:**
>
> ✅ **Stack** = Linear DS following **LIFO** (Last In, First Out)
>
> ✅ **PUSH** = Add element → Check Overflow → TOP = TOP + 1 → Insert
>
> ✅ **POP** = Remove element → Check Underflow → Save val → TOP = TOP − 1 → Return val
>
> ✅ **PEEK** = View TOP element → NO removal → Stack unchanged
>
> ✅ **Overflow** = PUSH on FULL stack (error condition)
>
> ✅ **Underflow** = POP on EMPTY stack (error condition)
>
> ✅ **Empty Stack** → `stack = []` OR `TOP = -1`
>
> ✅ **Python PUSH** = `list.append(item)` | **Python POP** = `list.pop()` | **Python TOP** = `list[-1]`
>
> ✅ **TOP starts at −1** (empty) and changes with every push/pop
>
> ✅ **Applications**: Function calls, Undo/Redo, Browser Back, String Reversal, Balanced Brackets, Expression Conversion
---
## 📋 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:**
| # | Operation | Stack State (B → T) | TOP | Note |
|---|-----------|---------------------|-----|------|
| 0 | Start | `[ ]` | -1 | Empty ✅ |
| 1 | Push(10) | `[10]` | 0 | OK ✅ |
| 2 | Push(20) | `[10, 20]` | 1 | OK ✅ |
| 3 | Pop() | `[10]` | 0 | Returns **20** ✅ |
| 4 | Push(30) | `[10, 30]` | 1 | OK ✅ |
| 5 | Push(40) | `[10, 30, 40]` | 2 | OK ✅ |
| 6 | Push(50) | `[10, 30, 40, 50]` | 3 | Stack is NOW FULL |
| 7 | Push(60) | `[10, 30, 40, 50]` | 3 | ❌ **OVERFLOW!** Stack unchanged |
| 8 | Pop() | `[10, 30, 40]` | 2 | Returns **50** ✅ |
### 🎯 Problem 2 — Find the Output
**What is the output of this Python code?**
```python
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:**
| Line | Output | Why? |
|------|--------|------|
| Line A | `15` | `stack[-1]` = topmost element = 15 |
| Line B | `[5, 10, 20]` | 15 was popped, 20 was pushed |
| Line C | `3` | Stack has 3 elements: 5, 10, 20 |
### 🎯 Problem 3 — Write This Function!
**Write a Python function `display_stack(stack)` that prints the stack from Top to Bottom with neat formatting.**
```python
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:**
```python
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
> [!RULE]
> **Key Rule 🔑 — Tick Every Box Before Walking Into the Exam Hall:**
- [ ] 📌 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
> [!WARNING]
> **The 6 Most Common Exam Mistakes — Don't Fall for These! ⚠️**
>
> ❌ **Mistake 1:** Appending first, then checking overflow → Always **check first!**
>
> ❌ **Mistake 2:** Forgetting Underflow check before POP → Always **check before removing!**
>
> ❌ **Mistake 3:** Confusing POP (removes element) with PEEK (only reads) → **POP changes stack, PEEK doesn't!**
>
> ❌ **Mistake 4:** Not showing step-by-step trace in trace questions → **Always show every state!**
>
> ❌ **Mistake 5:** Ignoring brackets in Infix-to-Postfix conversion → **Brackets always have highest priority!**
>
> ❌ **Mistake 6:** Writing `TOP = -1` for empty but forgetting to update it in algorithm → **TOP must update on every PUSH and POP!**
> [!TIP]
> **Last-Minute Power Tips 💡:**
>
> 🌟 The magic sentence: *"Stack follows LIFO — Last In, First Out!"* — Write this in EVERY stack answer!
>
> 🌟 In Python: `append()` = PUSH and `pop()` = POP — just 2 built-in methods and you have a full stack!
>
> 🌟 For EVERY PUSH function you write: **check Overflow first** — it shows the examiner you understand the concept!
>
> 🌟 For EVERY POP function you write: **check Underflow first** — same reason!
>
> 🌟 In any trace question: draw a neat table with columns — **Operation | Stack State | TOP | Note** — you'll get full marks!
>
> 🌟 Remember the palindrome/reversal trick: push all → pop all → compare with original!
---
::: grid
::: card 🌐 | Introduction | What are Data Structures and why computers need them | Linear, Non-Linear
::: card 📚 | What is a Stack? | LIFO principle explained with fun real-world analogies | LIFO, TOP
::: card 🔤 | Stack Terminology | TOP, PUSH, POP, PEEK, Overflow, Underflow — all key terms | Concepts
::: card ⚙️ | Implementation | Stack using Python list — Simple & Fixed Size (CBSE Style) | list, append, pop
::: card 🔄 | Operations | PUSH, POP, PEEK with step-by-step algorithms & flowcharts | Algorithm, Code
::: card 🌍 | Applications | Undo, Browser, String Reversal, Balanced Brackets & more! | Real World
:::
---
## 🌐 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**.
> [!NOTE]
> **Memory Trick 🧠:** Data Structure answers the question: **"HOW is data arranged in memory?"**
> Just like a bookshelf can be arranged alphabetically or by subject — the **arrangement itself** is the data structure!
### 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
> [!TIP]
> **Study Strategy 💡:** For CBSE Class 12, you are primarily tested on **Stack**. These topics carry **3–4 marks** in board exams — master them thoroughly!
---
## 📚 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!**
> [!IMPORTANT]
> **Board Exam Hotspot 📋:** A **Stack** is a **linear data structure** that follows the **LIFO** (Last In, First Out) principle.
>
> **LIFO = The element inserted LAST is the element removed FIRST.**
### 🔄 LIFO in Action — Simple Step-by-Step Visualisation
Let's push letters A → B → C, then Pop:
```mermaid
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;
```
> [!NOTE]
> **Memory Trick 🧠:**
> - **LIFO** = **L**ast **I**n **F**irst **O**ut
> - Easy way to remember: *"The last book you placed on your desk is the first one you pick up!"* 📚
> - Or think of a gun magazine — the last bullet loaded is the first one fired! 🔫
### 🌍 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!
> [!WARNING]
> **Common Mistake ⚠️ — Overflow vs Underflow Confusion!**
>
> | Condition | What It Means | When It Happens |
> |-----------|--------------|-----------------|
> | **OVERFLOW** | Stack is **FULL** — can't PUSH any more | Pushing into a full stack |
> | **UNDERFLOW** | Stack is **EMPTY** — can't POP anything | Popping from an empty stack |
>
> 🧠 Simple trick: **"Over"** = too much on top (full) | **"Under"** = nothing underneath (empty)
---
## ⚙️ 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!
> [!RULE]
> **Key Rule 🔑 — Python ↔ Stack Mapping Table:**
>
> | Stack Operation | Python Code | What It Does |
> |----------------|-------------|-------------|
> | Create empty stack | `stack = []` | Initialises empty list |
> | PUSH element | `stack.append(item)` | Adds to the END (= TOP) |
> | POP element | `stack.pop()` | Removes from END (= TOP) |
> | PEEK (view top) | `stack[-1]` | Reads last element without removing |
> | isEmpty check | `len(stack) == 0` | True if list is empty |
> | isFull check | `len(stack) == MAX` | True if list has MAX elements |
> | Size of stack | `len(stack)` | Number of elements currently |
### 🔧 Method 1 — Simple Stack (No Size Limit)
```python
# ====================================================
# 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)
```python
# ====================================================
# 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)
```
> [!TIP]
> **Study Strategy 💡:** Some CBSE exam questions show `TOP` as an integer variable (`TOP = -1` for empty). Both styles give the same result. In Python, using `len(stack) - 1` is simpler and less error-prone. Practice both — you may see either style in your question paper!
---
## 🔄 5. Operations on Stack — Deep Dive with Algorithms
### 📥 PUSH Operation — Inserting an Element
> [!RULE]
> **Key Rule 🔑 — PUSH Algorithm:**
> 1. **Check** if stack is FULL → If YES, print "**Overflow**" and STOP ❌
> 2. If NOT full → increment TOP: `TOP = TOP + 1`
> 3. Place element at new TOP: `stack[TOP] = element`
> 4. **Done!** Element successfully added ✅
```mermaid
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
> [!RULE]
> **Key Rule 🔑 — POP Algorithm:**
> 1. **Check** if stack is EMPTY (TOP == -1) → If YES, print "**Underflow**" and STOP ❌
> 2. If NOT empty → save top: `val = stack[TOP]`
> 3. Decrement TOP: `TOP = TOP - 1`
> 4. **Return** `val` ✅
```mermaid
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
```python
# 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!
```
> [!NOTE]
> **Memory Trick 🧠 — POP vs PEEK:**
> - 🤏 **POP** = "Take the top plate away" — element is **GONE** from stack
> - 👀 **PEEK** = "Look at the top plate" — element **STAYS** in stack
>
> The key difference: After POP, the stack CHANGES. After PEEK, stack is UNCHANGED!
### 📊 Complete Stack Trace — Master This for Exams!
**Given operations:** `Push(5) → Push(10) → Push(15) → Pop() → Push(20) → Peek()`
| Step | Operation | Stack (Bottom → Top) | TOP | Returns | Notes |
|------|-----------|----------------------|-----|---------|-------|
| 0 | (Start) | `[ ]` | -1 | — | Empty stack |
| 1 | Push(5) | `[5]` | 0 | — | 5 added ✅ |
| 2 | Push(10) | `[5, 10]` | 1 | — | 10 on top ✅ |
| 3 | Push(15) | `[5, 10, 15]` | 2 | — | 15 on top ✅ |
| 4 | Pop() | `[5, 10]` | 1 | 15 | 15 removed ✅ |
| 5 | Push(20) | `[5, 10, 20]` | 2 | — | 20 on top ✅ |
| 6 | Peek() | `[5, 10, 20]` | 2 | 20 | Stack unchanged! 👀 |
> [!IMPORTANT]
> **Board Exam Hotspot 📋:** Stack trace questions carry **2–3 marks** and appear in almost every board exam! Golden rules for full marks:
> 1. Show the **complete stack state** after EVERY single operation
> 2. Show **TOP value** at each step
> 3. Explicitly mention **OVERFLOW / UNDERFLOW** when it occurs
> 4. Show the **return value** of Pop() and Peek()
---
## 🖥️ Complete Menu-Driven Stack Program ⭐ (Board Exam 5 Marks)
```python
# ========================================================
# 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
```python
# ================================================
# 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
```python
# ================================================
# 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 ❌
```
---
## ⚡ Quick Revision — Everything on One Page!
> [!IMPORTANT]
> **Board Exam Hotspot 📋 — Memorise These Key Points:**
>
> ✅ **Stack** = Linear DS following **LIFO** (Last In, First Out)
>
> ✅ **PUSH** = Add element → Check Overflow → TOP = TOP + 1 → Insert
>
> ✅ **POP** = Remove element → Check Underflow → Save val → TOP = TOP − 1 → Return val
>
> ✅ **PEEK** = View TOP element → NO removal → Stack unchanged
>
> ✅ **Overflow** = PUSH on FULL stack (error condition)
>
> ✅ **Underflow** = POP on EMPTY stack (error condition)
>
> ✅ **Empty Stack** → `stack = []` OR `TOP = -1`
>
> ✅ **Python PUSH** = `list.append(item)` | **Python POP** = `list.pop()` | **Python TOP** = `list[-1]`
>
> ✅ **TOP starts at −1** (empty) and changes with every push/pop
>
> ✅ **Applications**: Function calls, Undo/Redo, Browser Back, String Reversal, Balanced Brackets, Expression Conversion
---
## 📋 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:**
| # | Operation | Stack State (B → T) | TOP | Note |
|---|-----------|---------------------|-----|------|
| 0 | Start | `[ ]` | -1 | Empty ✅ |
| 1 | Push(10) | `[10]` | 0 | OK ✅ |
| 2 | Push(20) | `[10, 20]` | 1 | OK ✅ |
| 3 | Pop() | `[10]` | 0 | Returns **20** ✅ |
| 4 | Push(30) | `[10, 30]` | 1 | OK ✅ |
| 5 | Push(40) | `[10, 30, 40]` | 2 | OK ✅ |
| 6 | Push(50) | `[10, 30, 40, 50]` | 3 | Stack is NOW FULL |
| 7 | Push(60) | `[10, 30, 40, 50]` | 3 | ❌ **OVERFLOW!** Stack unchanged |
| 8 | Pop() | `[10, 30, 40]` | 2 | Returns **50** ✅ |
### 🎯 Problem 2 — Find the Output
**What is the output of this Python code?**
```python
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:**
| Line | Output | Why? |
|------|--------|------|
| Line A | `15` | `stack[-1]` = topmost element = 15 |
| Line B | `[5, 10, 20]` | 15 was popped, 20 was pushed |
| Line C | `3` | Stack has 3 elements: 5, 10, 20 |
### 🎯 Problem 3 — Write This Function!
**Write a Python function `display_stack(stack)` that prints the stack from Top to Bottom with neat formatting.**
```python
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:**
```python
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
> [!RULE]
> **Key Rule 🔑 — Tick Every Box Before Walking Into the Exam Hall:**
- [ ] 📌 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
> [!WARNING]
> **The 6 Most Common Exam Mistakes — Don't Fall for These! ⚠️**
>
> ❌ **Mistake 1:** Appending first, then checking overflow → Always **check first!**
>
> ❌ **Mistake 2:** Forgetting Underflow check before POP → Always **check before removing!**
>
> ❌ **Mistake 3:** Confusing POP (removes element) with PEEK (only reads) → **POP changes stack, PEEK doesn't!**
>
> ❌ **Mistake 4:** Not showing step-by-step trace in trace questions → **Always show every state!**
>
> ❌ **Mistake 5:** Ignoring brackets in Infix-to-Postfix conversion → **Brackets always have highest priority!**
>
> ❌ **Mistake 6:** Writing `TOP = -1` for empty but forgetting to update it in algorithm → **TOP must update on every PUSH and POP!**
> [!TIP]
> **Last-Minute Power Tips 💡:**
>
> 🌟 The magic sentence: *"Stack follows LIFO — Last In, First Out!"* — Write this in EVERY stack answer!
>
> 🌟 In Python: `append()` = PUSH and `pop()` = POP — just 2 built-in methods and you have a full stack!
>
> 🌟 For EVERY PUSH function you write: **check Overflow first** — it shows the examiner you understand the concept!
>
> 🌟 For EVERY POP function you write: **check Underflow first** — same reason!
>
> 🌟 In any trace question: draw a neat table with columns — **Operation | Stack State | TOP | Note** — you'll get full marks!
>
> 🌟 Remember the palindrome/reversal trick: push all → pop all → compare with original!
---