ITPEC FE Morning April 2020 Question 6

Queue (FIFO) operations — trace ENQ/DEQ operations on a queue.

Given operations on an empty queue:
ENQ 1, ENQ 2, ENQ 3, DEQ, ENQ 4, ENQ 5, DEQ, ENQ 6, DEQ, DEQ

Step-by-step trace:

• •After ENQ 1, ENQ 2, ENQ 3 → [1, 2, 3]
• •DEQ → removes 1 → [2, 3]
• •ENQ 4, ENQ 5 → [2, 3, 4, 5]
• •DEQ → removes 2 → [3, 4, 5]
• •ENQ 6 → [3, 4, 5, 6]
• •DEQ, DEQ → removes 3, then 4 → [5, 6]

Next DEQ removes 5.

Why not others:
- (a) 1 — already removed in the first DEQ
- (b) 2 — already removed in the second DEQ
- (d) 6 — is at the tail, not the head

Key rule: Queue = FIFO. ENQ adds to tail, DEQ removes from head. Trace each operation sequentially.

AI-generated — may contain errors