GATE CSE 2000 | Question: 13

Question

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack.

• A. To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of $3$ operations.
• B. The following post fix expression, containing single digit operands and arithmetic operators $+$ and $*$, is evaluated using a stack. 
  $5 \ 2 * 3 \ 4 + 5 \ 2 * * +$
  Show the contents of the stack
  1. After evaluating $5 \ 2 * 3 \ 4 +$
  2. After evaluating $5 \ 2 * 3 \ 4 + 5 \ 2$
  3. At the end of evaluation

Comments

Similar --> https://gateoverflow.in/2007/gate2014-2-41

Answer 1

1. For enqueue push operation is sufficient
   For dequeue operation do the following
   -reverse, pop, reverse
    
2. Contents of stack from top to bottom:

          i) $7 \ 10$
         ii) $2 \ 5 \ 7 \ 10$
         ii) $80$

Comments

@once_2019

For dequeue reverse and pop are not sufficient because we might have popped only one element and would need to push later on. If we don't restore the order the the elements will be jumbled.

---

@Mizuki....can you explain with this example..please

For dequeue operation do the following 
-reverse, pop, reverse 

---

@ VIDYADHAR SHELKE 1    Consider that the stack initially contains the elements 1,2,3,4 from bottom to top (i.e 4 is at the top)

Consider 2 operations to be performed

1) Dequeue

2) Enqueue(5)

For 1)

We'll have to first reverse the stack. So stack contents 4,3,2,1 from bottom to top.

Next,we'll pop the element. So stack contents 4,3,2.

Now we'll have to reverse the elements,since we want to enqueue in 1 operation(if we dont reverse then 5 will be pushed after 2,but it should be pushed after 4). So stack contents 2,3,4.

Now Enqueue(5) . So stack contents 2,3,4,5 from bottom to top.

Hence, total Dequeue operations =3 and Enqueue operations = 1.

Answer 2

final answer should be 80.