CLASS XII — COMPUTER SCIENCE

CHAPTER 3

Stack
Exam-Optimized Notes | Board + KCET Level

"We're going to be able to ask our computers to monitor things for us..." — Steve Jobs
1. CHAPTER OVERVIEW
Chapter Name
Stack (NCERT Class XII Computer Science — Chapter 3)

Key Themes
• Data structures: definition, purpose, and classification (linear vs non-linear)
• Stack: definition, LIFO principle, and real-world analogies
• PUSH and POP operations: insertion, deletion, overflow, and underflow
• Python implementation of stack using list (append() and pop())
• All five stack functions: isEmpty, opPush, opPop, top, display, size
• Three notations: Infix, Prefix (Polish), and Postfix (Reverse Polish)
• Algorithm 3.1: Infix to Postfix conversion using stack
• Algorithm 3.2: Evaluation of Postfix expression using stack

Real-World Applications
• Undo/Redo in text editors (MS Word, Notepad, Photoshop)
• Browser BACK button — history of visited pages maintained as stack
• Compiler/interpreter: function call stack management
• Parenthesis matching / balanced brackets checking in code
• Reversing strings and sequences
• Memory management: OS call stack for program execution
2. CONCEPTUAL FOUNDATION (DEEP EXPLANATION)
2.1 Data Structure — First Principles
A data structure defines a mechanism to STORE, ORGANISE, and ACCESS data along with OPERATIONS
that can be efficiently performed on that data.
Intuition: Just as a physical library organises books by subject, author, or alphabetically so that retrieval is
efficient, a data structure organises data in memory so that operations on it are fast.
Python's built-in data types (String, List, Tuple, Set, Dictionary) are all data structures. They differ in how they
organise elements and what operations they support efficiently.

Data Structure Organisation Key Property

String Linear sequence of characters Immutable, indexed

List Linear sequence of heterogeneous Mutable, indexed, dynamic size

elements

Stack Linear sequence, LIFO access Insert/delete from ONE end only
(TOP)

Queue Linear sequence, FIFO access Insert at rear, delete from front

Tree Hierarchical (non-linear) Parent-child relationships

Graph Network (non-linear) Nodes connected by edges

2.2 Stack — Intuition from First Principles

Imagine a stack of plates in a cafeteria. When a new plate is added, it is placed ON TOP. When a plate is
needed, it is taken FROM THE TOP. You NEVER add or remove a plate from the bottom or middle — that
would topple the stack.
This is the essence of a stack data structure: insertion (PUSH) and deletion (POP) always happen at ONE
END, called the TOP.

LIFO Principle — The Core Law of Stack

LIFO = Last In, First Out

The element that was INSERTED LAST will be the FIRST one to be REMOVED.
Analogy: A stack of books. The book placed last (on top) is the first one you pick up.

Stack is a LINEAR data structure — elements are organised in a sequence. It is NOT directly available as a
built-in type in Python, but is easily implemented using Python's list.

2.3 PUSH and POP — Deep Understanding

PUSH (Insertion):
 • Adds a new element at the TOP of the stack
• The new element becomes the new TOP
• If the stack has a fixed maximum size and is FULL, adding another element causes OVERFLOW
exception
• In Python's list-based implementation: no fixed size limit (bounded only by available RAM), so
OVERFLOW never occurs

POP (Deletion):
• Removes and RETURNS the element currently at the TOP of the stack
• After POP, the element just below becomes the new TOP
• If the stack is EMPTY and we try to POP, it causes UNDERFLOW exception
• Python's opPop function handles this by checking isEmpty() first

2.4 Why Python List for Stack?

Python's list provides two critical built-in methods for stack:
• append(element): adds element at the END (rightmost) of the list — used as PUSH
• pop(): removes and returns the LAST element of the list — used as POP
By treating the RIGHT END (index -1, or index len-1) as the TOP, we get perfect stack behavior with NO
EXTRA CODE for managing the top pointer.

Key Insight

Because Python list has NO FIXED SIZE, the list-based stack implementation will NEVER cause
OVERFLOW — it only stops when RAM is exhausted. UNDERFLOW is still possible (popping from
empty stack) and must be checked.

2.5 Notations for Arithmetic Expressions — Deep Intuition

