# 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.

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

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

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

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.

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.

deletionRear( )

deletionRear( )

deletionFront( )

deletionFront( )

2. Compare and contrast queue with 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.

```# 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("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()

dequeue()

dequeue()

dequeue()

enqueue(1)

Answer: Status of Queue after each operations:-

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

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

```'''
#--------------------------------------#
#           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")```

Output:

Enter a String : naman

Given naman is a PALINDROME

Enter a String : tanmay

Given tanmay is NOT a PALINDROME