TOPIC-4

Stacks And Queues With Lists

Very Short Answer Type Questions (1 mark)

Question 1:
Expand the following:

1. LIFO
2. FIFO

Answer:

1. LIFO: Last-In First-Out

2. FIFO: First-In First-Out

Question 2:
Define stack.
Answer:
A stack is a data structure that allows adding and removing elements in a
particular order. Every time an element is added, it goes on the top of the
stack; the only element that can be removed is the element that was at
the top of the stack.

Question 3:
Define Queue.
Answer:
Queue is a first-in, first-out (FIFO) data structure, i.e. the element added
first to the queue will be the one to be removed first. Elements are always
added to the rear of the queue and removed from the front of the queue.

Question 4:
Write all the operations possible in data structure.
Answer:
The major operations are:

1. Traversal
2. Insertion
3. Deletion
4. Searching

Question 5:
What are the two major queue operations?
Answer:
Addition of element is known as INSERT operation, also known as
enqueuing. It is done using rear terminal position, i.e. tail end. Removal of
element is known as DELETE operation, also known as dequeueing.
 Short Answer Type Questions-I (2 marks)

Question 1:
Write an algorithm to implement push operation.
Answer:

1. Start
2. Initialize top with -1.
3. Input the new element.
4. Increment top by one.
5. stack[top]=new element
6. Print “Item Inserted”
7. Stop

Question 2:
Write an algorithm to implement pop operation.
Answer:

1. Start
2. If the value of top is -1 go to step 3 else go to step 4
3. Print “Stack Empty” and go to step 7
4. Deleted item = Stack[top]
5. Decrement top by 1
6. print “Item Deleted”
7. Stop

Question 3:
Write an algorithm to implement insertion opera¬tion of queue.
Answer:

1. Start
2. Check FRONT and REAR value,
1. if both the values are -1, then FRONT and REAR are
incremented by 1
2. other wise Rear is incremented by one.
3. queue [Rear]=new element.
4. Stop

Question 4:
Write an algorithm to implement deletion operation of queue.
Answer:

1. Start
2. Check for underflow situation by checking value of Front=-1
1. If it is display appropriate message and stop
2. Otherwise Deleted item=queue [Front]
 3. If Front=Rear then Front=Rear=-1 Otherwise Front is
incremented by one
4. Print “Item Deleted”
5. Stop

Question 5:
For a given list of values in ascending order, write a method in Python to
search for a value with the help of Binary Search method. The method
should return position of the value and should return -1 if the value not
present in the list.
Answer:
def Binary Search (list, search):
lower_bound=0
upper_bond=len(list) -1
found=false
pos=’x’
while lower_bound< =upper_bond:
middle_pos=(lower_bound + upper_bond)/2
if list [middle_pos] = = search:
pos=middlepos found=True break
elif search < list [middle_pos]:
upper_bound=middle_pos-l else:
lower_bound=middle_pos + 1 if found:
print(“The item found”, pos) else:
print (“The item not available”)
return (-1)

Long Answer Type Questions (4 marks)

Question 1:
Write Insert (city) and Delete (City) methods in Python to add City and
Romave City considering them to act as Insert and Delete operations of
the data structure Queue.
Answer:
class queue:
city=[ ]
def Insert (self):
a = raw_input(“Enter city”)
queue.city append (a)
def Delete (self):
if (queue, city = = []):
print “Queue empty”
else:
print “Deleted element is”,
queue.city[0]
queue.city.delete ()
OR
class queue:
city=[ ]
def Insert(self):
a=raw_input(“Enter city”)
queue.a.append(a)
def Delete(self):
if (queue.city==[ ]):
print (“Queue emtpy”)
else
print (“Deleted element is”,queue, city [0])

Question 2:
Define stack class in Python to operate on stack of numbers.
Answer:
class Stack:
def_init_(self):
self.s = [ ]
def push(self):
a = input(“Enter number”)
self.s. append(a)
def pop(self):
self.s.pop()
def display (self):
l = len(self.s)
for I in range(l-1,1,-1):
print self.s[i]

