Unit 1: Computational Thinking & Programming - 2
Chapter 3: Stack Data Structure Implementation
1. What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle - the last element added is the first one to be removed.
Real-life analogies: a stack of plates (you add/remove from the top only), a browser's "Back" button, the "Undo" feature in an editor, or a stack of books on a desk.
2. Stack Operations
| Operation | Meaning |
|---|---|
| PUSH | Insert a new element onto the top of the stack |
| POP | Remove and return the element currently at the top |
| PEEK / TOP | View the top element without removing it |
| isEmpty() | Check whether the stack has zero elements |
| isFull() | Check whether the stack has reached its maximum capacity (relevant for fixed-size stacks) |
- Overflow: Attempting to PUSH onto a stack that is already full.
- Underflow: Attempting to POP from a stack that is already empty.
3. Implementing a Stack Using a Python List
Python's built-in list already provides exactly the methods a stack needs: append() behaves as PUSH, and pop() behaves as POP (both operate on the end of the list, which we treat as the "top").
stack = []
def push(element):
stack.append(element)
print(element, "pushed to stack.")
def pop():
if isEmpty():
print("Stack Underflow! Cannot pop from an empty stack.")
else:
removed = stack.pop()
print(removed, "popped from stack.")
return removed
def peek():
if isEmpty():
print("Stack is empty.")
else:
return stack[-1] # last element = top of stack
def isEmpty():
return len(stack) == 0
# Demonstration
push(10)
push(25)
push(40)
print("Top element:", peek()) # 40
pop() # 40 popped
print(stack) # [10, 25]
4. Classic Board-Exam Pattern: Stack of Dictionaries/Records
A very common CBSE question style involves a list of dictionaries (simulating database records), where you must push the records satisfying a condition onto a stack, then pop and display them (which naturally reverses their order).
def push_selected(records, stack):
"""Push the name of every student who scored above 80 onto the stack."""
for rec in records:
if rec["marks"] > 80:
stack.append(rec["name"])
def pop_all(stack):
"""Pop and display all names - LIFO order, so the last one pushed appears first."""
while stack:
print(stack.pop())
students = [
{"name": "Aman", "marks": 75},
{"name": "Bina", "marks": 92},
{"name": "Chirag", "marks": 88},
]
call_stack = []
push_selected(students, call_stack)
print(call_stack) # ['Bina', 'Chirag']
pop_all(call_stack) # Chirag (printed first - last one pushed)
# Bina
5. Applications of Stacks
- Expression Evaluation: Converting and evaluating infix/postfix expressions.
- Balanced Parentheses Checking: Push opening brackets, pop and match when a closing bracket is seen.
- Undo/Redo functionality in text editors.
- Function Call Management: Every program uses an internal "call stack" to keep track of function calls (which is also why deep, unterminated recursion causes a stack overflow error).
- Browser History: The back button pops the most recently visited page.
6. Board Exam Focus Questions
Q1. Write a function Push_Even(L) that pushes all the even numbers from list L onto a stack named even_stack.
even_stack = []
def Push_Even(L):
for num in L:
if num % 2 == 0:
even_stack.append(num)
Push_Even([12, 7, 18, 25, 30])
print(even_stack) # [12, 18, 30]
Q2. Trace the output of the following code:
s = []
s.append(5)
s.append(10)
s.append(15)
s.pop()
s.append(20)
print(s)
Answer: [5, 10, 20] — push 5, push 10, push 15 → [5, 10, 15]; pop removes 15 → [5, 10]; push 20 → [5, 10, 20].
Q3. What happens when pop() is called on an empty Python list directly, without a custom isEmpty() check?
Answer: Python raises an IndexError: pop from empty list. This is exactly why a custom isEmpty() check (stack underflow check) is written before calling pop() in stack implementations - to handle the error gracefully instead of crashing the program.