Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of ...

Question

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of elements on the stack.

To implement a queue using the above stack implementation:
A. ENQUEUE can be implemented as a single operation and DEQUEUE as a sequence of 3 operations.
B. The following postfix expression containing single digit operands and arithmetic operators + and * is evaluated:
   5 2 * 3 4 * 5 2 + -
   Show the contents of the stack after evaluating: 5 2 *

Which of the following correctly describes how ENQUEUE and DEQUEUE are implemented using this stack with REVERSE?
A. ENQUEUE = PUSH; DEQUEUE = REVERSE, POP, REVERSE
B. ENQUEUE = REVERSE, PUSH, REVERSE; DEQUEUE = POP
C. ENQUEUE = PUSH; DEQUEUE = POP
D. ENQUEUE = REVERSE; DEQUEUE = POP

Accepted Answer

ENQUEUE = PUSH (1 operation); DEQUEUE = REVERSE, POP, REVERSE (3 operations). Answer: A. A queue is FIFO (First In First Out) while a stack is LIFO. To simulate queue behavior with a stack and a REVERSE operation, we need to get the oldest element out first. If we PUSH all elements normally, REVERSE flips the stack so the first-pushed element is now on top, then POP gets it, and REVERSE again restores the order for remaining elements. ENQUEUE is simply a PUSH (add to top).