ITPEC FE Morning October 2021 Question 7

Topic: Algorithm and Programming

After the procedure shown below has been executed in the listed order, which value will be stored in variable y? Here, the stack and queue structures are initially empty, and the four types of operations are defined as shown below.

[Operations] push(x):Add the value of x onto the top of the stack. pop():Remove a value from the top of the stack, then return the value. enq(x):Add the value of x into the rear of the queue. deq():Remove a value from the front of the queue, then return the value.

[Procedure]

 enq(1)

 enq(2)

 push(3)

 push(deq())

 enq(4)

 push(deq())

 y ← pop()

Explanation

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

OperationQueue, front to rearStack, bottom to top
enq(1)1empty
enq(2)1, 2empty
push(3)1, 23
push(deq())23, 1
enq(4)2, 43, 1
push(deq())43, 1, 2
y ← pop()43, 1

pop() returns the top of the stack, 2.

Answer (b)

Why not others:

  • •(a) 1 — the value moved by the first push(deq()); the second transfer puts 2 on top of it
  • •(c) 3 — the value pushed first, now at the bottom; pop() would return it only if the stack worked first in, first out
  • •(d) 4 — still in the queue; it would reach the stack only if deq() took from the rear, which transfers 2 and then 4 instead of 1 and then 2

Key rule: Keep a separate picture of each structure: deq() takes the oldest item in the queue, pop() the newest item on the stack.

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.