ITPEC FE Morning April 2020 Question 6

Topic: Algorithm and ProgrammingAlso asked in April 2023

Two operations against a queue are defined below.

ENQ n:adds a number n at the end of the queue.DEQ:removes the number at the head of the queue.

For an empty queue, a sequence of operations,

“ENQ 1, ENQ 2, ENQ 3, DEQ, ENQ 4, ENQ 5, DEQ, ENQ 6, DEQ, DEQ”,

is performed in this order. When another DEQ is performed in succession, what is the number to be removed by this operation?

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.