Chapter-3 Stack 2025
IntroductIon
A data structure defines a mechanism to store, organise and access data along with operations (processing) that
can be efficiently performed on the data
A stack is an ordered collection of items in which an element may be inserted or deleted only at same end.
This end is called as the top of the stack.
Stacks are sometimes known as LIFO (Last In First Out).
Operation on Stacks:
Stack ( ): It creates a new stack that is empty. It needs no parameter and returns an
empty stack.
push (item): It adds a new item to the top of the stack.
pop ( ): It removes the top item from the stack.
peek ( ): It returns the top item from the stack but does not remove it.
isEmpty ( ): It tests whether the stack is empty.
size ( ): It returns the number of items on the stack.
SUDHEER KN , HOD VANI PU COLLEGE Page 1
Chapter-3 Stack 2025
SUDHEER KN , HOD VANI PU COLLEGE Page 2
Chapter-3 Stack 2025
Implementation Of Stack In Python
insert/delete elements (glasses)
check if the STACK is empty (no glasses in the stack)
find the number of elements (glasses) in the STACK
read the value of the topmost element (number on the topmost glass) in the STACK
Let us create an empty stack named glassStack. We will do so by assigning an empty list to the identifier
named glassStack:
glassStack = list()
A function named isEmpty to check whether the stack glassStack is empty or not.
def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False
A function named opPush to insert (PUSH) a new element in stack. This function has two parameters - the
name of the stack in which the element is to be inserted (glassStack) and the element that needs to be
[Link] the built-in method append() of list to add an element to the stack that always adds at the end of
the list.
def opPush(glassStack,element):
[Link](element)
A function named size to read the number of elements in the glassStack.
def size(glassStack):
return len(glassStack)
A function named top to read the most recent element (TOP) in the glassStack.
def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x =len(glassStack)
element=glassStack[x-1]
return element
A function named opPop to delete the topmost element from the stack. It takes one parameter – the name of
the stack (glassStack) from which element is to be deleted.
def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
SUDHEER KN , HOD VANI PU COLLEGE Page 3
Chapter-3 Stack 2025
else:
return([Link]())
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])
EXAMPLE:
glassStack = list() # create empty stack
#add elements to 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)
#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)
The output of the above program will be as follows:
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
SUDHEER KN , HOD VANI PU COLLEGE Page 4
Chapter-3 Stack 2025
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
Underflow
Stack is empty now
Notations For Arithmetic Expressions
Conversion of expression from infix 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 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
while 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
SUDHEER KN , HOD VANI PU COLLEGE Page 5
Chapter-3 Stack 2025
postExp before pushing this operator on the
postStack
ELSE PUSH operator on the Stack
ELSE Append the character to postExp
Step 5: Pop elements from the Stack and append to postExp until Stack is empty
Step 6: OUTPUT postExp
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 POP two elements from the Stack, apply the operator on
the popped elements and PUSH the computed value onto
the Stack
SUDHEER KN , HOD VANI PU COLLEGE Page 6
Chapter-3 Stack 2025
Step 4: IF Stack has a single element
THEN POP the element and OUTPUT as the net result
ELSE OUTPUT “Invaild Postfix expression”
Evaluate following postfix expressions while showing status of stack after each operation given A=3, B=5,
C=1, D=4
a) A B + C *
b) A B * C / D *
6. Convert the following infix notations to postfix notations, showing stack and string contents at each step.
a) A + B - C * D
b) A * (( C + D)/E)
SUDHEER KN , HOD VANI PU COLLEGE Page 7