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

To DEQUEUE an item, simply POP. To ENQUEUE an item, we can do following 3 operations 1) REVERSE 2) PUSH 3) REVERSE

Comments

Please someone explain diagrammatically why option B is wrong

Answer 2

Answer is C. Though we can also implement queue by single operation of ENQUEUE and DEQUEUE using a sequence of 3 operations . ENQUEUE using simple PUSH operation and DEQUEUE(REV,POP,REV)

Answer 3

Option A is not right bcs we can implement a Queue and we will see how.

Option D is not feasible, as implementing a queue with one stack is a lot of work and cannot be done with a single operation.

Option B is tempting but think about it, suppose you have "1" in stack, now you push "2", so your queue is [1[2[... now you want to dequeue so you reverse the stack and pop 1 and then again reverse the stack, these are three operations, not two.

While Option C is right, see this - say you have "1", you still reverse the whole stack as mandatory procedure then push "2" then you reverse the whole stack again, so now you have [2[1... now you pop 1 in a single operation and that's a perfect queue. To insert another number, you again reverse it then push the number then again reverse it.

Three operations to insert, one to delete.

Option C is the right one.

Answer 4

 

FOR ENQUEUE: 3 OPERATIONS (REVERSE,PUSH ,REVERSE) 

Suppose the Order of queue operations is,

Enqueue(3,4,5),Dequeue(),Enqueue(6)

ENQUEUE USING STACK:

3

Then from 2nd Enqueue : Do reverse,PUSH,reverse

1. Reverse→ Stack will be as it is
2. Push  

   4

   3

    

3. Reverse

   3

   4

So this is how a Single Enqueue operation would be.

Continue same for all enqueues till Enqueue(5)

Now for DEQUEUE: 1 OPERATION POP

As FIFO order should be followed Our Queue Automatically follows it by Enqueue operation.

So for Dequeue Simply do POP only and 3 will be popped off.

Continue Popping for all Dequeues

SO FOR ENQUEUE 3 OPERATIONS(REVERSE,PUSH,REVERSE) AND FOR DEQUEUE 1 OPERATION(POP)