edited by
6,194 views
27 votes
27 votes

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

2 Answers

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

edited by

Related questions

48 votes
48 votes
4 answers
1
Kathleen asked Sep 14, 2014
17,496 views
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the foll...