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.
(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.
Answer
(a) Queue
(b) FIFO
(c) enqueue, dequeue
(d) front
(e) 'A', 'S', 'D', 'F'
(f) Deque
(g)
deletionFront()
deletionRear()
deletionRear()
deletionFront()
deletionFront()
Compare and contrast queue with stack.
Answer
| Stack | Queue |
|---|---|
| Stack follows LIFO (Last in First out) principle. | Queue follows FIFO (First in First out) principle. |
| In stack, insertion and deletion occurs at one end only. | In queue, insertion occurs at the rear end and deletion occurs at the front end. |
| In stack, Push operation is used for element insertion and Pop operation is used for element deletion. | In queue, enqueue is used for element insertion and dequeue is used for element deletion. |
| There are no variations of stack. | A queue may be circular or deque. |
How does FIFO describe queue ?
Answer
FIFO, First In First Out, defines a queue because in a queue, elements are retrieved from one end (called the front end) and inserted at another end (rear end). Thus, at any time, in a queue, retrieval gets the oldest element, while always adding to the rear of the queue. Thus, items are processed in first-in, first-out (FIFO) order.
Write a menu driven python program using queue, to implement movement of shuttlecock in it's box.
Answer
queue = []
def display_queue():
if not queue:
print("Queue is empty")
else:
print("Current queue:", queue)
def enqueue(item):
queue.append(item)
def dequeue():
if queue:
removed = queue.pop(0)
print("Removed", removed, "from the queue")
else:
print("Queue is empty, cannot remove")
while True:
print("\nMENU:")
print("1. Add movement to the queue")
print("2. Remove movement from the queue")
print("3. Display current queue")
print("4. Exit")
choice = input("Enter your choice (1-4): ")
if choice == '1':
movement = input("Enter the movement (up/down): ")
enqueue(movement)
print("Added", movement, "to the queue")
elif choice == '2':
dequeue()
elif choice == '3':
display_queue()
elif choice == '4':
print("Exiting program...")
break
else:
print("Invalid choice, please try again")MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 1
Enter the movement (up/down): up
Added up to the queue
MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 1
Enter the movement (up/down): down
Added down to the queue
MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 3
Current queue: ['up', 'down']
MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 2
Removed up from the queue
MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 3
Current queue: ['down']
MENU:
1. Add movement to the queue
2. Remove movement from the queue
3. Display current queue
4. Exit
Enter your choice (1-4): 4
Exiting program...
How is queue data type different from deque data type?
Answer
Queues only allow insertion in one end (rear end) and retrieval from the other end (front end). A deque, on the other hand, is a double-ended queue, which allows flexibility with insertion or deletion such that one of these operations is allowed at both ends rather than having a fixed end for the operations.
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
| enqueue(34) | 34 | |
| ↑ ↑ | ||
| f r | ||
| enqueue(54) | 34 | 54 |
| ↑ | ↑ | |
| f | r | |
| dequeue() | 54 | |
| ↑ ↑ | ||
| f r | ||
| enqueue(12) | 54 | 12 |
| ↑ | ↑ | |
| f | r | |
| dequeue() | 12 | |
| ↑ ↑ | ||
| f r | ||
| enqueue(61) | 12 | 61 |
| ↑ | ↑ | |
| f | r | |
| Peek() | 12 | |
| dequeue() | 61 | |
| ↑ ↑ | ||
| f r | ||
| dequeue() | #Empty | |
| dequeue() | underflow | |
| dequeue() | underflow | |
| enqueue(1) | 1 | |
| ↑↑ | ||
| f r |
Show the status of deque after each operation.
peek()
insertFront(12)
insertRear(67)
deletionFront()
insertRear(43)
deletionRear()
deletionFront()
deletionRear()
Answer
| peek() | #Empty | |
| insertFront(12) | 12 | |
| ↑↑ | ||
| f r | ||
| insertRear(67) | 12 | 67 |
| ↑ | ↑ | |
| f | r | |
| deletionfront() | 67 | |
| ↑↑ | ||
| f r | ||
| insertRear(43) | 67 | 43 |
| ↑ | ↑ | |
| f | r | |
| deletionRear() | 67 | |
| ↑ ↑ | ||
| f r | ||
| deletionfront() | #Empty | |
| deletionRear() | Underflow |
Write a python program to check whether the given string is palindrome or not, using deque. (Hint : refer to algorithm 4.1)
Answer
def Deque():
return []
def addRear(deque, ch):
deque.append(ch)
def removeFront(deque):
if len(deque) == 0:
return None
return deque.pop(0)
def removeRear(deque):
if len(deque) == 0:
return None
return deque.pop()
def palchecker(aString):
chardeque = Deque()
for ch in aString:
addRear(chardeque, ch)
while len(chardeque) > 1:
first = removeFront(chardeque)
last = removeRear(chardeque)
if first != last:
return False
return True
string1 = input("Enter a string: ")
pal = palchecker(string1.lower())
if pal:
print(string1, "is a palindrome.")
else:
print(string1, "is not a palindrome.")Enter a string: anupama
anupama is not a palindrome.
Enter a string: malayalam
malayalam is a palindrome.