When we write x + y, the operator (+) is BETWEEN the operands (x and y). This is called INFIX notation —
the natural way humans write math. But computers evaluate expressions by processing them sequentially.

The problem with Infix: Consider x + y * z. A computer reading left to right encounters + first, but BODMAS
says multiply first. So the computer needs to 'look ahead' and apply precedence rules. This requires complex
logic.

Polish Notation — Jan Lukasiewicz (1920s)

Polish mathematician Jan Lukasiewicz invented PREFIX notation: operators BEFORE operands.
He also introduced POSTFIX (Reverse Polish): operators AFTER operands.
KEY ADVANTAGE: Prefix and Postfix expressions embed the order of evaluation directly in the
expression. No parentheses needed. No precedence lookup. A single left-to-right scan
suffices.
2.6 Operator Precedence — Why It Matters for Infix to Postfix
The conversion algorithm uses operator precedence. Higher precedence operators are executed before lower
ones:

Precedence Level Operators Associativity

Highest (3) ^ (exponentiation) Right to Left

Medium (2) * / (multiply, divide) Left to Right

Lowest (1) + - (add, subtract) Left to Right

Parentheses () N/A — always processed first

2.7 Why Postfix is Used in Compilers

Compilers convert infix expressions (written by programmers) to postfix internally before evaluation. This is
because:
• Single left-to-right scan is sufficient — no back-tracking
• No precedence tables needed during evaluation
• No parentheses needed
• Stack-based evaluation is extremely fast and efficient
3. DEFINITIONS & KEY TERMS

Term Precise Exam-Ready Definition

Data Structure A mechanism to store, organise and access data along

with operations that can be efficiently performed on the
data.

Linear Data Structure A data structure in which elements are organised in a

sequential (linear) order, e.g., Stack, Queue, Array,
Linked List.

Stack A linear data structure in which insertion (PUSH) and

deletion (POP) of elements is done from only one end,
called the TOP of the stack.

LIFO Last-In-First-Out — the principle followed by a stack.

The most recently inserted element is the first one to be
removed.

TOP The end of the stack from which elements are inserted
(PUSH) or deleted (POP). It always points to the most
recently added element.

PUSH The operation of inserting (adding) a new element at

the TOP of the stack. It is an insertion operation.

POP The operation of removing (deleting) the element at the

TOP of the stack and returning its value. It is a deletion
operation.

Overflow An exception/error that occurs when a PUSH operation

is attempted on a FULL stack (i.e., no space for new
elements).

Underflow An exception/error that occurs when a POP operation

is attempted on an EMPTY stack (i.e., no elements to
remove).

Infix Notation An arithmetic expression notation in which binary

operators are placed BETWEEN their operands. E.g., x
+ y, (a * b) - c.

Prefix (Polish) Notation An expression notation introduced by Jan Lukasiewicz

in which operators are placed BEFORE their operands.
E.g., +xy, *-abc.

Postfix (Reverse Polish) An expression notation in which operators are placed

AFTER their operands. E.g., xy+, ab*c-. No
parentheses needed.

4. ALGORITHMS (DETAILED STEP-BY-STEP)

4.1 Algorithm 3.1: Infix to Postfix Conversion
Uses a stack (postStack) to hold operators and parentheses, and a string (postExp) to build the postfix result.
 Operator Precedence for Algorithm

^ (exponent): precedence 3 (highest)

* / (multiply, divide): precedence 2
+ - (add, subtract): precedence 1 (lowest)
( ) parentheses: handle separately — not pushed as operators

Step 1: Create empty string postExp = ''

Step 2: Create empty stack postStack = []
Step 3: INPUT infix expression inExp
Step 4: FOR each character ch in inExp:

CASE 1: ch is LEFT PARENTHESIS '('

→ PUSH '(' onto postStack

CASE 2: ch is RIGHT PARENTHESIS ')'

→ POP from postStack and APPEND to postExp
UNTIL '(' is found (discard the '(' too)
(Both '(' and ')' are discarded — NOT added to postExp)

CASE 3: ch is an OPERATOR (+, -, *, /, ^)

→ WHILE postStack is not empty AND
top of postStack is NOT '(' AND
precedence(top of postStack) >= precedence(ch):
POP from postStack and APPEND to postExp
→ PUSH ch onto postStack

