CHAPTER-3
STACK
3.1 Introduction OF Stack
3.2 Operations Of Stack
3.3 Implementation Of Stack
3.4 Notations For Arithmetic Expressions
3.5 Conversion From Infix To Postfix Notation
3.6 Evaluation Of Postfix Expressions
INTRODUCTION OF STACK 2 marks
Definition: stack is a linear data structure, it follows LIFO
principle OR FILO principle
✓ It has only one end that is TOP
✓ LIFO implies that the element that is inserted last,
comes out first
✓ FILO implies that the element that is inserted first,
comes out last
Operations of stack
1. Push operation
2. Pop operation 5 marks
3. Peek operation
4. Is_empty
5. Is_full
6. Display
Push operation
✓ It is used to inserting or adding an element into the
stack.
✓ The method is used to implementing a program is
[Link](x)
✓ Ex:
stack=[]
[Link](10)
[Link](20)
[Link](30)
print(stack)
output
[10,20,30]
Pop operation
✓ It is used to deleting or removing an element from the
stack.
✓ The method is used to implementing a program is
[Link]()
✓ Ex:
stack=[]
[Link](10)
[Link](20)
[Link](30)
[Link]()
[Link]()
print(stack)
output
[10]
Peek operation
✓ It returns a value of top element from the stack.
✓ The method is used to implementing a program is stack[-1]
✓ Ex:
stack=[]
[Link](10)
[Link](20)
[Link](30)
print(stack[-1])
output
[30]
Is_empty operation
✓ Its check whether the stack is empty OR not.
✓ The method is used to implementing a program is
len(stack)==0
✓ Ex:
stack=[]
if len(stack)==0:
print (“stack is empty or underflow”)
else:
print (“stack elements:”, stack)
output
stack is empty or underflow
Is_Full operation
✓ Its check whether the stack is Full OR not.
✓ The method is used to implementing a program is
len(stack)
✓ Ex:
Size=3
stack=[]
[Link](10)
[Link](20)
[Link](30)
if len(stack)==3:
print (“stack is full or overflow”)
else:
print (“stack elements:”, stack)
output
stack is full or overflow
Display operation
✓ It returns all elements from the stack.
✓ The method is used to implementing a program is stack
✓ Ex:
stack=[]
[Link](10)
[Link](20)
[Link](30)
print(stack)
output
[10,20,30]
Implementation of stack in python
Program:
stack=[]
[Link](10) Practical
print("push operation:10")
[Link](20)
print("Push operation :20")
[Link](30)
print("Push operation :30"
print("stack elements are:”, stack)
print("peek elements :",stack[-1])
print("pop operation:”, stack. Pop())
print("pop operation:”, stack. Pop())
print("pop operation:”, stack. Pop())
if len(stack)==0:
print("stack is empty or underflow")
else:
print("stack elements:",stack)
output
push operation : 10
Push operation : 20
Push operation : 30
stack elements are: [10, 20, 30]
peek elements : [30]
pop operation: [30]
pop operation: [20]
pop operation: [10]
stack is empty or underflow
Applications of Stack in Real Life
1. Pile of Clothes in an Almirah
5 marks
2. Multiple Chairs in a Vertical Pile
3. Bangles Worn on Wrist
4. Pile of Boxes in Pantry or Kitchen Shelf
Pile of Clothes in an Almirah
✓ A stack follows the LIFO (Last In, First Out) principle.
✓ In an almirah, when clothes are piled one over another, the
last cloth placed on top is the first one to be removed.
✓ For example, if you place shirts one by one, the shirt kept
at the top will be taken out first. To take a cloth from
the bottom, you must first remove all the clothes above it.
✓ Thus, it behaves exactly like a stack.
Multiple Chairs in a Vertical Pile
✓ When chairs are arranged in a vertical stack (like in
functions or classrooms), the last chair placed on top is
removed first when needed.
✓ If someone wants the bottom chair, all chairs above it must
be removed first.
✓ This arrangement clearly follows the LIFO principle, making
it a perfect example of stack usage in daily life.
Bangles Worn on Wrist
✓ Bangles are worn one after another on the wrist. The last
bangle worn is closest to the hand and is removed first.
✓ To remove a bangle that is inside, you must first remove
the bangles above it.
✓ This process follows the Last In, First Out order, just
like a stack data structure.
Pile of Boxes in Pantry or Kitchen Shelf
✓ In a kitchen or pantry, boxes (like food containers) are
often kept one above another. The last box placed on top
is the first to be taken out.
✓ If a box at the bottom is needed, all the boxes above it
must be removed first.
✓ This arrangement again follows the LIFO principle, showing
how stacks are used in everyday storage.
Applications of Stack in Programming
1. Expression Evaluation
2. Infix to Postfix / Prefix Conversion
5 marks
3. Function Calls (Recursion)
4. Undo and Redo Operations
5. Syntax Checking (Balanced Parentheses)
Expression Evaluation
✓ Stacks are used to evaluate postfix and prefix expressions.
✓ In postfix evaluation, operands are pushed into the stack,
and when an operator appears, calculations are performed
by popping elements.
✓ This helps in easy and fast computation without using
brackets.
Infix to Postfix / Prefix Conversion
✓ Stacks are used to convert infix expressions into postfix
or prefix form.
✓ Operators and parentheses are handled using a stack to
maintain precedence and order.
✓ This conversion is important because postfix expressions
are easier for computers to evaluate.
Function Calls (Recursion)
✓ Stacks are used in function calls and recursion.
✓ Whenever a function is called, its return address and local
variables are stored in the stack.
✓ After execution, the function is removed from the stack.
✓ This is called the call stack.
Undo and Redo Operations
✓ Stacks are used in applications like text editors.
✓ When a user performs an action, it is pushed onto the stack.
✓ Undo operation pops the last action
✓ Redo uses another stack to restore the action
✓ This helps in managing user actions efficiently.
Syntax Checking (Balanced Parentheses)
✓ Stacks are used to check whether parentheses like ( ), {
}, [ ] are balanced.
✓ Opening symbols are pushed into the stack, and closing
symbols pop them.
✓ If the stack is empty at the end, the expression is correct.
✓ This is widely used in compilers.
Notations For Arithmetic Expressions
✓ Arithmetic notations is a method of writing mathematical
expressions using operands(numbers/variables) and
operators (+, -, *, /) in a specific order.
✓ Arithmetic notation is the representation of arithmetic
expressions using operators and operands.
Arithmetic Expression
It is the actual combination of operands and operators.
Arithmetic Notation
It is the way of writing that expression (Infix, prefix and
postfix)
Types of Expressions
1. Infix expression 2 marks
2. Prefix expression
3. Postfix expression
Infix Expression:
✓ The operator are written in between operands.
✓ Infix notation is also known as standard algebraic
notation.
✓ Ex: A+B ,3*2, x+y*3
Prefix Expression:
✓ The operator are written before the corresponding
operands.
✓ Prefix expression is also known as polish notation.
✓ Ex: +AB , *3+45 ,+z*xy
Postfix Expression:
✓ The postfix operator are written after the corresponding
operands.
✓ Postfix expression is also known as reverse polish notation.
✓ Ex: AB+ ,AB+3- ,AB+34*/
Conversion of Infix Expression to Postfix Expression
Algorithm
Step 1: START 5 marks
Step 2: Input the Infix Expression
Step 3: Read each symbol of the infix expression from left to right
If the symbol is an operand, append it to the Postfix
Expression
If the symbol is a left parenthesis (, push it onto the stack
If the symbol is an operator, then
✓ While the stack is not empty and the precedence of the
top of the stack is greater than or equal to the
precedence of the current operator,
✓ pop the operator from the stack and append it to the
postfix expression
✓ Push the current operator onto the stack
If the symbol is a right parenthesis ), then
✓ Pop operators from the stack and append them to postfix
expression until a left parenthesis is encountered
✓ Remove the left parenthesis from the stack (do not append
it)
Step 4: After reading the entire expression, pop all remaining
operators from the stack and append them to postfix expression
Step 5: Output the Postfix Expression
Step 6: STOP
Example 1: (X+Y)/(Z+8)
Example 2: A*B+3-4
Example 3: A+B-X*d
Example 4: A*((2+d-3)/E)
Example 5: ((2+3)*(4/2))+2
Evaluation of Postfix Expression
Algorithm
5 marks
Step 1: START
Step 2: Input the Postfix Expression
Step 3: Scan the postfix expression from left to right
If the symbol is an operand, push it onto the stack
If the symbol is an operator, then
✓ Pop two operands from the stack
✓ Perform the arithmetic operation (operand1 operator
operand2)
✓ Push the result back onto the stack
Step 4: After scanning the entire expression, pop the final result
from the stack
Step 5: Output the Result
Step 6: STOP
Example 1: shows the step by step process of evaluation of the
postfix expression 782*4/+ using the algorithm?
Example 2: evaluate following postfix expression whilw showing
status of stack after each operation given A=3,b=5,c=1 and d=4
a) AB+c*
b) AB*C/D*
c) 23+42/*
d) AB+CD*-
e) A2D+B/*
Example:
State True or False for the following cases MCQ(1m)
a) Stack is a linear data structure
➢ True
b) Stack does not follow LIFO Rule
➢ False
c) Push operation may result into underflow condition
➢ False
d) In Postfix notation for expression, operators are placed
after operands
➢ True
e) In Prefix notation for expression, operators are placed
after operands
➢ False
f) In infix notation for expression, operators are placed in
between the operands.
➢ True