A queue has configuration a, b, c, d from front to rear. Counting only queue…
2024
A queue has configuration a, b, c, d from front to rear. Counting only queue operations (deletions from the front and additions at the rear), what minimum is needed to get d, c, b, a?
- A.
2 deletions and 3 additions
- B.
3 deletions and 3 additions
- C.
4 deletions and 4 additions
- D.
More than one of the above
- E.
None of the above
Attempted by 767 students.
Show answer & explanation
Correct answer: B
Queue deletion happens from the front and addition happens at the rear. Here we count only queue operations; the deleted elements can be retained temporarily and reinserted as needed.
Start with a, b, c, d. To get d, c, b, a with minimum operations, keep d in the queue and move only a, b, c.
Delete a: the queue becomes b, c, d.
Delete b: the queue becomes c, d.
Delete c: the queue becomes d.
Add c: the queue becomes d, c.
Add b: the queue becomes d, c, b.
Add a: the queue becomes d, c, b, a.
Total operations are 3 deletions and 3 additions. Deleting all 4 elements and adding all 4 back can also reverse the queue, but it is not minimum. Therefore, option B is correct.