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

Accepted Answer

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

b) Operations on a queue are performed in FIFO (First In First Out) order.

c) Insertion operation in a queue is called enqueue and deletion operation in a queue is called dequeue.

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

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

f) Deque (Double Ended Queue) 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'. The sequence of deletion operation performed on deque is: deleteFront(), deleteRear(), deleteFront(), deleteRear(), deleteFront(). — a) Queue allows insertion at rear and deletion at front, hence different ends.

b) Queue follows FIFO order, meaning first element inserted is first to be deleted.

c) Enqueue means insertion at rear; dequeue means deletion from front.

d) Deletion is always from the front end in a queue.

e) Since queue is FIFO, elements are received in the order they were inserted.

f) Deque allows insertion and deletion at both ends but not in the middle.

g) The deletion sequence corresponds to alternating deletions from front and rear to produce the given output.

Question 2

Compare and contrast queue with stack.

Accepted Answer

Comparison between Queue and Stack:

1. Order of Operations:
- Queue follows FIFO (First In First Out) order.
- Stack follows LIFO (Last In First Out) order.

2. Insertion and Deletion:
- In Queue, insertion is at rear and deletion is at front.
- In Stack, insertion and deletion both happen at the top.

3. Usage:
- Queue is used in scheduling, buffering, etc.
- Stack is used in recursion, expression evaluation, backtracking.

4. Data Structure Type:
- Queue is a linear data structure.
- Stack is also a linear data structure but with different access rules.

5. Access:
- Queue allows access only at front and rear.
- Stack allows access only at top. — The key difference lies in the order in which elements are removed and the ends at which insertion and deletion happen. Queue is FIFO, Stack is LIFO. This affects their applications and behavior.

Question 3

How does FIFO describe queue?

Accepted Answer

FIFO stands for First In First Out. It means that the first element inserted into the queue will be the first one to be removed. This describes the behavior of a queue where elements are inserted at the rear and deleted from the front, ensuring that the order of processing is the same as the order of arrival. — FIFO ensures that elements are processed in the order they arrive, which is the fundamental property of a queue data structure.

Question 4

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

Accepted Answer

Below is a sample Python program implementing a queue to simulate the movement of shuttlecock in its box:

```python
from collections import deque

class ShuttlecockBox:
    def __init__(self):
        self.queue = deque()

def enqueue(self, item):
        self.queue.append(item)
        print(f"Inserted {item} into the box.")

def dequeue(self):
        if len(self.queue) == 0:
            print("Box is empty. No shuttlecock to remove.")
        else:
            removed = self.queue.popleft()
            print(f"Removed {removed} from the box.")

def display(self):
        if len(self.queue) == 0:
            print("Box is empty.")
        else:
            print("Current shuttlecocks in box:", list(self.queue))

def menu():
    box = ShuttlecockBox()
    while True:
        print("
Menu:")
        print("1. Insert shuttlecock")
        print("2. Remove shuttlecock")
        print("3. Display shuttlecocks")
        print("4. Exit")
        choice = input("Enter your choice: ")

if choice == '1':
            item = input("Enter shuttlecock to insert: ")
            box.enqueue(item)
        elif choice == '2':
            box.dequeue()
        elif choice == '3':
            box.display()
        elif choice == '4':
            print("Exiting program.")
            break
        else:
            print("Invalid choice. Please try again.")

if __name__ == '__main__':
    menu()
```

This program uses a queue to insert and remove shuttlecocks, simulating their movement in a box. — The program uses Python's deque to implement queue operations enqueue and dequeue. The menu allows user interaction to insert, remove, and display shuttlecocks, demonstrating queue behavior.

Question 5

How is queue data type different from deque data type?

Accepted Answer

Queue is a linear data structure where insertion happens at the rear end and deletion happens at the front end only. It follows FIFO order strictly.

Deque (Double Ended Queue) is a generalized form of queue where insertion and deletion can happen at both front and rear ends. It supports more flexible operations than a queue. — Queue restricts operations to one end for insertion and the other for deletion, while deque allows both operations at both ends, making it more versatile.

Question 6

Show the status of queue after each operation
enqueue(34)
enqueue(54)
dequeue()
enqueue(12)
dequeue()
enqueue(61)
peek()
dequeue()
dequeue()
dequeue()
enqueue(1)

Accepted Answer

Initial queue: empty

