ITPEC FE Morning April 2023 Question 8

Topic: Algorithm and ProgrammingAlso asked in Spring 2020

The operations for a queue are defined as below.

ENQ n:This operation appends data n to the queue.DEQ:This operation removes data from the queue.

On an empty queue, the operations ENQ 1, ENQ 2, ENQ 3, DEQ, ENQ 4, ENQ 5, DEQ, ENQ 6, DEQ, DEQ are performed. After that, when DEQ is performed, what is the value that is removed?

Explanation

5 — a queue is first in, first out, so values leave in the order they were added.

Trace, with the front of the queue on the left:

OperationRemovedQueue after
ENQ 1, ENQ 2, ENQ 3none1, 2, 3
DEQ12, 3
ENQ 4, ENQ 5none2, 3, 4, 5
DEQ23, 4, 5
ENQ 6none3, 4, 5, 6
DEQ, DEQ3, 45, 6
DEQ56

Shortcut: the last operation is the fifth DEQ, and the fifth value enqueued is 5.

Answer (c)

Why not others:

  • •(a) 1 — the value removed by the first DEQ, long before this one
  • •(b) 2 — what a stack (last in, first out) would give: its pops remove 3, 5, 6 and 4, leaving 1 and 2, so the next pop returns 2
  • •(d) 6 — the value added last; it comes out only on the DEQ after this one

Key rule: In a queue the k-th DEQ always returns the k-th value enqueued, however the operations are interleaved.

Algorithm and Programming · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.