CASE 4: ch is an OPERAND (letter or digit)

→ APPEND ch directly to postExp

Step 5: WHILE postStack is not empty:

POP from postStack and APPEND to postExp

Step 6: OUTPUT postExp (final postfix expression)

KEY RULES to remember:

• Operands → go DIRECTLY to postExp (never pushed onto stack)
• '(' → always PUSHED onto stack
• ')' → POP and append until '(' found; DISCARD both parentheses
• Operator → POP operators of EQUAL OR HIGHER precedence first, then PUSH current
• End of input → POP ALL remaining operators from stack to postExp

4.2 Algorithm 3.2: Evaluation of Postfix Expression

Uses a stack to hold operands. When an operator is encountered, pop two operands, apply the operator, and
push the result back.
 Step 1: Create empty stack evalStack = []
Step 2: INPUT postfix expression postExp
Step 3: FOR each character ch in postExp:

CASE 1: ch is an OPERAND (digit or letter)

→ PUSH ch onto evalStack

CASE 2: ch is an OPERATOR (+, -, *, /, ^)

→ POP top element → operand2
→ POP next element → operand1
(NOTE: operand1 was pushed BEFORE operand2,
so operand1 is the LEFT operand)
→ result = operand1 (operator) operand2
→ PUSH result onto evalStack

Step 4: AFTER processing all characters:

IF evalStack has EXACTLY ONE element:
→ POP and OUTPUT as the final result
ELSE:
→ OUTPUT 'Invalid Postfix Expression'

Critical: Order of Operands When Applying Operator

When operator is found: POP gives operand2 (right operand), then POP gives operand1 (left
operand).
Apply as: operand1 OPERATOR operand2 (NOT operand2 OPERATOR operand1)
Example: For 8 2 / → pop 2 (operand2), pop 8 (operand1) → compute 8/2 = 4, NOT 2/8
5. COMPLETE PYTHON IMPLEMENTATION OF STACK
5.1 All Five Functions
# Initialize an empty stack
glassStack = list()

# 1. isEmpty() — Check if stack is empty

def isEmpty(glassStack):
if len(glassStack) == 0:
return True
else:
return False

# 2. opPush() — Push element onto stack

def opPush(glassStack, element):
[Link](element) # append adds at END (= TOP)

# 3. size() — Return number of elements

def size(glassStack):
return len(glassStack)

# 4. top() — Return topmost element WITHOUT removing it

def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x = len(glassStack)
element = glassStack[x - 1] # last index = TOP
return element

# 5. opPop() — Remove and return topmost element

def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return ([Link]()) # pop() removes from END (= TOP)

# 6. display() — Print all elements (TOP first)

def display(glassStack):
x = len(glassStack)
print('Current elements in the stack are:')
for i in range(x-1, -1, -1): # traverse from last to first
print(glassStack[i])

5.2 Complete Stack Driver Program

def opPush(stack, element):
[Link](element)

def opPop(stack):
if len(stack) == 0:
return None
return [Link]()

def size(stack):
return len(stack)

def top(stack):
if len(stack) == 0:
return None
return stack[-1]

def display(stack):
print("Stack elements:", stack)

glassStack = list()

# Push glass1
element = 'glass1'
print('Pushing element ', element)
opPush(glassStack, element)

# Push glass2
element = 'glass2'
print('Pushing element ', element)
opPush(glassStack, element)

# Print size
print('Current number of elements in stack is', size(glassStack))

# Pop one element

element = opPop(glassStack)
print('Popped element is', element)

# Push glass3
element = 'glass3'
print('Pushing element ', element)
opPush(glassStack, element)

# Show top element

print('top element is', top(glassStack))

# Display all elements

display(glassStack)

# Pop all elements

while True:
 item = opPop(glassStack)
if item == None:
print('Stack is empty now')
break
else:
print('Popped element is', item)

Expected Output:
Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
underflow
Stack is empty now

5.3 Function Summary Table

Function Parameters Returns Behavior

isEmpty(stack) stack (list) True / False True if len(stack)==0

opPush(stack, elem) stack, element None Appends element to end

opPop(stack) stack (list) Element or None Removes & returns last;

None if empty

top(stack) stack (list) Element or None Returns last WITHOUT