Question 3:
Write a function to push any student’s information to stack.
Answer:
def push(stack):
s=[]
print “STACK BEFORE PUSH” display(stack)
s.append(input(“Enter student rollno?”))
s.append(raw_input(“Enter student name”))
s.append(raw_input(“Enter student grade”))
stack, append(s)
def display (stack):
l=len(stack)
print “STACK CONTENTS”
for i in range(l-1,-1,-1):
print stack[i]
stack=[]
print “Creating Stack”
n = input(“Enter the number of students”)
for i in range(n): student = []
student.append(input(“Enter student rollno?”))
student.append(raw_input(“Enter student name”))
student.append(raw_input(“Enter student grade”))
stack, append(student) push(stack)
display(stack)
Question 4:
Write the push operation of stack containing names using class.
Answer:
class stack:
s=[]
def push(self):
a=r’aw_input(“Enter any name :”)
stack.s.append(a)
def display(self):
l=len(stack.s) for i in range(l-1,-1,-1):
print stack.s[i]
a=stackO
n= input(“Enter no. of names”)
for i in range (n):
a.push()
a.display()

Question 5:
Write Insert (Place) and Delete (Place) methods in Python to be add Place
and Remove Place considering them to act as Insert and Delete
operations of the data structure Queue.
Answer:
Class queue: place=[]
def Insert (self):
a=raw_input (“Enter city”)
queue.place. append (a)
def delete (self):
if (queue.place = = []):
print “Queue empty”
else:
print “Deleted element is”, queue, place [0]
class queue :
place = [ ]
def Insert (self) 1
a = rawjnput (“Enter place”) queue, a.append (a)
def delete (self):
if (queue.place==[ ] ):
print (“Queue empty”)
else:
print (“Deleted element is” queue, place [0])
queue.place.delete ( )

Question 6:
Write the pop operation of stack containing names using class.
Answer:
class stack:
s=[]
def push (self):
a=raw_input(“Enter any name :”)
stack.s.append(a)
def pop(self):
if (a.s==D):
print “Stack Empty”
else:
print “Deleted element is : ”,
a.s.pop()
def display (self):
l=len(stack.s)
print “STACK CONTENTS”
for i in range(l-1,-1,-1):
print stack.s[i]
a=stack()
n= input(“Enter no. of names”)
for i in range(n):
a.push()
a.pop()
a.display()

Question 7:
Write the pop operation of stack containing num-bers using class.
Answer:
class stack:
s=[]
def push(self):
a=input(“Enter number :”)
stack.s.append(a)
def pop(self):
if (a.s==[]):
print “Stack Empty”
else:
print “Deleted element is : ”,a.s.pop()
def display(self):
l=len(stack.s) print “STACK CONTENTS”
for i in range(l-1,-1,-1):
print stack.s[i]
a=stack()
n= input(“Enter count of numbers”)
for i in range (n):
a.push()
a.pop()
a. display ()

Question 8:
Write a function to add any customer’s information to queue.
Answer:
def insert(queue): customer=[]
print “QUEUE BEFORE INSERT” display(queue)
customer.append(input(“Enter customer number?’’))
customer.append(raw_input(“Enter customer name”))
customer.append(input(“Enter customer phone number”))
queue. append(customer)
def display (queue):
l=len(queue)
fori in range(O.l): print queue[i]
queue=[]
print “Creating Queue”
n=input(“Enter the number of customers”)
for i in range(n):
customer=[]
customer. append(input(“Enter customer number?”))
customer.append(rawjnput(“Enter customer name”))
customer.append(input(“Enter customer phone number”))
queue.append(customer)
insert(queue)
display(queue)

Question 9:
Write the insertion operation of queue containing character using class.
Answer:
class queue:
s=0
def insert(self):
a=raw_input(“Enter any letter:”)
queue.s.append(a)
def display (self):
l=len(queue.s)
print “QUEUE CONTENTS”
for i in range(o,l):
print queue. s[i]
a=queue()
n= input(“Enter no. of letters”)
for i in range(n): a.insert()
ch = raw_input(“Do you want to insert more letters”)
if ch==‘y’:
a.insert()
a.display()

Question 10:
Write Add(Fruit) and Remove (Fruit) methods in Python to insert name of
a Fruit and to delete name of a Fruit considering them to act as Insert and
Delete operations of the data structure Queue.
Answer:
def que insert (fruit, Rear) :
ch=‘y’
while ch==‘y’ or ch==‘yes’
Frt=input(“Enter a fruit”)
Rear=Rear + 1
Fruit, append (Frt)
print(“Do you wand to Add more”)
ch=input ().upper ( )
if ch==’N’ or ch==‘No’ :
break
return rear
def quedelete (Fruit, Rear):
if not len (fruist):
print f(“Fruit + list is empty”)
else :
Rear = Rear – 1
Frt = Fruit.pop( )
print(“Fruit is delete from list”)
return Rear

