ITPEC FE Morning October 2021 Question 7

Stack and Queue operations — trace push/pop/enq/deq to find the final value.

Queue (FIFO): enq(x) adds to rear, deq() removes from front.
Stack (LIFO): push(x) adds to top, pop() removes from top.

Step-by-step trace:

• •enq(1) → Queue: [1]
• •enq(2) → Queue: [1, 2]
• •push(3) → Stack: [3]
• •push(deq()) → deq() returns 1 → Stack: [3, 1], Queue: [2]
• •enq(4) → Queue: [2, 4]
• •push(deq()) → deq() returns 2 → Stack: [3, 1, 2], Queue: [4]
• •y ← pop() → returns top of stack → y = 2

Why not others:
- (a) 1 — 1 was pushed onto the stack but is not on top at the end
- (c) 3 — 3 is at the bottom of the stack
- (d) 4 — 4 is in the queue, never pushed onto the stack

Key rule: Always trace both structures separately. deq() takes from the front of the queue (FIFO), pop() takes from the top of the stack (LIFO).

AI-generated — may contain errors