CHAPTER 3 : STACK

Complete Premium Revision Notes

INDEX
1 Introduction to Data Structures 3

2 Stack — Meaning & Concept 3

• Applications of Stack 4

3 Operations on Stack (PUSH & POP) 4

4 Implementation of Stack in Python 6

• Complete Worked Example — Program & Output 8

• Function Reference Table 9

5 Notations for Arithmetic Expressions 10

6 Conversion from Infix to Postfix Notation 10

• Worked Example 3.1 11

7 Evaluation of Postfix Expression

• Worked Example 3.2

T H 12

12

M A
I
END-OF-CHAPTER REVISION ZONE

R1

R2
Chapter Summary

Key Points (Must-Know) — Top 20

CH 13

A
14
ce
R3

R4
Definitions at One Place

Syntax Collection
A N uter
Sc
ie n 15

16

R5 Algorithms Collection

E N r in
C om p 17

R6

R7
V E
Examples Collection

tur
Infix ↔ Postfix Conversion Collection
Le
c
e
17

18

R8
A
Postfix Expression Evaluation Collection

R
19

R9

R10
P
Important Tables

Formula / Rules
19

20

R11 Frequently Confused Concepts 20

R12 One-Page Quick Revision 21

R13 Last 5 Minutes Before Exam 21

© PRAVEEN ANACHIMATH Page 1 of 19

 1 Introduction to Data Structures

DEFINITION — DATA STRUCTURE

A data structure defines a mechanism to store, organise and access data, along with the operations
(processing) that can be efficiently performed on that data.

In Class XI, we studied data types like String, List, Set, Tuple — these are sequence data
types used to represent a collection of elements (same or different types).

➔ Multiple data elements are grouped in a particular way for faster accessibility and efficient
storage of data. This grouping is called a data structure.
➔ String — a data structure containing a sequence of elements where each element is a character.
➔ List — a sequence data structure in which each element may be of a different type.
➔ Different operations (reversal, slicing, counting elements, etc.) can be applied on list and string.

IMPORTANT NOTE

T H
A data structure in which elements are organised in a sequence is called a linear data structure.

A
Other important data structures in Computer Science include: Array, Linked List, Binary Trees,

M
Heaps, Graph, Sparse Matrix, etc.

H I
Stack and Queue are two popular linear data structures used in programming. Although not directly

A C
available as a built-in Python type, it is important to learn these concepts as they are extensively used in
many programming languages. In this chapter we study Stack, its implementation in Python, and its
ce
applications.

A N ute
rS
cie n

2 Stack — Meaning & Concept

E N r in
C om p

DEFINITION — STACK
V E ec
ture

A L order in which addition of a new element or removal of an

An arrangement of elements in linear

R
existing element takes place from the same end (called TOP), is called a Stack. A stack follows the

P
Last-In-First-Out (LIFO) principle.

✔ Real-life examples: pile of books in a library, stack of plates at home.

✔ To add a book/plate, we always place it at the TOP. To remove one, we always remove it from the
TOP only — because it is inconvenient to add/remove from the middle or bottom of a large pile.
✔ LIFO Principle: The element inserted last (most recent) is the first one to be taken out.

© PRAVEEN ANACHIMATH Page 2 of 19

 Fig 3.1 — Structure of a Stack showing TOP and BOTTOM (LIFO order)

3.2.1 Applications of Stack

T H
Real-life Applications
M
Applications in Programming A
★ Pile of clothes in an almirah
H I
➤ Reversing a string: traversed last-to-first using a
★ Multiple chairs in a vertical pile
★ Bangles worn on a wrist
★ Pile of boxes of eatables in a pantry or kitchen
stack.

A C
➤ Undo/Redo: most recent change affected first.
e
➤ Browser history (Back button): pages maintained as
nc
shelf

A N a stack.

ter
using a stack.
u
Sc ie
➤ Matching parentheses: compiler checks nesting

3 Operations on Stack
E N r in
C om p

