search
Log In
38 votes
11.7k views

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

  1. A queue cannot be implemented using this stack.
  2. A queue can be implemented where $ENQUEUE$ takes a single instruction and $DEQUEUE$ takes a sequence of two instructions.
  3. A queue can be implemented where $ENQUEUE$ takes a sequence of three instructions and $DEQUEUE$ takes a single instruction.
  4. A queue can be implemented where both $ENQUEUE$ and $DEQUEUE$ take a single instruction each.
in DS
edited by
11.7k views
1
2

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

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

8 Answers

60 votes
 
Best answer

(C) is the answer. While $ENQUEUE$ we $REVERSE$ the stack, $PUSH$ the element and then again $REVERSE$ the stack. For $DEQUE$ we simply $POP$ the element.

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


edited by
0
sir,if we would dequeue,we must dequeue from last not first...but as it is stack how dequeue takes only one operation...i mean to say if it does pop it would from first as in case of stack FIFO but queue follows LIFO,!!!!please help me out arjun sir!!!
10
In C option while adding element we put it at the bottom of the stack, so the top of the stack is actually the first inserted element. So, a simple POP is doing a FIFO here.

Queue - FIFO

Stack - FILO or LIFO
0
Sir for B u said "next pop wont work" . Shouldn't it be "next push wont work" ? As we reverse the stack we can get items in the order they were inserted but once the stack has been reversed , We cannot the maintain the same order for enque as for queue. Please correct if i am wrong.
0
@Arjun sir..plzz elaborate this solution that what happend when reverese of stack n the push n then again reverse..its not clear to me,
0
or anybody else here plzz explain it
0
@Aman, Neha clear now? The  sentence was not complete earlier..
1
@Arjun sir..yes sir
1
yes..
1
ohh .. cleared.. thnks sir
1
@arjun sir

tell what should b do in exam when such type of question will come ?
0
Sir, it can be either way as well. 1 instruction for enqueue, three instructions for dequeue.
0
can anyone explain it nicely with an examle..m unable to understand...what is happening here??
0
For the option B... How it is taking 3 instructions..
Step1:reverse
Step2:pop
Then for next pop
We can simply perform pop operation.. We are we again reversing ??
1
Similarly can we say that Deque can be done in 3 instruction while enque in one instruction.
0

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

0

@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)  

 

 

43 votes

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

1
Good Explanation
0

https://gateoverflow.in/684/gate2000-13...in this question said ENQUEUE take single operation..?

0
To DEQUEUE an item , can we first Reverse the stack and then POP it takes 2 operations. is it correct?
0
Thanks for the explanation.It really helps me to clear my concept.
0
GOOD EXP
0
Thanks...
0
Nice Explanation.
0
These type of questions needs diagrammatically explanation, very nicely done. @rishu_darkshadow
26 votes
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.
0
so whats the answer?? c or D i think one of the function will take 3 operation and other one will take one operation.
2
ANswer is C. I gave other implementation just for more info. See that I've written in my answer as ANSWER is C.
1
can anyone explain it diagrammatically???
0
2nd image Caption
0
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
5 votes

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 


edited by
0
@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.
2
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
2 votes
To DEQUEUE an item, simply POP. To ENQUEUE an item, we can do following 3 operations 1) REVERSE 2) PUSH 3) REVERSE
0
Please someone explain diagrammatically why option B is wrong
1 vote

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)

1 vote
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.
–4 votes
D....
0
how?
0

@Arjun sir

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

Answer:

Related questions

15 votes
3 answers
1
2.4k views
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is: $10, 8, 7, 3, 2, 1, 5$ $10, 8, 7, 2, 3, 1, 5$ $10, 8, 7, 1, 2, 3, 5$ $10, 8, 7, 5, 3, 2, 1$
asked Sep 28, 2014 in DS jothee 2.4k views
27 votes
3 answers
2
5.2k views
Consider the C program below #include <stdio.h> int *A, stkTop; int stkFunc (int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; case 0: if (stkTop < size ) A[stkTop++]=val; break; default: if (stkTop) return A[--stkTop]; } ... 0, 5); stkFunc (0, 10); printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0)); } The value printed by the above program is ________.
asked Feb 12, 2015 in DS jothee 5.2k views
32 votes
5 answers
3
11.2k views
The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is: $AB + CD + *F/D +E*$ $ABCD + *F/DE* ++$ $A * B + CD/F *DE ++$ $A + *BCD/F* DE ++$
asked Oct 8, 2014 in DS Kathleen 11.2k views
16 votes
5 answers
4
11.7k views
What is the minimum number of stacks of size $n$ required to implement a queue of size $n$? One Two Three Four
asked Sep 15, 2014 in DS Kathleen 11.7k views
...