GATE CSE 2014 Set 2 | Question: 41

Question

Suppose a stack implementation supports an instruction $\text{REVERSE}$, which reverses the order of elements on the stack, in addition to the $\text{PUSH}$ and $\text{POP}$ instructions. Which one of the following statements is $\text{TRUE}$ (with respect to this modified stack)?

• A. A queue cannot be implemented using this stack.
• B. A queue can be implemented where $\text{ENQUEUE}$ takes a single instruction and $\text{DEQUEUE}$ takes a sequence of two instructions.
• C. A queue can be implemented where $\text{ENQUEUE}$ takes a sequence of three instructions and $\text{DEQUEUE}$ takes a single instruction.
• D. A queue can be implemented where both $\text{ENQUEUE}$ and $\text{DEQUEUE}$ take a single instruction each.

Comments

Similar --> https://gateoverflow.in/684/gate2000-13

---

We can implement the queue operations in either of these two ways:-

1. Reverse, push, reverse; and pop.
2. Reverse, pop, reverse; and push.

---

  In all the implementation total of 4 instructions needed 2 reverse, 1 push, 1 pop. 

1. For push operation simply push. for pop: reverse → pop → reverse.

For pop operation simply pop. for push: reverse → push → reverse.

---

to the people’s who are getting (b) as answer,

(B) this option is correct if they given 2 opn for enque and 2 opn for deque,

(C) this is correct you can try this for enque: 3 opn are( REVERSE, ENQUE, REVERSE)

Answer 1

D....

Comments

how?

---

@Arjun sir

If the REVERSE instruction is given, so we can implement Queue using only one stack??