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

Correct Option: C

While $\text{ENQUEUE}$ we $\text{REVERSE}$ the stack, $\text{PUSH}$ the element and then again $\text{REVERSE}$ the stack. For $\text{DEQUE}$ we simply $\text{POP}$ the element.

Option B can be used to get the first element from the stack by doing a $\text{POP}$ after $\text{REVERSE}$ for $\text{DEQUEUE}$ and $\text{PUSH}$ for $\text{ENQUEUE}$. But we have to restore the stack using $\text{REVERSE}$ (otherwise next $\text{POP}$ won't work) which means $\text{DEQUEUE}$ actually needs $3$ instructions and not $2$.

Comments

Similarly can we say that Deque can be done in 3 instruction while enque in one instruction.

---

Arjun Ideal answer for this question should be 2 operations for Enqueue (Reverse+Push) and 2 operations for Dequeue(Reverse+Pop). It will work for all the cases

---

@shetu_raj It will not work ...consider 

Enqueue 1      stack      1

Enqueue 2      stack      2  1 

Enqueue 3       stack     3 1  2   ( reverse  then push)

Dequeue       gives you 2.  (reverse+pop)  

 

 

Answer 2

suppose queue is: 

1

2

3

4

5

  stack representation will be:             

5

4

3

2

1

Reverse the stack

STACK

1

2

3

4

5

Now, To DEQUEUE an item, simply POP. For eg. If we want to delete 1 from queue then we simply pop the top element of stack, which is 1.

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

For eg. If we want to add 6 in queue then first we reverse the stack

5

4

3

2

1

Push 6

6

5

4

3

2

1

And then again reverse the stack

1

2

3

4

5

6

hence ans : C

Comments

These type of questions needs diagrammatically explanation, very nicely done. @rishu_darkshadow

---

in enque operation step 1 is written reverse,

but the answer is showing the same stack

5

4

3

2

1

---

We have done 2 operations to Dequeue first is we REVERSED the stack and then we did POP, so haven’t we done sequence of 2 operations? I am confused here please someone clarify.

Answer 3

ENQUEUE -> REVERSE the stack, PUSH the element and then again REVERSE the stack.

For DEQUEUE we simply POP the element.

So answer is C.

Additional Information->

We can also implement queue can be implemented where DEQUEUE takes a sequence of three instructions and ENQUEUE takes a single instruction.

While Doing ENQUEUE  we just PUSH.while doing DEQUEUE  we first REVERSE, Then POP, Then again REVERSE.

Comments

I guess, the part additional information is what comes to mind first....I dont understand why Enqueue would take 3 instruction at all. If  Queue has 1,2,3,4,5 elements....then stack will contain elements also in the order $,1,2,3,4,5 <- top of stack

Hence Enqueue would take one 1 PUSH operation

Please someone clarify

---

@pgoldar

Stack will not contain the order 1,2,3,4,5(bottom to top) here we have to think that how can we perform the ENQUEUE using 3 operations (because in question they are asking how can we implement a queue, for this there are different ways)   at the time of ENQUEUE what we can do is just reverse the stack(empty) and then push the element into it and then again reverse the stack so total 3 operations required for this and as per your example (i.e 1,2,3,4,5)  after the ENQUEUE operation the order will as 5,4,3,2,1(bottom to top) so that for DEQUEUE only one pop operation is required .

so that’s why for ENQUEUE → 3 operations and for DEQUEUE → 1 operations required !!

hope it helps!

---

here for the very first ENQUEUE operation when we do first REVERSE then stack will be empty so nothing will happen, then we will do PUSH then we will push the elements and then we will do REVERSE then stack will be in reverse order, Am I thinking correct for the very first enqueue operation?

Answer 4

Consider a Stack element {1,2,3,4,5} given by below==>>

5

4

3

2

1

To Implement Queue using Stack we have three operation given as ===>

Operation 1.Reversing it we get====>>

STACK

1

2

3

4

5

Operation 2 Followed by Poping===>>

{1,2,3,4,5}

Operation 3 Followed by Enqueing===>>>

1

2

3

4

5

From the Above Diagram we can conclude that C) is true 

Comments

@sourav. So the steps for enqueue are reverse the stack, pop then reverse again, as you say.

But in Arjun sir's answer, we have reverse,push(and not pop) then reverse.

Could you please clarify the ambiguity.

---

its reverse push reverse, take small example for this. if you pop then you have to do two push , since one for you pop and one for new element