Chapter 3: Stack

CBSE Unit: Unit 1, Computational Thinking and Programming, 2 (40 marks) Marks Weightage: ~5-8 marks (1 MCQ + 1 program/output question typically) Priority: HIGH, always asked in board exam, predictable questions

---

Key Concepts

3.1 What is a Data Structure?

• A mechanism to store, organise and access data with efficient operations
• Linear data structures: elements in sequence (stack, queue, list), String, List, Tuple = built-in Python data structures

3.2 What is a Stack?

• Linear data structure following LIFO (Last In First Out) principle, Elements added/removed from ONE end only: TOP
• Think: pile of plates, stack of books, bangles on wrist

3.3 Real-World Applications, Pile of plates/books (physical)

• Undo/Redo in text editors
• Browser back button - history stored as stack
• Parenthesis matching in compilers
• Function call stack in programming

3.4 Stack Operations

Operation	Description	Condition
PUSH	Insert element at TOP	Overflow if stack is full
POP	Remove element from TOP	Underflow if stack is empty
peek/top	View TOP element without removing	Check empty first
isEmpty	Check if stack has no elements	-
size	Count elements in stack	-

Key terms:

• Overflow: trying to PUSH into a full stack
• Underflow: trying to POP from an empty stack

---

Implementation in Python Using List

Complete Stack Implementation

# Create empty stack
stack = []

# isEmpty -  check if stack is empty
def isEmpty(stack):
    if len(stack) == 0:
        return True
    else:
        return False

# PUSH -  add element at top
def push(stack, element):
    stack.append(element)

# POP -  remove and return top element
def pop(stack):
    if isEmpty(stack):
        print("Underflow! Stack is empty")
        return None
    else:
        return stack.pop()

# peek/top -  view top element
def peek(stack):
    if isEmpty(stack):
        print("Stack is empty")
        return None
    else:
        return stack[len(stack) - 1]
        # OR: return stack[-1]

# size -  number of elements
def size(stack):
    return len(stack)

# display -  show all elements (top to bottom)
def display(stack):
    if isEmpty(stack):
        print("Stack is empty")
    else:
        for i in range(len(stack) - 1, -1, -1):
            print(stack[i])

Using the Stack

stack = []
push(stack, "glass1")     # stack: ['glass1']
push(stack, "glass2")     # stack: ['glass1', 'glass2']
print(size(stack))        # 2
item = pop(stack)         # item = 'glass2', stack: ['glass1']
push(stack, "glass3")     # stack: ['glass1', 'glass3']
print(peek(stack))        # 'glass3'
display(stack)            # glass3, glass1

Key insight: Python list has no size limit → stack never overflows (only underflow possible)

---

Arithmetic Expression Notations

Three Notations

Notation	Operator Position	Example	Equivalent
Infix	Between operands	x + y	Normal math
Prefix (Polish)	Before operands	+ x y
Postfix (Reverse Polish)	After operands	x y +

More Examples

Infix	Prefix	Postfix
x * y + z	+ * x y z	x y * z +
3 * (4 + 5)	* 3 + 4 5	3 4 5 + *
(x + y) / (z * 5)	/ + x y * z 5	x y + z 5 * /

Why postfix/prefix? No parentheses needed, operator position determines evaluation order.

Infix to Postfix Conversion (Using Stack)

Algorithm:

1. Create empty string postExp and empty stack
2. For each character in infix expression:

• If operand → append to postExp
• If ( → push onto stack
• If ) → pop and append until matching ( found
• If operator → if lower precedence than stack top, pop and append; then push current operator

3. Pop remaining stack elements to postExp

Precedence: *, / > +, -

Example: (x + y) / (z * 8) → Postfix

Symbol	Action	Stack	postExp
(	Push	(
x	Append	(	x
+	Push	( +	x
y	Append	( +	xy
)	Pop till (		xy+
/	Push	/	xy+
(	Push	/ (	xy+
z	Append	/ (	xy+z
*	Push	/ ( *	xy+z
8	Append	/ ( *	xy+z8
)	Pop till (	/	xy+z8*
End	Pop all		xy+z8*/

Result: xy+z8*/

Postfix Expression Evaluation (Using Stack)

Algorithm:

1. For each character in postfix expression:

• If operand → push onto stack
• If operator → pop two operands, apply operator, push result

2. Final value on stack = result

Example: 7 8 2 * 4 / +

Symbol	Action	Stack
7	Push	[7]
8	Push	[7, 8]
2	Push	[7, 8, 2]
*	Pop 2,8 → 8*2=16, push	[7, 16]
4	Push	[7, 16, 4]
/	Pop 4,16 → 16/4=4, push	[7, 4]
+	Pop 4,7 → 7+4=11, push	[11]

Result: 11

---

Important Programs for Board Exam

Program 1: Stack of odd numbers

stack = []
n = int(input("How many numbers? "))
for i in range(n):
    num = int(input("Enter number: "))
    if num % 2 != 0:
        stack.append(num)

largest = None
while stack:
    item = stack.pop()
    print(item, end=" ")
    if largest is None or item > largest:
        largest = item
print(f"\nLargest odd: {largest}")

Program 2: Reverse a string using stack

def reverse_string(s):
    stack = []
    for ch in s:
        stack.append(ch)
    result = ""
    while stack:
        result += stack.pop()
    return result

print(reverse_string("Hello"))  # olleH

Program 3: Menu-driven stack program (VERY common in boards)

stack = []
while True:
    print("\n1. Push\n2. Pop\n3. Display\n4. Exit")
    choice = int(input("Enter choice: "))
    if choice == 1:
        item = input("Enter element: ")
        stack.append(item)
        print(f"Pushed: {item}")
    elif choice == 2:
        if stack:
            print(f"Popped: {stack.pop()}")
        else:
            print("Underflow! Stack is empty")
    elif choice == 3:
        if stack:
            print("Stack (top to bottom):")
            for i in range(len(stack)-1, -1, -1):
                print(stack[i])
        else:
            print("Stack is empty")
    elif choice == 4:
        break

---

Common Board Exam Question Patterns

1. MCQ: True/False about stack properties (1 mark)
2. Output question: What does this stack code print? (2 marks)
3. Trace: Show stack state after push/pop operations (2-3 marks)
4. Convert: Infix to postfix using stack (3-4 marks)
5. Evaluate: Postfix expression using stack (3-4 marks)
6. Program: Implement stack with specific logic (4-5 marks)
7. Short answer: Applications of stack (2 marks)

---

Key Points Students Miss

1. LIFO not FIFO, stack is NOT a queue
2. append() = PUSH, pop() = POP, use list's built-in methods
3. In Python, no overflow possible (list grows dynamically), only underflow
4. Always check isEmpty() before POP, prevents IndexError
5. When displaying stack, show from TOP to BOTTOM (reverse order of list)
6. In postfix evaluation: second popped element is LEFT operand (order matters for, and /)

• Pop A, Pop B → result = B operator A (not A operator B)

7. Infix to postfix: only operators go on stack, operands go directly to output string
8. Postfix evaluation: only operands go on stack