V E e ctu
Since a stack implements a LIFO arrangement,
re
elements are added and deleted from one end only,

A
called the TOP of the stack. The twoLfundamental operations are PUSH and POP.

R
P
PUSH OPERATION
PUSH adds a new element at the TOP of the stack. It is an insertion operation. We can add
elements until the stack is full. Trying to add to a full stack causes an exception called OVERFLOW.

POP OPERATION
POP removes the topmost element of the stack. It is a deletion operation. We can delete elements
until the stack is empty. Trying to delete from an empty stack causes an exception called
UNDERFLOW.

© PRAVEEN ANACHIMATH Page 3 of 19

 T H
M A
H I
A C ce

A N uter
S
Fig 3.3 — Redrawn flowchart logic for PUSH (checks Overflow)
n
cieand POP (checks Underflow)

WARNING — COMMON CONFUSION

E N C o mp
OVERFLOW occurs on PUSH when stack isinFULL. UNDERFLOW occurs on POP when stack is

V E
EMPTY. Do not mix these up in exams! ure
e ct
r

A L
4 Implementation of Stack in Python
R
P
KEY IDEA
A stack is a linear, ordered collection of elements. The simplest way to implement a stack in Python is
using the list data type. We fix either end of the list as TOP. Python's built-in list methods append()
and pop() are used — inserting/removing at the rightmost end — so no explicit TOP variable/pointer
is needed.

Program goal: create a STACK (stack of glasses) that can:

✔ Insert / delete elements (glasses)
✔ Check if the STACK is empty
✔ Find the number of elements in the STACK
✔ Read the value of the topmost element in the STACK

© PRAVEEN ANACHIMATH Page 4 of 19

 Step 1 — Create an Empty Stack

glassStack = list() # create empty stack (empty list)

Step 2 — isEmpty() Function

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

➤ Checks whether glassStack is empty. Returns True if empty, else False. Used to avoid underflow
before a POP. This same underflow check reappears below in the worked Example — Program &
Output and in the opPop() function.
Step 3 — opPush() Function

def opPush(glassStack, element):

T H
[Link](element)

M A
➔ Two parameters: name of stack + element to insert.

H I
➔ Uses built-in append() which always adds at the end of the list = TOP of stack.

memory runs out).

