II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

Chapter 3 Stack

Data structure: A data structure defines a mechanism to store, organise and access data along with operations (processing) that can be
efficiently performed on the data.
Example: string, list, array, linked list, binary trees, heaps, graphs, sparse matrix, stack, queue and so on.

Linear data structure: A data structure in which elements are organised in a sequence is called linear data structure.
Example: array, list, stack, queue

Stack
 It is a linear data structure where elements are added and removed from the same end.
 The end from which elements are added and removed form stack is called as top.
 Stack follows the Last-In-First-out (LIFO) principle.
 This means, the element which was inserted last (the most recent element) will be the first one to be removed from the stack.
 Stack is LIFO data structure because only one end is used for insertion and deletion of elements.

Applications of stack
a) Applications of stack in real-life are
 Pile of clothes in an almirah.
 Multiple chairs in a vertical pile.
 Bangles worn on wrist.
 Pile of boxes of eatables in pantry or on a kitchen shelf.

b) Application of stack in programming

 Reverse a string.
 Undo/redo options in text/image editor.
 To store links, webpages visited by user while browsing the web.
 Expression evaluation by compiler/ interpreter.
 Decimal to binary number conversion.

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 1

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

Operations on Stack
Two fundamental operations performed on the stack are
1) Push
2) Pop
Push operation
 PUSH adds a new element at the TOP of the stack.
 It is an insertion operation. We can add elements to a stack until it is full.
 A stack is full when no more elements can be added to it.
 Trying to add an element to a full stack results in an exception called ‘overflow’.

POP operation
 POP operation is used to remove the top most element of the stack, that is, the element at the TOP of the stack.
 It is a delete operation.
 We can delete elements from a stack until it is empty i.e. there is no element in it.
 Trying to delete an element from an empty stack results in an exception called ‘underflow’.

Example:

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 2

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

Implementation of Stack in Python

 The simple way to implement a stack in Python is using the data type list.
 Programmer can fix either of the sides of the list as TOP end to insert/remove elements.
 Built-in methods append () and pop () of the list data type are used for implementation of the stack.
 As these built-in methods insert/delete elements at the rightmost end of the list, hence explicit declaration of TOP is not needed.

Stack is implemented by considering the following

 Create a stack.
 Insert elements
 Delete elements.
 Checking if the STACK is empty or not.
 Finding the number of elements in the stack.
 Reading the value of the topmost element in the stack.
 Displaying all elements from stack.

Following functions are used to perform these operations:

1) Creating an empty stack named glassStack.
glassStack = list()

2) A function named isempty( ):

 This function returns True if the stack is empty, else returns False.
 Trying to remove an element from an empty stack would result in ‘underflow’.
def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False

3) A function named opPush ( ):

 This function inserts an element to the top of the stack.
 This function has two parameters - the name of the stack and the element that needs to be inserted.

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 3

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

 Built-in method append () is used to insert an element at the top end.

 As there is no limit on the size of list in Python, the implemented stack will never be full unless there is no more space available in
memory.
 Hence, programmer will never face ‘overflow’ (no space for new element) condition for stack.
def opPush(glassStack, element):
[Link](element)

4) A function named size ( ):

 This function reads the number of elements in the stack.
 len() builtin function is used to find the number of elements in the glassStack.
def size(glassStack):
return len(glassStack)

5) A function named top ( ):

 This function is used to read the most recent element (TOP) in the stack.
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x =len(glassStack)
element=glassStack[x-1]
return element

6) A function named opPop ( ):

 This function deletes and returns top most element from the stack by using pop() builtin function.
 It takes one parameter - the name of the stack (glassStack) from which element is to be deleted.
 It returns the value of the deleted element.
 The function first checks whether the stack is empty or not. If it is not empty, it removes the topmost element from it.
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 4
II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

return None
else:
return([Link]())

7) A function named display to show the contents of the stack.

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

After defining all above functions, following Python code implements a stack of glasses.
glassStack = list() # create empty stack

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

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

#display number of elements in stack

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

#delete an element from the stack

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

#add new element to stack

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

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 5

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

#display the last element added to the stack

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

#display all elements in the stack

display(glassStack)
#delete all elements from stack
while True:
item=opPop(glassStack)
if item == None:
print("Stack is empty now")
break
else:
print("Popped element is",item)

Notations for arithmetic expressions

Arithmetic expressions
 Arithmetic expressions are written using operators in between operands and parentheses () are used to order the evaluation of
operators in complex expressions.
 These expressions follow infix representation and are evaluated using BODMAS rule.
 Example a+b, m/n*y
 any arithmetic expression can be represented in any of the three notations viz. Infix, Prefix and Postfix.

Infix expressions
 It is an expression in which operators are present in between operands.
 Example: x + y, 2 - 3 * y

