Stacks

Stacks are known as last in first out data structure (LIFO). In this the last item pushed on the stack is the first item popped from the stack. In stack the insertion and deletion can be taken placed at one only end called stack’s top. A stack is a non-primitive linear data structure in which the insertion and the deletion of the elements take place from only one end, known as the top.

The fundamental operations that can be performed on stack are push and pop. Push operation causes a value to be stored in (pushed onto) the stack; whereas, Pop retrieves and removes a value from the stack. PUSH is an operation used to add a new element in to a stack. When implementing the push operation, overflow condition of a stack is to be checked. Insert a new data item on the TOP. TOP is set to a newly added item.

Pop is an operation used to remove an element from the TOP of the stack. When implementing the pop operation, underflow condition of a stack is to be checked. Stack can be implemented in two ways As an Array and as a Linked List.

To Access the full content, Please Purchase

  • Q1

    Evaluate the given postfix expression, showing the stack at every stage.

    20 10 + 12 10 - * 4 1 - 3 ^ +

    Marks:2
    Answer:

    Stages are:-

    Element

    Operation

    Stack

    1

    20

    push

    20

    2

    10

    push

    20 10

    3

    +

    pop

    pop

    perform 20 + 10

    push result

    30

    4

    12

    push

    30 12

    5

    10

    push

    30 12 10

    6

    -

    pop

    pop

    perform 12 - 10

    push result

    30 2

    7

    *

    pop

    pop

    perform 30 * 2

    push result

    60

    8

    4

    push

    60 4

    9

    1

    push

    60 4 1

    10

    -

    pop

    pop

    perform 4 - 1

    push result

    60 3

    11

    3

    push

    60 3 3

    12

    ^

    pop

    pop

    perform 3 ^ 3

    push result

    60 27

    13

    +

    pop

    pop

    perform 60 + 27

    push result

    87


    Result - 87

    View Answer
  • Q2

    Evaluate the given postfix expression, showing the stack at every stage.

    15 3 + 4 * 6 7 5 - / -

    Marks:2
    Answer:

    Stages are:-

    Element

    Operation

    Stack

    1

    15

    push

    15

    2

    3

    push

    15 3

    3

    +

    pop

    pop

    perform 15 + 3

    push result

    18

    4

    4

    push

    18 4

    5

    *

    pop

    pop

    perform 18 * 4

    push result

    72

    6

    6

    push

    72 6

    7

    7

    push

    72 6 7

    8

    5

    push

    72 6 7 5

    9

    -

    pop

    pop

    perform 7 - 5

    push result

    72 6 2

    10

    /

    pop

    pop

    perform 6 / 2

    push result

    72 3

    11

    -

    pop

    pop

    perform 72 - 3

    push result

    69

    Result = 69

    View Answer
  • Q3

    Convert the given infix expression to postfix, showing the stack at every stage.

    (true AND false) OR NOT(false OR True)

    Marks:2
    Answer:

    : Input expression : (true AND false) OR NOT(false OR True)

    Element

    Stack

    Expression Y in Postfix

    1

    (

    2

    (

    ((

    3

    true

    ((

    true

    4

    AND

    ((AND

    true

    5

    false

    ((AND

    true false

    6

    )

    (

    true false AND

    7

    OR

    (OR

    true false AND

    8

    NOT

    ( OR NOT

    true false AND

    9

    (

    (OR NOT (

    true false AND

    10

    false

    (OR NOT(

    true false AND false

    11

    OR

    (OR NOT(OR

    true false AND false

    12

    true

    (OR NOT(OR

    true false AND false true

    13

    )

    (OR NOT

    true false AND false true OR

    14

    )

    true false AND false true OR NOT OR


    The Postfix expression is : true false AND false true OR NOT OR

    View Answer
  • Q4

    Convert the given infix expression to postfix, showing the stack at every stage.

    A * ( B + C ) / E – F – (D + G) / H

    Marks:3
    Answer:

    Input expression : A * ( B + C ) / E – F – (D + G) / H

    Element

    Stack

    Expression Y in Postfix

    1

    A

    (

    A

    2

    *

    (*

    A

    3

    (

    (*(

    A

    4

    B

    (*(

    AB

    5

    +

    (*(+

    AB

    6

    C

    (*(+

    ABC

    7

    )

    (*

    ABC+

    8

    /

    (/

    ABC+*

    9

    E

    (/

    ABC+*E

    10

    -

    (-

    ABC+*E/

    11

    F

    (-

    ABC+*E/F

    12

    -

    (-

    ABC+*E/F-

    13

    (

    (-(

    ABC+*E/F-

    14

    D

    (-(

    ABC+*E/F-D

    15

    +

    (-(+

    ABC+*E/F-D

    16

    G

    (-(+

    ABC+*E/F-DG

    17

    )

    (-

    ABC+*E/F-DG+

    18

    /

    (-/

    ABC+*E/F-DG+

    19

    H

    (-/

    ABC+*E/F-DG+H

    20

    )

    ABC+*E/F-DG+H/-


    The Postfix expression is : ABC+*E/F-DG+H/-

    View Answer
  • Q5

    What is ‘Polish String’ ? Give examples and describe its forms.

    Marks:4
    Answer:

    Polish string is a notation in which the operator is placed before or after the two operands it is working on. There are no brackets or parenthesis in his form. Prefix is the form in which operator is placed before the operands. Postfix is the form in which operator is placed after the operands.

    Expression in Infix form

    Expression in Prefix form

    Expression in Postfix form

    A + B

    + A B

    A B +

    (A – B) * C

    *- A B C

    A B - C *

    (A – B) / (C – D)

    / - A B - C D

    A B - C D - /

    View Answer