Question 11:
Write the deletion operation of queue containing characters using class.
Answer:
class queue:
s=0
def insert(self):
a=raw_input(“Enter any letter:”)
queue.s.append(a)
def delete(self):
if (a.s==[]):
print “Queue Empty”
else:
print “Deleted element is: ”,queue.s[0]
del queue.s[0]
def display(self): l=len(queue.s)
print “QUEUE CONTENTS”
for i in range(0,l):
print queue.s[i]
a=queue()
n= input(“Enter no. of letters”)
for i in range (n):
a.insert()
a. delete()
a. display ()

Question 12:
Write the deletion operation of queue containing numbers using class.
Answer:
class queue:
s=[]
def insert(self):
a=input(“Enter the number:”)
queue.s.append(a)
def delete(self):
if (a.s==Q):
print “Queue Empty”
else:
print “Deleted element is: ”,queue.s[0]
del queue.s[0]
def display(self):
l=len(queue.s)
print “QUEUE CONTENTS”
for i in range(0,l):
print queue.s[i]
a=queue()
n= input(“Enter no. of numbers”)
for i in range(n):
a.insert()
a.delete()
a.display()

TOPIC-5
Applications of Stacks
Very Short Answer Type Questions (1 mark)

Question 1:
Give one example of infix expression.
Answer:
A + B *C / D

Question 2:
Give one example of postfix expression.
Answer:
ABC*D/+

Question 3:
Give one example of prefix expression.
Answer:
+/*BCDA

Question 4:
Convert (A+B)*C in to postfix form.
Answer:
AB+C*

Short Answer Type Questions-I (2 marks)

Question 1:
Evaluate the following postfix notation of expressio,
Show status of stack after every operation.
12,2,7,34,20,-, +,5, +
Answer:

Question 2:
Evaluate the following postfix expression. Show the status of stack after
execution of each operation separately: 2,13, + , 5, -,6,3,/,5,*,<
Answer:
Stack contents

Result: 0

Question 3:
Evaluate using stack 10, 3,*, 30, 2,*,-
Answer:

Question 4:
Evaluate the following Postfix expression :
20,10,-15,3,/, +, 5, *
Answer:

Question 5:
Convert A+ (B*C – (D / E A F) * G) * H into postfix form showing stack
status after every step.
Answer:

Question 6:
Convert (True And False) OR (False And True) into postfix form using
stack.
Answer:
Question 7:
What are the applications of queue in computer?
Answer:
In a single processor multitasking computer, job(s) wait to be processed
form a queue. Same happens when we share a printer with many
computers.

 Compiling a HLL code.

 Using download manager, for multiple files also uses queue for
ordering the files.
 In multiuser OS – job scheduling is done through queue.

Question 8:
Evaluate the following postfix notation of expression. Show status of stack
after every operation.
Answer:
Final Result = 1

Question 9:
Evaluatethefollowingpostixnotationofexpression. Show status of stack
after every operation.
12,2, *, 24,20, -, +, 8, –
Answer:

Question 10:
Give few applications of stack.
Answer:

1. Expression evaluation
2. Backtracking (game playing, finding paths, exhaustive
searching).
3. Memory management, run-time environment for nested
language features.

Short Answer Type Questions-II (2 marks)

Question 1:
Write an algorithm to evaluate postfix expression.
Answer:
Step 1: Start
Step 2: Check all symbols from left to right and repeat steps 3 & 4 for
each symbol of expression ‘E’ until all symbols are over.

1. If the symbol is an operand, push it onto stack.

2. If the symbol is an operator then:
3. Pop the top two operands from stack and apply an operator in
between them.
4. Evaluate the expression and place the result back on the stack.

Step 3: Set result equal to top element on the stack.

Step 4: Stop

Question 2:
Write an algorithm to convert infix to postfix.
Answer:

1. Create an empty stack and an empty postfix output

string/stream.
2. Scan the infix input string/stream left to right.
3. If the current input token is an operand, simply append it to the
output string (note the examples above that the operands
remain in the same order).
4. If the current input token is an operator, pop off all operators
that have equal or higher precedence and append them to the
output string; push the operator onto the stack. The order of
popping is the order in the output.
5. If the current input token is push it onto the stack.
6. If the current input token is ‘)’, pop off all operators and
append them to the output string until a ‘(‘ is popped; discard
the ‘(‘.
7. If the end of the input string is found, pop all operators and
append them to the output string.