Polish notation or prefix notation

 It is a representation of arithmetic expressions in which operators are written before their operands.
 Polish mathematician Jan Lukasiewicz introduces this in the 1920's.
 Here order of operations (operators) and operands determines the result, making parentheses unnecessary.
 For example, x+y is written in polish notation (prefix) as +xy.

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 6

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

Reverse polish notation or postfix notation

 It is a representation of arithmetic expressions in which operators are written after their operands.
 For example, x+y can be written as xy+.

Need of Conversion from Infix to Postfix Notation

 It is easy for humans to evaluate an infix expression using BODMAS rule.
 This is because the order of precedence of operators follows BODMAS rule.
 But this rule is not used by computers. Computer uses prefix or postfix expressions.
 Prefix/postfix expressions do not follow precedence of operators because the operators are already positioned according to their
order of evaluation.
 Hence, a single traversal from left to right is sufficient to evaluate the expression.

Conversion from Infix to Postfix Notation

 Stack is used for conversion form infix to postfix expressions.
 During such conversion, a stack keeps track of the operators encountered in the infix expression.
 A variable of string type is used to store the equivalent postfix expression.

Algorithm to converts an expression in infix notation to postfix notation:

Step 1: Create an empty string named postExp to store the converted postfix expression.
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 it to the Stack
ELSE IF character is a right parenthesis
THEN POP the elements from the Stack and append to postEXP string
Until the left parenthesis,
Pop and discarding 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 and append to string postExp
before pushing this operator on the postStack
ELSE PUSH operator on the Stack
ELSE Append the character to postExp

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 7

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

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

Example
1) Convert a+b-c*d to postfix expression 2) Convert (x+y)/(z*8) to postfix expression
inExp Stack postExp
a a inExp Stack postExp
+ + a ( (
b + ab x ( x
- - ab+ + (+ x
c - ab+c y (+ xy
* -* ab+c ) xy+
d -* ab+cd / / xy+
ab+cd*- ( /( xy+
z /( xy+z
* /(* xy+z
8 /(* xy+z8
) / xy+z8*
xy+z8*/

3) Convert (x*y)/(z*5) 4) Convert 3*(4+5) to postfix expression

inExp Stack postExp
( (
x ( x
* (* x
y (* xy
) xy*
/ / xy*
( /( xy*
z /( xy*z
* /(* xy*z
5 /(* xy*z5
) xy*z5*/

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 8

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

Evaluation of Postfix Expression

 Stacks can be used to evaluate an expression in postfix notation.
 For simplification, it is assumed that operators used in expressions are binary operators.

Algorithm: Evaluation of postfix expression

Step 1: INPUT postfix expression in a variable, say postExp
Step 2: For each character in postExp, REPEAT Step 3
Step 3: IF character is an operand
THEN PUSH character on the Stack
ELSE if character is operator
Then POP two elements from the Stack, apply the operator on these elements
and PUSH the computed value onto the Stack
Step 4: IF Stack has a single element
THEN POP the element as final output
ELSE OUTPUT “Invalid Postfix expression”

1) Evaluate the postfix expression 7 8 2*4/+

postExp =7 8 2*4/+
Symbol Operation Stack Output
7 Push 7 into stack 7
8 Push 8 into stack 7 8
2 Push 2 into stack 7 8 2
* Pop 2 and 8, multiply(8*2) and push result to stack 7 16
4 Push 4 into stack 7 16 4
/ Pop 4 and 16, divide (16/4) and push result to stack 7 4
+ Pop 4 and 7, add (7+4) and push result to stack 11
No elements Pop 11 from stack. 11 is final answer 11

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 9

II PUC 2025-26 (New syllabus) Computer Science Chapter 3 Stack

2) Evaluate the postfix expression ab + cd*-

Assume a=5 b=4 c=3 d=2
postExp= ab + cd*-
Symbol Operation Stack Output
5 Push 5 into stack 5
4 Push 4 into stack 5 4
+ Pop 4 and 5, add(5+4) and push result to stack 9
3 Push 3 into stack 9 3
2 Push 2 into stack 9 3 2
* Pop 2 and 3, multiply(3*2) and push result to stack 9 6
- Pop 6 and 9, subtract (9-6) and push result to stack 3
No elements Pop 3 from stack. And 3 is the final answer 3

3) Evaluate the postfix expression xy*z5*/

Assume x=2 y=3 z=4
postExp= xy*z5*/
Symbol Operation Stack Output
2 Push 2 into stack 2
3 Push 3 into stack 2 3
* Pop 3 and 2, multiply(2*3) and push result to stack 6
4 Push 4 into stack 6 4
5 Push 5 into stack 6 4 5
* Pop 5 and 4, multiply(4*5) and push result to stack 6 20
/ Pop 20 and 6, divide(6/20) and push result to stack 0.3
No elements Pop 0.3 from stack and 0.3 is the final answer 0.3

Dept. Of Computer Science, Sri Adichunchanagiri Ind PU college, Shivamogga 10