Class 12 Computer Science Queues NCERT Exercise Solution

Queue

1. Fill in the blank.

a) ________ is a linear list of elements in which insertion and deletion takes place from different ends.

Answer : Queue

b) Operations on a queue are performed in ______ order.

Answer : FIFO

c) Insertion operation in a queue is called _________ and deletion operation in a queue is called ________.

Answer : Enqueue, Dequeue

d) Deletion of elements is performed from _________ end of the queue.

Answer : Front

e) Elements ‘A’,’S’,’D’ and ‘F’ are present in the queue, and they are deleted one at a time, ____________ is the sequence of element received.

Answer : ‘A’, ‘S’, ‘D’, ‘F’

f) _________ is a data structure where elements can be added or removed at either end, but not in the middle.

Answer : Deque

g) A deque contains ‘z’, ’x’, ’c’, ’v’ and ‘b’ . Elements received after deletion are ‘z’, ’b’, ’v’, ’x’ and ‘c’. ________________ is the sequence of deletion operation performed on deque.

Answer : deletionFront()

deletionRear( )

deletionFront( )

deletionFront( )

2. Compare and contrast queue with stack.

Answer: Queue vs Stack:

(i) Queue support FIFO while Stack support LIFO.

(ii) In Queue, Insertion occurs at the rear end and deletion at the end. While in Stack, Insertion and Deletion at one end only i.e. top.

(iii) In Queue, Enqueue for element insertion, while in Stack, PUSH for element insertion.

(iv) In Queue, Dequeue for element deletion, while in Stack, POP for element deletioni.

(v) Queues can be implement in several ways like Circular Queue, Doubly ended queue (deque), while Stack is implemented in one way only.

3. How does FIFO describe queue?

Answer: FIFO means First In First Out. FIFO defines queues, because in queue, elements are inserted at rear and deleted at front. So the element inserted first in queue is deleted first, and the element inserted at last removed last, i.e FIFO order.

4. Write a menu driven python program using queue, to implement movement of shuttlecock in it’s box.

Answer:

# Queue Implementation 
 def clearScreen():
     print("\n"*12)
  
 def isEmpty(que):
     if que == []:
         return True
     else:
         return False
  
 def ENQUEUE(que, item):
     que.append(item)
     if len(que) == 1:
         front = rear = 0
     else:
         rear = len(que) - 1
  
 def DEQUEUE(que):
     if isEmpty(que):
         return "UNDERFLOW"
     else:
         item = que.pop(0)   #remove element at index position 0
         if len(que) == 0:
             front = rear = None
         
         return item
  
 def PEEK(que):
     if isEmpty(que):
         return "UNDERFLOW"
     else:
         front = 0
         return que[front]
  
 def DISPLAY(que):
     if isEmpty(que):
         print(" Queue is EMPTY")
     elif len(que)== 1:
         print(que[0], "<= front, rear")
     else:
         front = 0
         rear = len(que) - 1
         print(que[front], '<- front')
         for i in range(1, rear):
             print(que[i])
         print(que[rear], '<- rear')
  
  
 Queue = [] #Empty Queue
 #front = rear = None
 while True:
     
     print("QUEUE MENU")
     print("1. ENQUEUE")
     print("2. DEQUEUE")
     print("3. Peek")
     print("4. Display")
     print("5. Exit")
     clearScreen()
     option = int(input("Enter your choice (1-5) : "))
     if option == 1:
         item = int(input("Enter Shuttlecock Number :: "))
         ENQUEUE(Queue, item)
         input("Press Enter to continue....")
         
     elif option == 2:
         item = DEQUEUE(Queue)
         if item == "UNDERFLOW":
             print("Underflow !")
         else:
             print(item , 'Shuttlecock is dequeue-ed')
         input("Press Enter to continue....")
         
     elif option == 3:
         item = PEEK(Queue)
         if item == "UNDERFLOW":
             print("Underflow !")
         else:
             print("Front most Shuttlecock is ",item)
         input("Press Enter to continue....")
         
     elif option == 4:
         DISPLAY(Queue)
         input("Press Enter to continue....")
     elif option == 5:
         break
     else:
         print("Invalid Choice!")
         input("Press Enter to continue....")

5. How is queue data type different from deque data type?

Answer: In Queue insertion allow in rear end and removal (retrieval) allow from the front end.

Deque, stands for double ended queue, which allows insertion and deletion operation at both ends.

6. Show the status of queue after each operation

enqueue(34)

enqueue(54)

dequeue()

enqueue(12)

dequeue()

enqueue(61)

peek()

dequeue()

enqueue(1)

Answer: Status of Queue after each operations:-

Operations	Queue Status Initially Queue is Empty #; f = front, r = rear	Remarks / Output
enqueue(34)	34 f	Inserted 34 in Queue
enqueue(54)	34 54 f r	Inserted 54 in Queue
dequeue()	54 f r	Removed 34 from Queue
enqueue(12)	54 12 f r	Inserted 12 in Queue
dequeue()	12 f r	Removed 54 from Queue
enqueue(61)	12 61 f r	Inserted 61 in Queue
peek( )	12 61 f r	Returned 12
dequeue()	61 f r	Removed 12
dequeue()	# Empty	Removed 61
dequeue()	Error : Underflow	Queue is Empty
enqueue(1)	1 f r	Inserted 1 in Queue

Queue Operation | mycstutorial.in

7. Show the status of deque after each operation

peek()

insertFront(12)

insertRear(67)

deletionFront()

insertRear(43)

deletionRear()

deletionFront()

deletionRear()

Answer: Status of deque after each operation

Operations	Queue Status, Initially Queue is Empty #; f = front, r = rear	Remarks / Output
peek	#	Deque is Empty
insertFront(12)	12 f r	Inserted 12 in Deque
insertRear(67)	12 67 f r	Inserted 67 in Deque
deletionFront()	67	12 is Deleted
insertionRear(43)	67 43 f r	Inserted 43 in Deque
deletionRear()	67 f r	Removed 43 from Deque
deletionFront()	#	Deque is Empty
deletionRear()	Error : Underflow

Deque Operation | mycstutorial.in

8. Write a python program to check whether the given string is palindrome or not, using deque. (Hint : refer to algorithm 4.1)

Answer:

'''
 #--------------------------------------#
 #           Chapter 3 :- Queue         #
 #  Check given string is palindrome or #
 #             not using deque          #
 #          Author : Anjeev Singh       #
 #--------------------------------------# 
'''

 def insertRear(que, ch):
     que.append(ch)

 def deletionFront(que):
     if que != []:
         return que.pop(0)
 
 def deletionRear(que):
     if que != []:
         return que.pop()
 
 def palindromeCheck(string):
     palindrome = True
     for ch in string:     
         insertRear(strque, ch) 
     while len(strque) > 1 and palindrome:     
         first = deletionFront(strque)     
         last = deletionRear(strque)
          if first != last:         
             palindrome = False 
     return palindrome
 
#__main__
 strque = []
 string = input("Enter a String : ")
 if palindromeCheck(string):
     print("Given String ", string, "is a PALINDROME")
 else:
     print("Given string ", string, "is NOT a PALINDROME")