removing; None if empty

size(stack) stack (list) Integer Returns len(stack)

display(stack) stack (list) None (prints) Prints from TOP (last) to

BOTTOM (first)

6. ILLUSTRATIVE EXAMPLES
Example 1 (Beginner): Tracing PUSH/POP Operations
Initial: glassStack = []
Step-by-step trace from Figure 3.2:
Push 1 → Stack: [1] TOP = 1
Push 2 → Stack: [1, 2] TOP = 2
Pop → removes 2 → Stack: [1] TOP = 1
 Push 3 → Stack: [1, 3] TOP = 3
Push 4 → Stack: [1, 3, 4] TOP = 4
Pop → removes 4 → Stack: [1, 3] TOP = 3
Pop → removes 3 → Stack: [1] TOP = 1
Pop → removes 1 → Stack: [] Stack EMPTY

Example 2 (Intermediate): NCERT Exercise Q2a — Trace Code

result = 0
numberList = [10, 20, 30]
[Link](40) # Stack: [10, 20, 30, 40]
result = result + [Link]() # pops 40; result = 0+40 = 40
result = result + [Link]() # pops 30; result = 40+30 = 70
print('Result=', result) # Output: Result= 70

Example 3 (Intermediate): NCERT Exercise Q2b — String Reversal via Stack

answer = []
[Link]('T') # Stack: ['T']
[Link]('A') # Stack: ['T', 'A']
[Link]('M') # Stack: ['T', 'A', 'M']
ch = [Link]() # ch = 'M'
output = '' + 'M' = 'M'
ch = [Link]() # ch = 'A'
output = 'M' + 'A' = 'MA'
ch = [Link]() # ch = 'T'
output = 'MA' + 'T' = 'MAT'
print('Result=', output) # Output: Result= MAT
# Original was TAM (pushed in order), reversed is MAT

Example 4 (Intermediate): Infix to Postfix — (x+y)/(z*8)

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

Step Symbol Action Stack postExp

(bottom→top)

