2nd PU Computer Science | Chapter 3: Stack

CHAPTER 3

STACK
Topics in this Chapter
• 3.1 Introduction to Data Structures
• 3.2 What is a Stack? (LIFO principle)
• 3.3 Operations on Stack — PUSH & POP
• 3.4 Implementation of Stack in Python (Complete Program)
• 3.5 Notations for Arithmetic Expressions (Infix / Prefix / Postfix)
• 3.6 Conversion from Infix to Postfix Notation
• 3.7 Evaluation of Postfix Expression

INTRODUCTION TO DATA STRUCTURES

• Data Structures defines the mechanism to store, organize, and access data efficiently.
• Examples: String, List, Set, Tuple, Array, Linked List, Stack, Queue, Trees, Graphs, etc.
• Stack and Queue are not built-in Python structures but can be implemented using list

STACK
Definition:
A stack is a linear data structures, where elements are added and removed from the same end called the TOP
of the stack.
 LIFO Principle: Last In – First Out. The element inserted last is the first one to be removed
 Real-life analogy: A pile of plates — you always add or remove from the top.

Applications of Stack
Real-life uses:
• Pile of clothes in an almirah – Clothes are added or removed from the top of the pile, following the
LIFO order.
• Multiple chairs in a vertical pile – Chairs are stacked one on top of the other, and removed in reverse
order.
• Bangles worn on the wrist – The last bangle worn is the first to be removed.
• Boxes of eatables in pantry – Boxes are added and removed from the top for convenience.

Programming uses:
• Reversing a string: Characters are pushed onto the stack and popped back in reverse order.
• Undo / Redo: Text/image editors store changes in a stack — clicking Undo pops the last change.

Karnataka State Board | Page 1

 2nd PU Computer Science | Chapter 3: Stack

• Browser Back button: History of visited pages is maintained as a stack — BACK button pops the last
page.
• Parenthesis matching: Compiler uses a stack to check every opening bracket has a matching closing
bracket.
• Function calls: The OS uses a call stack to manage function execution order.

OPERATIONS ON STACK — PUSH & POP

• PUSH: Add an element to the TOP of the stack.
• POP: Remove the topmost element.
• Overflow: Trying to PUSH to a full stack (not typically an issue in Python).
• Underflow: Trying to POP from an empty stack.

IMPLEMENTATION OF STACK IN PYTHON

Python uses the built-in list data type to implement a stack.
• append( ) → used for PUSH (adds at the end)
• pop( ) → used for POP (removes from the end)

Note: Since Python lists have no fixed size limit, the stack will never have an OVERFLOW unless
memory is exhausted.

# Create an empty stack

stack = list()

Function 1 — isEmpty( )
It used to checks whether the stack is empty. Returns True if empty, otherwise False.

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

Function 2 — opPush( )
It is used inserts (pushes) a new element at the TOP of the stack using append( ) method.

def opPush(stack, element):

[Link](element)

Karnataka State Board | Page 2

 2nd PU Computer Science | Chapter 3: Stack

Function 3 — size( )
It is used returns the number of elements currently in the stack.

def size(stack):
return len(stack)

Function 4 — top( )
It is used to returns the topmost element without removing it. If stack is empty, then returns None.

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

Function 5 — opPop( )
It is used to removes and returns the topmost element. If stack is empty, then it Print 'underflow'.

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

Function 6 — display( )
It is used to displays all elements of the stack from top to bottom.

def display(stack):
x = len(stack)
print('Current elements in the stack are:')
for i in range(x - 1, -1, -1):
print(stack[i])

Karnataka State Board | Page 3

 2nd PU Computer Science | Chapter 3: Stack

NOTATIONS FOR ARITHMETIC EXPRESSIONS

Arithmetic expressions can be written in three different notations:
1. Infix
2. Prefix (Polish)
3. Postfix (Reverse Polish)

1. Infix: Operator are placed in between operands

Example: X + Y
2. Prefix (Polish): Operator are placed before operands
Example: + X Y
3. Postfix (Reverse Polish): Operator are placed after operands
Example: X Y +

Example conversions:
1. x + y
Prefix Postfix
→ +xy → xy+

2. x + y - z
Prefix Postfix
→ +xy – z → xy+ – z
→ –+xyz → xy+z–

3. (x + y) / (z * 8)
Prefix Postfix
→ +xy / *z8 → xy+ / z8*
→ /+xy*z8 → xy+z8*/

4. 3 * (4 + 5)
Prefix Postfix
→ 3 * +45 → 3 * 45+
→ *3+45 → 345+*

Karnataka State Board | Page 4

 2nd PU Computer Science | Chapter 3: Stack

CONVERSION FROM INFIX TO POSTFIX NOTATION

Infix to Postfix

Rules:
 Operators go onto a stack.
 Operands go directly to the output string.
 Operators are popped and appended based on precedence rules.

Operator Precedence (High to Low):

Operator Precedence
^ (Exponentiation) Highest
*, / (Multiply, Divide) Medium
+, − (Add, Subtract) Lowest

Algorithm Steps:
1. Create empty string postfix expression and empty stack.
2. Input infix expression.
3. For each character in infix expression:
◦ If character is '(' → PUSH onto stack
◦ If character is ')' → POP and append to postfix expression until '(' is found; discard both parentheses
◦ If character is an OPERATOR → If its precedence ≤ top of stack's operator, POP and append till
condition fails, then PUSH current operator; else directly PUSH
◦ If character is an OPERAND → directly append to postfix expression
4. After all characters are processed → POP remaining operators from stack and append to postfix
expression.
5. Output postfix expression

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

Symbol Stack Postfix Expression
( (
x ( x
+ (+ x
y (+ xy
) xy+
/ / xy+

Karnataka State Board | Page 5

 2nd PU Computer Science | Chapter 3: Stack

( /( xy+
z /( xy+z
* /(* xy+z
8 /(* xy+z8
) / xy+z8*
END xy+z8*/

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

EVALUATION OF POSTFIX EXPRESSION

Algorithm — Evaluate Postfix

Algorithm Steps:
1. Input postfix expression.
2. For each character in postfix expression:
◦ If character is an OPERAND → PUSH onto stack
◦ If character is an OPERATOR → POP two elements from stack, apply operator, PUSH result back
3. After processing all characters:
◦ If stack has exactly ONE element → POP and output as result
◦ Else → output 'Invalid Postfix Expression'

Example — Evaluate Postfix Expression: 7 8 2 * 4 / +

Symbol Action Stack
7 Operand → PUSH 7
8 Operand → PUSH 7, 8
2 Operand → PUSH 7, 8, 2
* POP 2 & 8 → 8×2=16 → PUSH 16 7, 16
4 Operand → PUSH 7, 16, 4
/ POP 4 & 16 → 16÷4=4 → PUSH 4 7, 4
+ POP 4 & 7 → 7+4=11 → PUSH 11 11
END Pop 11 element → then RESULT = 11 EMPTY

Karnataka State Board | Page 6