edited by
24,499 views
54 votes
54 votes

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

  1. A queue cannot be implemented using this stack.
  2. A queue can be implemented where $\text{ENQUEUE}$ takes a single instruction and $\text{DEQUEUE}$ takes a sequence of two instructions.
  3. A queue can be implemented where $\text{ENQUEUE}$ takes a sequence of three instructions and $\text{DEQUEUE}$ takes a single instruction.
  4. A queue can be implemented where both $\text{ENQUEUE}$ and $\text{DEQUEUE}$ take a single instruction each.
edited by

9 Answers

Best answer
78 votes
78 votes

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$.

edited by
61 votes
61 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

29 votes
29 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.
5 votes
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
Answer:

Related questions

21 votes
21 votes
1 answer
1
go_editor asked Sep 28, 2014
5,497 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$ ar...
25 votes
25 votes
3 answers
2
go_editor asked Sep 28, 2014
9,750 views
The number of distinct positive integral factors of $2014$ is _____________
34 votes
34 votes
3 answers
4
go_editor asked Sep 28, 2014
11,127 views
Which of the following socket API functions converts an unconnected active TCP socket into a passive socket?$\textsf{connect}$$\textsf{bind}$$\textsf{listen}$$\textsf{acc...