1 ( PUSH '(' (

2 x Append operand ( x

3 + Push operator ( + x
(stack top is '(' —
don't pop)

4 y Append operand ( + xy

5 ) POP until '(': pop + xy+

→ append; discard
'('

6 / Stack empty → / xy+

 PUSH /

7 ( PUSH '(' / ( xy+

8 z Append operand / ( xy+z

9 * Stack top is '(' — / ( * xy+z

PUSH *

10 8 Append operand / ( * xy+z8

11 ) POP until '(': pop * / xy+z8*

→ append; discard
'('

12 EOI POP all: pop / → xy+z8*/

append

RESULT: Postfix = xy+z8*/

Example 5 (Advanced): Infix to Postfix — A + B - C * D

Step Symbol Action Stack postExp

1 A Append operand A

2 + Stack empty → + A
PUSH +

3 B Append operand + AB

4 - Prec(-)==Prec(+): - AB+
POP + → append;
PUSH -

5 C Append operand - AB+C

6 * Prec(*)>Prec(-): - * AB+C
PUSH *

7 D Append operand - * AB+CD

8 EOI POP all: * → AB+CD*-

append, - →
append

RESULT: Postfix = AB+CD*-

Example 6 (Advanced): Postfix Evaluation — 7 8 2 * 4 / +

Postfix: 7 8 2 * 4 / + Expected result: 7 + (8*2)/4 = 7 + 16/4 = 7 + 4 = 11

Step Symbol Action Stack (bottom→top)

1 7 PUSH 7 7

2 8 PUSH 8 7 8

3 2 PUSH 2 7 8 2
 4 * POP 2, POP 8 → 8*2=16 7 16
→ PUSH 16

5 4 PUSH 4 7 16 4

6 / POP 4, POP 16 → 16/4=4 7 4

→ PUSH 4

7 + POP 4, POP 7 → 7+4=11 11

→ PUSH 11

8 EOI Stack has 1 element → EMPTY

POP 11 = RESULT

RESULT = 11

Example 7 (Advanced): Evaluate AB+C* where A=3, B=5, C=1

Postfix: AB+C* with A=3, B=5, C=1
Step Symbol Action Stack

1 A=3 PUSH 3 3

2 B=5 PUSH 5 3 5

3 + POP 5, POP 3 → 3+5=8 8

→ PUSH 8

4 C=1 PUSH 1 8 1

5 * POP 1, POP 8 → 8*1=8 8

→ PUSH 8

6 EOI Stack has 1 element → EMPTY

POP = RESULT

RESULT = 8

Example 8 (Advanced): Evaluate AB*C/D* where A=3, B=5, C=1, D=4

Postfix: AB*C/D* with A=3, B=5, C=1, D=4
Step Symbol Action Stack

1 A=3 PUSH 3 3

2 B=5 PUSH 5 3 5

3 * POP 5, POP 3 → 3*5=15 15

→ PUSH 15

4 C=1 PUSH 1 15 1

5 / POP 1, POP 15 → 15
15/1=15 → PUSH 15

6 D=4 PUSH 4 15 4

7 * POP 4, POP 15 → 60
15*4=60 → PUSH 60
 8 EOI POP → RESULT EMPTY

RESULT = 60
7. EDGE CASES & EXCEPTIONS
7.1 Overflow vs Underflow
Condition When Which Operation Python List-based Stack

Overflow Stack is FULL; trying to PUSH NEVER occurs (list has

PUSH no fixed size limit)

Underflow Stack is EMPTY; trying to POP OCCURS if isEmpty() not

POP checked; returns None in
our implementation

7.2 top() vs opPop() — Critical Difference

Feature top() opPop()

What it does READS the topmost element REMOVES and returns the topmost
element

Stack size change NO change Decreases by 1

Exam trap Does NOT pop DOES pop

7.3 display() Range — Common Mistake

The display() function uses: range(x-1, -1, -1) — starts at last index, stops BEFORE -1 (i.e., includes index 0),
step -1.
This prints elements from TOP (rightmost) to BOTTOM (leftmost) — correctly showing stack from top to
bottom.
# If stack = ['glass1', 'glass3']
# x = 2, range(1, -1, -1) → indices 1, 0
# prints: glass3 (index 1 = top), glass1 (index 0 = bottom)

7.4 Operand Order in Postfix Evaluation

TRAP: When applying a binary operator during postfix evaluation, the FIRST popped element is the RIGHT
operand, the SECOND popped is the LEFT operand.
# For expression 8 3 -:
# PUSH 8 → Stack: [8]
# PUSH 3 → Stack: [8, 3]
# Operator '-': POP 3 (operand2), POP 8 (operand1)
# Apply: 8 - 3 = 5 (NOT 3 - 8 = -5)

7.5 Parentheses in Infix to Postfix: NEVER go to postExp

Both '(' and ')' are completely DISCARDED during conversion. Neither appears in the final postfix expression.
7.6 When to POP vs PUSH operator during conversion
When current operator has LOWER or EQUAL precedence to the top of stack → POP stack first
When current operator has HIGHER precedence than top of stack → PUSH directly
EXCEPTION: Left parenthesis '(' on stack — NEVER pop it for an operator (only pop for ')')

7.7 Final Pop at End of Infix Expression

After all characters are processed, ALL remaining operators on the stack must be POPPED and appended to
postExp. If any parentheses remain on the stack, the expression was invalid.

8. VISUALIZATION SUPPORT
8.1 How to Draw a Stack Diagram in Exams
Draw a vertical rectangle divided into boxes (cells). Label TOP with an arrow pointing to the topmost element.
___________
TOP → | element3 | ← most recently pushed
|__________|
| element2 |
|__________|
| element1 | ← first pushed (bottom)
|__________|

8.2 Infix to Postfix Step-by-Step Drawing Format

In exams, draw two columns: STACK and POSTFIX STRING. Process each character of infix from left to
right:
Character | Action | Stack State | postExp
----------+-----------------+-------------+--------
( | PUSH ( | ( |
A | Append operand | ( | A
+ | PUSH operator | ( + | A
B | Append operand | ( + | AB
) | POP until ( | | AB+
etc.

8.3 Postfix Evaluation Drawing Format

Draw a vertical stack box. For each character:
• Operand: draw arrow pushing onto stack
• Operator: draw arrows popping two elements, show calculation, draw arrow pushing result
8.4 Three Notations Comparison — Visual Summary
Notation Operator Position Example: A+B*C Parentheses Evaluation
Needed? Direction

Infix BETWEEN A+B*C Sometimes (for Left to Right with

operands precedence) precedence rules

Prefix (Polish) BEFORE operands +A*BC NEVER Right to Left scan

Postfix (Reverse AFTER operands ABC*+ NEVER Left to Right scan

Polish)

9. MEMORY OPTIMIZATION
9.1 LIFO Mnemonic
LIFO = Last In, First Out

Memory hook: Think of a STACK of exam papers. Last paper placed ON TOP is the FIRST one
graded (removed).
Real-life: Browser BACK button, Undo/Redo, stack of plates.

9.2 Infix-Prefix-Postfix Pattern Recognition

Notation Memory Hook Operator Location

Infix 'In' = operator is IN between a + b (operator between)

Prefix 'Pre' = operator PRECEDES + a b (operator first)

operands

Postfix 'Post' = operator AFTER operands a b + (operator last)

9.3 Conversion Rules Quick Card

Infix to Postfix — 4 Rules

• Rule 1: OPERAND → directly to postExp (never to stack)

• Rule 2: '(' → PUSH to stack
• Rule 3: ')' → POP and append until '(' found; discard both brackets
• Rule 4: OPERATOR → POP operators of >= precedence from stack to postExp first, then
PUSH this operator
• Rule 5 (end): POP ALL remaining stack items to postExp
9.4 Evaluation Rules Quick Card
Postfix Evaluation — 3 Rules

• Rule 1: OPERAND → PUSH to stack

• Rule 2: OPERATOR → POP two: right=first popped, left=second popped; compute; PUSH
result
• Rule 3: End of expression → ONE element on stack = RESULT

9.5 Python Stack Method Quick Map

Stack Operation Python List Method Works on

PUSH (insert) [Link](element) End of list (= TOP)

POP (delete+return) [Link]() End of list (= TOP)

TOP (peek) list[len(list)-1] or list[-1] Last element (= TOP)

isEmpty len(list) == 0 Entire list

SIZE len(list) Entire list

10. BOARD EXAM FOCUS
10.1 Most Frequently Asked Questions
1. Define: data structure, stack, LIFO, PUSH, POP, overflow, underflow. (1-2 marks each)
2. Differentiate: PUSH and POP operations. (2 marks)
3. Write Python functions for: isEmpty(), opPush(), opPop(), top(), size(), display(). (2-3 marks each)
4. Convert infix to postfix with step-by-step stack/string trace. (5 marks)
5. Evaluate a given postfix expression step-by-step. (5 marks)
6. State TRUE or FALSE: (a) Stack is linear data structure. (b) Stack follows LIFO. (c) PUSH causes
underflow. (d) In postfix, operators are after operands. (1 mark each)
7. Explain with real-life examples: applications of stack. (3 marks)
8. Write a Python program to reverse a string using stack. (5 marks)
9. Trace the output of given stack code (NCERT Exercise Q2). (2-3 marks)

10.2 NCERT Exercise Answers

Q1. TRUE or FALSE:
• (a) Stack is a linear data structure → TRUE
• (b) Stack does not follow LIFO rule → FALSE (Stack DOES follow LIFO)
• (c) PUSH operation may result into underflow condition → FALSE (PUSH causes OVERFLOW, not
underflow; POP causes underflow)
• (d) In POSTFIX notation for expression, operators are placed after operands → TRUE

Q3. Reverse a String Using Stack:

def reverseString(s):
stack = list()
for ch in s:
[Link](ch) # PUSH each character
result = ''
while len(stack) > 0:
result += [Link]() # POP each character (LIFO reverses order)
return result

s = input('Enter string: ')

print('Reversed:', reverseString(s))

Q6a. Infix A+B-C*D to Postfix:

Answer: AB+CD*- (shown in Example 5 above)

Q6b. Infix A*((C+D)/E) to Postfix:

Step Symbol Action Stack postExp
 1 A Append A

2 * PUSH * * A

3 ( PUSH ( * ( A

4 ( PUSH ( * ( ( A

5 C Append * ( ( AC

6 + PUSH + * ( ( + AC

7 D Append * ( ( + ACD

8 ) POP until (: pop +; * ( ACD+

discard (

9 / PUSH / (top is ( → * ( / ACD+

don't pop)

10 E Append * ( / ACD+E

11 ) POP until (: pop /; * ACD+E/

discard (

12 EOI POP * ACD+E/*

RESULT: Postfix = ACD+E/*

11. COMPETITIVE EDGE (KCET LEVEL)
11.1 Advanced Insights
• Stack ADT (Abstract Data Type): Stack can be implemented using arrays (fixed size → overflow
possible) or linked lists (dynamic → no overflow). Python's list-based approach is a dynamic array.
• Time Complexity: PUSH = O(1), POP = O(1), TOP = O(1), isEmpty = O(1) — all stack operations are
constant time, making it extremely efficient.
• Space Complexity: O(n) where n = number of elements currently in the stack.
• Associativity matters: For equal precedence, LEFT-ASSOCIATIVE operators (+ - * /) are processed
left to right. So when current operator equals top precedence, we POP first (same precedence
triggers pop).
• Right-associative operators (like ^ exponentiation): when current operator equals top precedence, we
do NOT pop — we push directly.
• Infix expression validity: A valid postfix result should leave EXACTLY one element on the stack. If 0
or 2+, the input was invalid.

11.2 Common MCQ Traps

10. Trap: 'PUSH causes underflow' → WRONG. PUSH → overflow; POP → underflow.
11. Trap: 'Postfix and prefix need parentheses' → WRONG. Only INFIX needs parentheses.
12. Trap: 'Top element is the first element pushed' → WRONG. TOP = most recently pushed (LIFO).
13. Trap: 'display() prints from bottom to top' → WRONG. display() prints from TOP to BOTTOM (index
last to 0).
14. Trap: 'When evaluating postfix, first popped = left operand' → WRONG. First popped = RIGHT
operand.
15. Trap: 'In Python, stack overflow can occur for list-based stack' → WRONG. List has no size limit in
Python.
16. Trap: 'Parentheses are added to postfix expression' → WRONG. Parentheses are DISCARDED in
conversion.

A. KCET-STYLE MCQ QUESTIONS

Q1. A stack follows which principle?
Option Answer

(a) FIFO

(b) LIFO ✓ CORRECT

(c) Random access

(d) FILO

Explanation: LIFO = Last-In-First-Out. The most recently inserted element is removed first. FILO is the same
concept with different words but the standard term is LIFO.
Q2. Which Python method is used to implement PUSH in a list-based stack?
Option Answer

(a) insert()

(b) add()

(c) append() ✓ CORRECT

(d) push()

Explanation: Python's [Link](element) adds element at the END of the list, which is used as TOP in stack
implementation.

Q3. Trying to POP from an empty stack results in:

Option Answer

(a) Overflow

(b) Underflow ✓ CORRECT

(c) IndexError

(d) Nothing happens

Explanation: Underflow occurs when POP is attempted on an empty stack. Our opPop() function handles it by
printing 'underflow' and returning None.

Q4. What is the postfix notation for the infix expression A + B * C?

Option Answer

(a) AB+C*

(b) ABC*+ ✓ CORRECT

(c) ABC+*

(d) A+BC*

Explanation: * has higher precedence than +. So B*C is grouped first: A + (B*C). Postfix: A B C * + = ABC*+

Q5. In a postfix expression evaluation using stack, what is pushed onto the stack?
Option Answer

(a) Operators only

(b) Operands only ✓ CORRECT

(c) Both operands and operators

(d) Parentheses

Explanation: In postfix EVALUATION, only OPERANDS are pushed. When operator is found, POP two
operands, compute, push result.
Q6. In infix to postfix CONVERSION using stack, what is pushed onto the stack?
Option Answer

(a) Operands only

(b) Operators (and parentheses) only ✓ CORRECT

(c) Both

(d) Nothing

Explanation: In infix to postfix CONVERSION, only OPERATORS and PARENTHESES are pushed onto the
stack. Operands go directly to postExp.

Q7. What is the output of: stack = []; [Link](5); [Link](10); print([Link]())?
Option Answer

(a) 5

(b) 10 ✓ CORRECT

(c) [5, 10]

(d) Error

Explanation: append(5) → [5], append(10) → [5,10]. pop() removes from END (TOP) → removes 10.

Q8. Evaluate postfix expression: 5 3 2 * +

Option Answer

(a) 16

(b) 11 ✓ CORRECT

(c) 25

(d) 10

Explanation: PUSH 5, PUSH 3, PUSH 2. Operator *: POP 2, POP 3 → 3*2=6 → PUSH 6. Stack: [5,6].
Operator +: POP 6, POP 5 → 5+6=11 → PUSH 11. Result = 11.

Q9. Which of these is the PREFIX notation for (A+B)*C?

Option Answer

(a) AB+C*

(b) *+ABC ✓ CORRECT

(c) ABC+*

(d) *C+AB
Explanation: Prefix = operator BEFORE operands. (A+B)*C: the * operates on (A+B) and C. In prefix: * (+AB)
C → *+ABC

Q10. In Python's list-based stack implementation, which condition correctly represents

overflow?
Option Answer

(a) len(stack) == 0

(b) len(stack) > MAX_SIZE

(c) Overflow never occurs ✓ CORRECT

(d) [Link]() fails

Explanation: Python list has no fixed size limit — it grows dynamically. Therefore, using a Python list-based
stack, OVERFLOW will NEVER occur (only underflow is possible).

C. FORMULA/SYNTAX BOOSTER

Stack Quick Reference

stack = list() → empty stack

[Link](x) → PUSH x
[Link]() → POP (removes + returns TOP)
stack[-1] or stack[len(stack)-1] → PEEK (TOP without removing)
len(stack) == 0 → isEmpty check
len(stack) → size of stack
for i in range(len(s)-1,-1,-1): print(s[i]) → display TOP to BOTTOM

Notation Table

INFIX: operator BETWEEN operands: a + b

PREFIX: operator BEFORE operands: + a b
POSTFIX: operator AFTER operands: a b +
Infix to Postfix: PUSH operators; OPERANDS go straight to postExp
Postfix Eval: PUSH operands; OPERATORS trigger pop-compute-push
12. RAPID REVISION SHEET

Quick Revision — Stack (Chapter 3)

BASICS:
• Data structure = mechanism to store, organise, access data + operations on data
• Stack = linear data structure; insertion + deletion from ONE END (TOP) only
• LIFO: Last Inserted = First Removed
• Real-life: stack of plates, browser back button, undo/redo, function calls

OPERATIONS:
• PUSH = insertion at TOP → append() in Python
• POP = deletion from TOP → pop() in Python
• OVERFLOW = PUSH on FULL stack (never in Python list)
• UNDERFLOW = POP from EMPTY stack (check isEmpty() first!)
• TOP = glassStack[len-1] or glassStack[-1]
• No explicit TOP pointer needed in Python list implementation

PYTHON IMPLEMENTATION:
• isEmpty(): len()==0 → True; else False
• opPush(stack, elem): [Link](elem)
• opPop(stack): if isEmpty → None; else [Link]()
• top(stack): if isEmpty → None; else stack[len-1]
• size(stack): return len(stack)
• display(stack): for i in range(len-1, -1, -1): print(stack[i])

NOTATIONS:
• Infix: a+b (operator BETWEEN) — humans write this
• Prefix: +ab (operator BEFORE) — Polish notation, Jan Lukasiewicz 1920s
• Postfix: ab+ (operator AFTER) — Reverse Polish, used by compilers
• Postfix/Prefix: NO parentheses needed; single L-to-R scan sufficient

INFIX TO POSTFIX CONVERSION:

• Operand → directly to postExp
• '(' → PUSH to stack
• ')' → POP until '(' found; DISCARD both parentheses
• Operator → POP higher/equal precedence operators first; then PUSH
• End of input → POP ALL remaining operators to postExp
• Precedence: ^(3) > * /(2) > + -(1)

POSTFIX EVALUATION:
 • Operand → PUSH to stack
• Operator → POP right operand, POP left operand; compute; PUSH result
• End → single element on stack = RESULT; else invalid expression

KEY TRAPS:
• PUSH → overflow; POP → underflow (NOT the other way!)
• First popped in evaluation = RIGHT operand
• Parentheses NEVER appear in postfix expression
• Python list stack → OVERFLOW never occurs (dynamic size)
• top() = peek (no removal); opPop() = removes element