A C
➔ Since Python lists have no fixed size limit, this stack will practically never face overflow (unless
ce
Step 4 — size() Function
A N uter
Sc
ie n

def size(glassStack):
return len(glassStack)
E N r in
C o m p

V E re
ctu in the stack.
➤ Uses len() to return number of elements
Le

RA
Step 5 — top() Function

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

➤ Reads (does not remove) the most recent / topmost element of the stack. Compare this with opPop()
below, which does remove the element — see the clarification in R11 Frequently Confused Concepts.

© PRAVEEN ANACHIMATH Page 5 of 19

Step 6 — opPop() Function

def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return([Link]())

➤ Takes one parameter — name of the stack. Returns the value of the deleted element.
➤ First checks if empty (underflow); if not empty, removes topmost element using built-in pop() —
which removes from the end of the list.

Step 7 — display() Function

def display(glassStack):
x = len(glassStack)
print("Current elements in the stack are: ")

H
for i in range(x-1, -1, -1):

T
print(glassStack[i])

A
➤ Displays contents of the stack from TOP to BOTTOM (reverse order of the underlying list).

M
H I
A C nc
e

A N uter
Sc ie

E N r in
C om p

V E ec
ture

RA L

© PRAVEEN ANACHIMATH Page 6 of 19

COMPLETE PROGRAM — DRIVER CODE

glassStack = list() # create empty stack

element = 'glass1'
print("Pushing element ", element)
opPush(glassStack, element)

element = 'glass2'
print("Pushing element ", element)
opPush(glassStack, element)

print("Current number of elements in stack is", size(glassStack))

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

element = 'glass3'
print("Pushing element ", element)

H
opPush(glassStack, element)

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

display(glassStack)
A T
# delete all elements from stack
I M
while True:
item = opPop(glassStack)
if item == None:
CH
print("Stack is empty now")
break
N A c ie nc
e
else:
A
print("Popped element is", item)
uter
S

OUTPUT
E N r in
C om p

V E
Pushing element glass1
ec
tu re

A L
Pushing element glass2
Current number of elements in stack is 2

P R
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

Function Reference Table

Function Purpose Returns

© PRAVEEN ANACHIMATH Page 7 of 19

 isEmpty(stack) Check whether stack has zero elements True / False

opPush(stack, element) Insert element at TOP using append() Nothing (None)

size(stack) Count number of elements using len() Integer count

top(stack) Read topmost element without removing Value at TOP /

None

opPop(stack) Remove & return topmost element using pop() Deleted value /
None

display(stack) Print all elements from TOP to BOTTOM Nothing (None)

5 Notations for Arithmetic Expressions

➤ We normally write arithmetic expressions using operators between operands, e.g. x + y, 2 - 3 * y.
Parentheses () are used to order evaluation in complex expressions.

H
➤ These expressions follow Infix representation and are evaluated using the BODMAS rule.

T
A
➤ Polish mathematician Jan Lukasiewicz (1920s) introduced Polish Notation, where operators are
written before their operands — parentheses become unnecessary. Example: x+y → +xy. This is also

M
called Prefix notation.

H I
➤ By reversing the logic, operators are written after their operands: x+y → xy+. This is called
Reverse Polish Notation or Postfix notation.

A C nc
e
Type of Expression

Infix
Description

A N
Operators placed between operands
te
Example

S cie
r x*y+z | 3*(4+5) | (x+y)/(z*5)

pu
Prefix (Polish)

E N in
C om
Operators placed before operands +z*xy | *3+45 | /+xy*z5

Postfix (Reverse
Polish)
V E e ctu
r er
Operators placed after operands xy*z+ | 345+* | xy+z5*/

RA
WHY POSTFIX/PREFIX?
L

P
In infix expressions, humans use knowledge of operator precedence (BODMAS) to decide what to
evaluate first. But passing this “precedence knowledge” to a computer is complex. In prefix/postfix,
operators are already positioned according to evaluation order — so a single left-to-right traversal is
enough to evaluate the expression, with NO need for precedence rules or parentheses!

6 Conversion from Infix to Postfix Notation

A stack is used to keep track of operators encountered in the infix expression. A string variable stores
the equivalent postfix expression as it is built.

© PRAVEEN ANACHIMATH Page 8 of 19

ALGORITHM 3.1 — INFIX TO POSTFIX CONVERSION

ConvertInfixToPostfix(inExp)
Step 1: Create an empty string named postExp to store the converted postfix expressi
on.
Step 2: INPUT infix expression in a variable, say inExp
Step 3: For each character in inExp, REPEAT Step 4
Step 4: IF character is a left parenthesis THEN
PUSH on the Stack
ELSE IF character is a right parenthesis THEN
POP the elements from the Stack and append to string postExp
until the corresponding left parenthesis is popped
(discard both left and right parentheses)
ELSE IF character is an operator THEN
IF its precedence is lower than that of operator at the
top of Stack THEN
POP elements from the Stack till an operator with
precedence less than the current operator is
encountered, append each to postExp,

H
then PUSH the current operator on the Stack
ELSE

ELSE
PUSH operator on the Stack

A T
Append the character (operand) to postExp

I M
Step 5: Pop elements from the Stack and append to postExp until Stack is empty
Step 6: OUTPUT postExp

CH
A
KEY RULES TO REMEMBER
✔ Left parenthesis ( → always PUSH onto stack ce

A N
✔ Right parenthesis ) → POP & append until matching ( is found;
add them to postExp)
uter
S
n
cie DISCARD both parentheses (don't

E N
✔ Operand → directly append to postExp string om
C
p
in TOP; pop-and-append higher/equal precedence

V E
✔ Operator → compare precedence with stack
tur
operators first, then push current operator
c
e r
Lestack elements into postExp

RA
✔ At the end → pop ALL remaining

Worked Example 3.1 — Convert (x + y) / (z * 8) to Postfix

Symbol
P Action Stack
(bottom→top)
postExp (string)

( Left paren → PUSH on Stack ( (empty)

x Operand → Append directly to postExp ( x

+ Operator, Stack top is "(" → PUSH operator (+ x

y Operand → Append to postExp (+ xy

) Right paren → POP till "(" is popped, (empty) xy+

append popped ops; discard both parens

© PRAVEEN ANACHIMATH Page 9 of 19

 /(z*8) Repeat same logic → "/" pushed, "(" / xy+z8*
pushed, z appended, "*" pushed, 8
appended, ")" pops "*"

END Pop all remaining operators from Stack → (empty) xy+z8*/

append to postExp

Fig 3.4 — Step-by-step conversion of (x + y)/(z*8) to postfix using a stack

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

7 Evaluation of Postfix Expression

Stacks can be used to evaluate an expression written in postfix notation. For simplification, we assume
all operators are binary operators (take exactly 2 operands).

ALGORITHM 3.2 — EVALUATION OF POSTFIX EXPRESSION

T H
EvaluatePostfix(postExp)
Step 1: INPUT postfix expression in a variable, say postExp

M A
Step 2: For each character in postExp, REPEAT Step 3
Step 3: IF character is an operand THEN
PUSH character on the Stack
H I
ELSE

A C
POP two elements from the Stack, apply the operator on

nc
e
the Stack
Step 4: IF Stack has a single element THEN
A N
the popped elements, and PUSH the computed value onto

uter
Sc ie

N
POP the element and OUTPUT as the net result
m p
o
E
ELSE
C
r in
OUTPUT "Invalid Postfix expression"

V E
Le
c tur
e

A
IMPORTANT — ORDER OF OPERANDS IN POP

R
When popping two elements for a binary operator, the first popped value is the second operand (right
side) and the second popped value is the first operand (left side). For non-commutative operators like

P
- and /, the order matters! Example: popped values are 4 then 16 → operation is 16 / 4, NOT 4 / 16.

Worked Example 3.2 — Evaluate 7 8 2 * 4 / +

Symbol Read Action Stack After Action

7 Operand → PUSH 7

8 Operand → PUSH 7, 8

2 Operand → PUSH 7, 8, 2

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

© PRAVEEN ANACHIMATH Page 10 of 19

 4 Operand → PUSH 7, 16, 4

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

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

Fig 3.5 — Step-by-step evaluation of postfix expression 7 8 2 * 4 / + using a stack

FINAL RESULT
Only ONE element remains in the Stack at the end → POP it → Result = 11

EXAM TIP
If at the end of evaluation the stack contains more than one element (or is empty), the expression is
INVALID POSTFIX. Always verify only ONE value remains at the end!

8 Textbook Chapter Summary (As-Is)

ORIGINAL NCERT/KARNATAKA TEXTBOOK SUMMARY POINTS

T H
A
✔ Stack is a data structure in which insertion and deletion is done from one end only, usually referred to

M
as TOP.

H I
✔ Stack follows the LIFO principle — an element inserted last will be the first one to be taken out.

elements, respectively.
A C
✔ PUSH and POP are the two basic operations performed on a stack for insertion and deletion of

ce

A N r
n
✔ Trying to pop an element from an empty stack results in a specialecondition
S ci
✔ In Python, list is used for implementing a stack; its built-in functions
ute
called underflow.
append() and pop() are used

N
for insertion and deletion, respectively. Hence, no explicitpdeclaration of TOP is needed.
omof the three notations: Infix, Prefix and Postfix.

E E
✔ Any arithmetic expression can be represented inCany
✔ While programming, Infix notation is usedefor
r
r inwriting an expression in which binary operators are

A V
written between the operands.
L e ctu
✔ A single traversal from left to right of a Prefix/Postfix expression is sufficient to evaluate it, as

P R
operators are correctly placed as per their order of precedence.
✔ Stack is the commonly used data structure to convert an Infix expression into equivalent Prefix/Postfix
notation.
✔ While converting Infix to Prefix/Postfix notation, only operators are PUSHed onto the Stack.
✔ When evaluating a Postfix expression using a Stack, only operands are PUSHed onto it.

© PRAVEEN ANACHIMATH Page 11 of 19

 END-OF-CHAPTER REVISION ZONE — 11 POWER SECTIONS

R2 Key Points (Must-Know)

TOP 20 KEY POINTS
1. Stack = Linear data structure, insertion/deletion from ONE end only (TOP).
2. Stack follows LIFO — Last In First Out.
3. PUSH = insert operation; fails with OVERFLOW when stack is full.
4. POP = delete operation; fails with UNDERFLOW when stack is empty.
5. Python implements stack using list data type.
6. append() is used for PUSH (adds at end of list = TOP).
7. pop() (no argument) is used for POP (removes from end of list = TOP).
8. Python lists have no fixed size → stack (in Python) practically never overflows.
9. len() is used to find the size of the stack.
10. isEmpty() checks emptiness before POP to prevent underflow errors.
11. top() reads the topmost value WITHOUT removing it.
T H
12. 3 Notations: Infix (between), Prefix (before), Postfix (after) operands.

M A
I
13. Infix needs BODMAS + parentheses; Prefix/Postfix do NOT need parentheses.

H
14. Prefix/Postfix require only ONE left-to-right traversal to evaluate.

A C
15. Converting Infix→Postfix: Stack stores operators (and parentheses temporarily); string stores
operands/result.

ce (, discard both.
16. Left parenthesis ( → always PUSH; Right parenthesis ) → POP till matching

N te
18. Order matters in POP for evaluation: 1st popped = right operand,
i
rS
en
17. Evaluating Postfix: Stack stores operands; on operator, POP 2, ccompute,

A
PUSH result.
2nd popped = left operand.
pu

E N m remain in stack = the answer.

19. At the end of postfix evaluation, exactly ONE value should
Co
in (Prefix); reversing gives Postfix (Reverse Polish).
20. Jan Lukasiewicz (1920s) introduced Polish Notation

V E
R3 Definitions at One Placeect
ur
e r

Term
RA L
Definition

P
Data Structure A mechanism to store, organise and access data along with operations that can
be efficiently performed on it.

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

Stack An arrangement of elements in linear order where addition/removal happens

from the same end (TOP), following LIFO.

LIFO Last-In-First-Out — the element inserted last is removed first.

TOP The end of the stack from which elements are PUSHed (inserted) and POPped
(deleted).

© PRAVEEN ANACHIMATH Page 12 of 19

 PUSH Operation to insert a new element at the TOP of the stack.

POP Operation to remove the topmost element of the stack.

Overflow Exception when trying to PUSH an element into a FULL stack.

Underflow Exception when trying to POP an element from an EMPTY stack.

Infix Notation Operators are placed IN BETWEEN the operands. E.g. x + y.

Prefix (Polish) Notation Operators are placed BEFORE the corresponding operands. E.g. +xy.

Postfix (Reverse Polish) Operators are placed AFTER the corresponding operands. E.g. xy+.
Notation

R4 Syntax Collection

T H
M A
H I
A C nc
e

A N uter
Sc ie

E N r in
C om p

V E ec
tu re

RA L

© PRAVEEN ANACHIMATH Page 13 of 19

 # Create empty stack
glassStack = list()

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

# PUSH - insert at TOP

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

# SIZE - count elements

def size(glassStack):
return len(glassStack)

# TOP - read without removing

H
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty'); return None
else:
A T
return glassStack[len(glassStack)-1]

I M
# POP - remove & return from TOP
def opPop(glassStack):
if isEmpty(glassStack):
CH
print('underflow'); return None
else:
N A c ie nc
e
return([Link]())
A uter
S

def display(glassStack):
E N
# DISPLAY - show TOP to BOTTOM

r in
C om p

V E
x = len(glassStack)
for i in range(x-1, -1, -1):
print(glassStack[i]) ec
ture

RA
R5 Algorithms Collection
L

© PRAVEEN ANACHIMATH Page 14 of 19

 ALGORITHM 3.1 — INFIX TO POSTFIX CONVERSION (CONDENSED)

1. Create empty string postExp; INPUT infix expression inExp

2. For each character in inExp:
- "(" -> PUSH on Stack
- ")" -> POP & append to postExp until "(" popped; discard both parens
- Operator ->
if precedence LOWER than Stack TOP:
POP & append until higher-precedence operator found, then PUSH curren
t
else: PUSH current operator
- Operand -> Append directly to postExp
3. After loop: POP all remaining Stack elements & append to postExp
4. OUTPUT postExp

ALGORITHM 3.2 — POSTFIX EXPRESSION EVALUATION (CONDENSED)

1. INPUT postfix expression postExp

2. For each character in postExp:
- Operand -> PUSH on Stack
- Operator -> POP two elements, apply operator, PUSH result back
3. IF Stack has exactly ONE element:
T H
POP it -> OUTPUT as final result
ELSE:
M A
OUTPUT "Invalid Postfix Expression"

H I
R6 Examples Collection

A C nc
e
EXAMPLE B — INFIX TO POSTFIX
Infix: (x + y) / (z * 8) → Postfix: x y + z 8 * /
A N uter
Sc ie

EXAMPLE C — POSTFIX EVALUATION

E N r in
C om p

V E
Postfix: 7 8 2 * 4 / + → Result: 11
(Steps: 8*2=16 → 16/4=4 → 7+4=11)
ec
tu re

RA L
EXAMPLE D — TRUE/FALSE STYLE PRACTICE (FROM TEXTBOOK PATTERN)

P
Statement

Stack is a linear data structure

Answer

TRUE

Stack does not follow LIFO rule FALSE (it DOES follow LIFO)

PUSH operation may result into underflow condition FALSE (PUSH causes OVERFLOW,
not underflow)

In POSTFIX notation, operators are placed after operands TRUE

R7 Infix ↔ Postfix Conversion Collection

© PRAVEEN ANACHIMATH Page 15 of 19

Complete Conversion Reference — (X + Y) / (Z * 8)

Symbol Action Stack postExp

( PUSH ( —

x Append (operand) ( x

+ PUSH (top is "(") (+ x

y Append (operand) (+ xy

) POP till "(" popped; append "+" empty xy+

/ PUSH (stack empty) / xy+

( PUSH /( xy+

z Append (operand) /( xy+z

* PUSH (top is "(") /(* xy+z

8 Append (operand) /(* xy+z8

) POP till "(" popped; append "*" / xy+z8*

T H
END POP all remaining ("/") empty

M
xy+z8*/
A
Precedence Order for Conversion (Standard)
H I
Precedence Operators

A C nc
e
Highest

Next
^ (exponent)

*,/
A N uter
Sc ie

Lowest

E N
+,-
C om
p
in before pushing the current operator (left-to-right for
same precedence).
V E e ctu
er
Rule: pop operators of equal or higher precedence
r

RA L
R8 Postfix Expression Evaluation Collection

P
Additional Practice — A B + C * (A=3, B=5, C=1)

Symbol Action Stack

A (3) PUSH 3

B (5) PUSH 3, 5

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

C (1) PUSH 8, 1

* POP 1, POP 8 → 8*1=8 → PUSH 8 8

Result = 8

© PRAVEEN ANACHIMATH Page 16 of 19

 R9 Important Tables

Notation Description Example

Infix Operators between operands x*y+z

Prefix Operators before operands +z*xy

Postfix Operators after operands xy*z+

Stack Operation Python Equivalent Error Condition

PUSH [Link](x) Overflow (stack full)

POP [Link]() Underflow (stack empty)

PEEK/TOP list[len(list)-1] None if empty

T H
SIZE len(list)

M
—

A
ISEMPTY

R10 Formula / Rules

len(list) == 0

H I —

Stack Size = len(stack_list)

A C nc
e
TOP element = stack_list[len(stack_list)-1]
Underflow condition: len(stack_list) == 0
A N
Overflow condition (conceptual): len(stack_list) == MAX_SIZE
uter
Sc ie

RULE OF THUMB
E N r in
C om p

V E
✔ Postfix Evaluation: Operands go e c t
e
✔ Infix→Postfix: Operators go on Stack, operands
ur
go directly to output string.

L on Stack, operators trigger POP-POP-compute-PUSH.

RA
P
R11 Frequently Confused Concepts

Confusing Pair Clarification

Overflow vs Underflow Overflow = PUSH into FULL stack. Underflow = POP from EMPTY stack.

Stack vs Queue Stack = LIFO (one end). Queue = FIFO (two ends: front & rear) — covered
in Chapter 4.

append() vs insert(0,x) append() adds at END (stack PUSH). insert(0,x) adds at BEGINNING (not
used for stack).

pop() vs pop(0) pop() removes from END (stack POP). pop(0) removes from BEGINNING
(used in queue, not stack).

© PRAVEEN ANACHIMATH Page 17 of 19

 Prefix vs Postfix Prefix: operator BEFORE operands (+xy). Postfix: operator AFTER
operands (xy+). Remember "POST = after/last".

top() vs opPop() top() only READS the top value (no removal). opPop() REMOVES and
returns the top value.

Order of POP in evaluation First popped value = RIGHT operand; Second popped value = LEFT
operand. Critical for - and /.

Left vs Right parenthesis handling "(" is always PUSHed. ")" triggers POPping until matching "(" —
parentheses are NEVER added to postExp.

R12 One-Page Quick Revision

Stack Basics Notations

✔ Linear DS, LIFO principle ✔ Infix: a+b (needs BODMAS)
✔ TOP = only access point
✔ PUSH = insert; POP = delete
✔ Prefix: +ab (operator first)

T
✔ Postfix: ab+ (operator last)
H
✔ Overflow (full) / Underflow (empty) Conversion & Evaluation

M A
Python Implementation
✔ Stack = Python list
H I
✔ Infix→Postfix: Stack holds operators
✔ "(" push; ")" pop till "("
✔ append() → PUSH
✔ pop() → POP
C
✔ Postfix Eval: Stack holds operands

A
✔ Operator → pop
e 2, compute, push 1
nc
✔ len() → size
✔ No fixed limit → rarely overflows
A N t e rS
ie left in stack = answer
✔ Final: 1 value
c
pu
R13 Last 5 Minutes Before Exam
E N r in
C o m

Rapid Fire Facts

V E ec
ture

A
✔ Stack → LIFO → TOP only

R
✔ PUSH = insert = append()
L

P
✔ POP = delete = pop()
✔ Full stack + PUSH = OVERFLOW
✔ Empty stack + POP = UNDERFLOW
✔ Infix: a+b | Prefix: +ab | Postfix: ab+

© PRAVEEN ANACHIMATH Page 18 of 19

 Conversion Cheat
✔ Operand → straight to output
✔ "(" → push
✔ ")" → pop till "("
✔ Operator → pop higher/equal precedence first, then push
✔ End → pop everything left

Evaluation Cheat
✔ Operand → PUSH
✔ Operator → POP 2 → compute (2nd popped OP 1st popped) → PUSH result
✔ End: exactly 1 value left = answer; else “Invalid Postfix”

Memorize This Example

(x+y)/(z*8) → x y + z 8 * / | 7 8 2 * 4 / + → 11

T H
A
— End of Chapter 3: STACK — Premium Revision Notes —
© PRAVEEN ANACHIMATH | Lecturer in Computer Science

I M
CH
N A c ie nc
e

A uter
S

E N r in
C o m p

V E ec
ture

RA L

© PRAVEEN ANACHIMATH Page 19 of 19