ITPEC FE Morning April 2019 Question 6

Stack and Queue operations — tracing push/pop/enq/deq to determine a variable's final value.

Two data structures are used simultaneously:

• •Stack (LIFO): push(y) adds to top, pop() removes from top
• •Queue (FIFO): enq(y) adds to tail, deq() removes from head

Step-by-step trace:

1. push(a) → Stack: [a]
2. push(b) → Stack: [a, b]
3. enq(pop()) → pop() returns b; enq(b) → Stack: [a], Queue: [b]
4. enq(c) → Queue: [b, c]
5. push(d) → Stack: [a, d]
6. push(deq()) → deq() returns b (head of queue); push(b) → Stack: [a, d, b], Queue: [c]
7. x ← pop() → pop() returns b (top of stack)

The answer is (b) b.

Why not others:
- (a) a is at the bottom of the stack, never reached by pop()
- (c) c remains in the queue and is never moved to the stack
- (d) d is in the stack but one level below b at the time of the final pop()

Key rule: When stack and queue interact, trace each structure separately — pop() always takes the most recent stack element, deq() always takes the oldest queue element.

AI-generated — may contain errors