The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.1k views

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

  1. 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.
  2. 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
asked in DS by Veteran (59.6k points)
edited by | 1.1k views
0

1 Answer

+23 votes
Best answer
  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$

answered by Boss (31.8k points)
edited by
0
Content of stack at end of evaluation should be empty?
0
for dequeue it should be reverse and pop are sufficient.
+2

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

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,415 questions
48,473 answers
154,474 comments
62,887 users