ITPEC FE Morning April 2019 Question 6

Topic: Algorithm and Programming

When the procedure described below is executed in sequence for an empty stack and empty queue, what is the value assigned to variable x? Here, the functions used in the procedure are defined as follows:

[Function definitions] push(y):pushes data y onto the top of the stack. pop():removes the data from the top of the stack and returns it as the function value. enq(y):inserts data y at the tail of the queue. deq():removes the data from the head of the queue and returns it as the function value.

[Procedure]

  push(a)

  push(b)

  enq(pop())

  enq(c)

  push(d)

  push(deq())

  x ← pop()

Explanation

b — trace the stack (last in, first out) and the queue (first in, first out) side by side.

  • •push(a), push(b): stack a, b (top b)
  • •enq(pop()): pop takes b; stack a; queue b
  • •enq(c): queue b, c (head b)
  • •push(d): stack a, d
  • •push(deq()): deq takes b from the head; stack a, d, b; queue c
  • •x ← pop(): the top of the stack is b

Answer (b)

Why not others:

  • •(a) — treats the stack as first in, first out: the first pop would return a, which then travels through the queue back onto the top of the stack
  • •(c) — treats the queue as last in, first out: deq would return c, the most recently inserted item, instead of b at the head
  • •(d) — d is the top only before push(deq()) puts b above it

Key rule: When data moves between a stack and a queue, keep both states written down after every step; pop takes the newest item and deq takes the oldest.

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.