Operation 1: enqueue(34) -> Queue: [34]
Operation 2: enqueue(54) -> Queue: [34, 54]
Operation 3: dequeue() -> removes 34 -> Queue: [54]
Operation 4: enqueue(12) -> Queue: [54, 12]
Operation 5: dequeue() -> removes 54 -> Queue: [12]
Operation 6: enqueue(61) -> Queue: [12, 61]
Operation 7: peek() -> returns 12 (front element), Queue unchanged: [12, 61]
Operation 8: dequeue() -> removes 12 -> Queue: [61]
Operation 9: dequeue() -> removes 61 -> Queue: []
Operation 10: dequeue() -> Queue is empty, cannot dequeue
Operation 11: enqueue(1) -> Queue: [1] — Stepwise:
- Enqueue adds element at rear.
- Dequeue removes element from front.
- Peek returns front element without removing.
- When queue is empty, dequeue operation cannot remove any element.

The queue status after each operation is updated accordingly.

Question 7

Show the status of deque after each operation
peek()
insertFront(12)
insertRear(67)
deletionFront()
insertRear(43)
deletionRear()
deletionFront()
deletionRear()

Accepted Answer

Initial deque: empty

Operation 1: peek() -> Deque is empty, no element to peek.
Operation 2: insertFront(12) -> Deque: [12]
Operation 3: insertRear(67) -> Deque: [12, 67]
Operation 4: deletionFront() -> removes 12 -> Deque: [67]
Operation 5: insertRear(43) -> Deque: [67, 43]
Operation 6: deletionRear() -> removes 43 -> Deque: [67]
Operation 7: deletionFront() -> removes 67 -> Deque: []
Operation 8: deletionRear() -> Deque is empty, cannot delete — Operations on deque allow insertion and deletion at both ends:
- insertFront adds element at front.
- insertRear adds element at rear.
- deletionFront removes element from front.
- deletionRear removes element from rear.
- peek returns front element if present.

The deque status is updated after each operation accordingly.

Question 8

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

Accepted Answer

Below is a Python program to check palindrome using deque:

```python
from collections import deque

def is_palindrome(s):
    d = deque()
    for ch in s:
        d.append(ch)

while len(d) > 1:
        front = d.popleft()
        rear = d.pop()
        if front != rear:
            return False
    return True

# Example usage
string = input("Enter a string: ")
if is_palindrome(string):
    print(f"{string} is a palindrome.")
else:
    print(f"{string} is not a palindrome.")
```

Explanation:
- The string characters are added to a deque.
- Characters are compared from front and rear by popping from both ends.
- If all pairs match, the string is palindrome; otherwise not. — Using deque allows efficient removal of characters from both ends to compare for palindrome property. The algorithm continues until all characters are checked or a mismatch is found.

Question 9

Which of the following best describes the Queue data structure?

Accepted Answer

A linear data structure following FIFO where insertion is at rear and deletion is at front — Queue is a linear data structure following the First-In-First-Out (FIFO) strategy, meaning elements are inserted at the rear and deleted from the front.

Question 10

Which operation in a queue removes the element at the front?

Accepted Answer

Dequeue — The dequeue operation removes the element at the front of the queue, following the FIFO principle.

Question 11

In a queue, what does the 'peek' operation do?

Accepted Answer

Returns the element at the front without removing it — The peek operation returns the front element of the queue without removing it, allowing inspection of the next element to be dequeued.

Question 12

Which of the following operations is NOT typically associated with a queue?

Accepted Answer

InsertFront — InsertFront is an operation associated with Deque, not a standard queue. Queues only allow insertion at the rear.

Question 13

Which of the following best defines a Deque?

Accepted Answer

A double-ended queue allowing insertion and deletion at both ends — A Deque (Double-Ended Queue) allows insertion and deletion at both the front and rear ends, supporting both stack and queue operations.

Question 14

Which of the following operations is used to insert an element at the front of a deque?

Accepted Answer

InsertFront — InsertFront is the operation used to insert an element at the front end of a deque.

Question 15

Which operation removes an element from the rear end of a deque?

Accepted Answer

DeletionRear — DeletionRear removes an element from the rear end of a deque.

Queue

Queue — Study Notes

4.1 INTRODUCTION TO QUEUE

4.1.1 First In First Out (FIFO)

4.1.2 Applications of Queue

Practice Questions — Queue

All 13 Chapters in Computer Science