**UNIT 3 STACK**

** 2,4, & 8 MARK QUESTIONS**

**1) Define stack. (Definition-2Marks)**

**Ans:**A stack is linear data structure or orderly collection of data in which data may be inserted or deleted from one end called “top of stack” for this reason stack is referred as LIFO( Last in First Out).

**2) State applications of stack.(Any 2 Applications – 1 Mark each)**

**OR**

**2) Write any two application of stack.(Any 2 application: 1 MARKS each)**

**Ans:**Following are the applications of stack

Recursion

Reversing String

Interrupt handling

Expression conversion & evaluation: Polish Notation

Stack machine

Matching parenthesis in an expression

**3) Explain stack as an abstract data type. (4 Marks) (Any representation of an ADT containing elements and operation shall be considered)**

**Ans:**Stack as an abstract data type contains stack elements and its operations.

**Stack elements:** a list, stack top

**Stack operations:**

Initialize stack to be empty

Checking whether stack is empty or not

Checking if stack is full or not

If stack is not full, then insert a new element.

This operation is called as push.

If stack in not empty, then retrieve element from stack top.

If stack in not empty, then remove an element from stack top.

This operation is called as pop.

**4) Explain stack as an abstract data type. (Any representation of an ADT containing elements and operation shall be considered -4Marks)**

**Ans:Stack As An Abstract Data Type:
**Representation of stack as an abstract data type is very straightforward.

We use eltype to denote type of stack element & parameterize stack type with eltype

abstract typedef <<eltype>> stack (eltype).

C implementation of stack: A stack , s of integer data type can be

defined as: int s[10]; int top =-1;

Where s is an array of integer type which can hold integer values & top is variable used to hold top position of list.

Formally stack may be defined as follows:

typedef struct stack

{

int data [size];

int top;

}stack;

size is constant, maximum number of elements that can be stored

**5) Describe primitive operations on stack. (Any four operation 1 mark each)**

**Ans:**

**Basic operations of stack are:**

**1) CREATE stack():**To initialize stack as an empty stack.

**2) PUSH:**

The process of adding new element to the top of the stack is called

PUSH operation.

As the new element is added to the top, after every push operation

the top is incremented by one.

**3) POP:**

The process of deleting an element from top of the stack is called

POP operation.

As deletion takes place from the top of the stack.

After every POP operation the top of the stack is decremented by one.

**4) Retrieval & Display:** Reading elements from stack and display them.

**6) What is the Affect of PUSH and POP operation on to the stack? The stack contain 10,20, 22, 26, 28, 30 with 30 being at top of the stack. Show diagrammatically the effect of ( 1mark each explanation of push and pop. 6 marks for diagram of affect of operation)**

**PUSH 46**

**PUSH 48**

**POP**

**POP**

**POP**

**PUSH 82**

**Ans:**

**1) PUSH:**

The process of adding new element to the top of the stack is called PUSH operation. As the new element is added to the top, after every push operation the top is incremented by one.

**2) POP:**

The process of deleting an element from top of the stack is called POP operation. As deletion takes place from the from top of the stack. After every POP operation the top of the stack is decremented by one.

**7) Explain the concept of representing stack through arrays. Explain the concept of PUSH, POP and TOP of stack with example. (2marks for stack representation, PUSH-2MARKS, POP 2 MARKS, TOP 2 MARKS) (Diagram required))**

**Ans:**

Stack is ordered collection of items.

In it item inserted from one end of stack known as top of stack.

In stack item deleted from top of stack.+

Elements of stack accessed only through TOP of stack.

**Push :** Push operation is used to insert an element into the stack.

Initially stack top is set to -1 as array started with 0 to indicate empty stack. When element is to be inserted first increment the stack top by 1 and then

insert two new elements into it.

**Algorithm for push operation (Steps)**

Step 1: First check for overflow i.e. if stack top =max-1

(maximum size of an array) then push operation cannot be performed.

Step 2: If there is no overflow then increment the stack top by 1 and insert new element at stack top position.

Pop operation is used to remove an element from stack .

An element at the stack top is removed then pop operation is called.

When pop operation is called stack top is decremented by 1.

**Algorithm for pop operation(Steps)**

Step 1: First check for underflow i.e. if stacktop is -1 means there is no element in

the stack then pop operation cannot be performed.

Step 2: If there is no underflow then decrement the stacktop by 1.

It removes an element placed at stacktop of the stack.

**8) Explain the term ‘overflow’ and ‘underflow’ with respect to stack use suitable data and diagram. (Explanation overflow and underflow -2 M,Diagram of each-1M)**

**Ans:**A stack cannot grow indefinitely, because there is always a limit to memory.

**Overflow:** When the stack is completely full and then a PUSH operation is performed onto the stack then a ‘stack overflow’ occurs.

**Example:**

let us assume that 5 items 30, 20, 25, 10 and 40 are to be placed on the stack. The items can be inserted one by one as shown in following figure.

After inserting 40 the stack is full. In this situation, if push operation is called then stack overflow occurs.

**Underflow:** If the stack is completely empty and a POP operation is called, then ‘stack underflow’ occurs.

**Example:** When an item is to be deleted, it should be deleted from the top as shown in the following figure.

The items deleted in order are 40, 10, 25, 20 and 30. Finally, when all items are

deleted then TOP points to bottom of stack.

When the stack is empty, if POP operation is called stack underflow occurs.

**9) Explain push and POP operation on stack with algorithm and example.(Push Algorithm 2 M, Example 2 Marks, POP Algorithm 2 Marks, Example 2 Marks)**

**OR**

**9) Explain PUSH and POP operation on stack using Array representation.(Push & POP operation with array representation -2 Marks each)**

**Ans:**

**PUSH:** Push operation is used to insert an element in stack.

Initially stack top is set to -1.i.e stack is empty .

When an element is to be inserted first increment the stack top by 1 and then insert new element into it.

**Algorithm**

1. If TOP = SIZE – 1, then:

(a) Display “The stack is in overflow condition”

(b) Exit

2. TOP = TOP + 1

3. STACK [TOP] = ITEM

4. Exit

**POP:** Pop operation is used to remove an element from stack.

When pop operation is called stack top is decremented by 1.

**Algorithm:-**

1. If TOP < 0, then

(a) Display “The Stack is empty”

(b) Exit

2. Else remove the Top most elements

3. DATA = STACK [TOP]
4. TOP = TOP – 1

5. Exit.

**10) Write a ‘c’ program to implement push & pop function in stack as an array. (3Marks for push function& 3 Marks for pop function, 2 Marks for main program)**

**Ans:Program on implementation of stack as an array
**#include<stdio.h>

#define max 20

typedef struct stack

{

int a[max];

int top;

}

push(stack *s, int info)

{

s->top=s->top+1;

s->a[s->top]=info;

}

int pop(stack *s)

**{**

int info;

info=s->a[s->top];

s->top–;

return(info);

}

void main( )

{

int n, choice;

stack s;

clrscr( );

do

{

**printf(“\n 1 for PUSH\n 2 for POP\n 3 for EXIT”);**

printf(“Enter your choice”);

scanf(“%d”, &choice);

switch(choice)

{

case 1: if(s->top==max-1)

printf(“Stack is full”);

else

{

printf(“Enter the element to be pushed”);

scanf(“%d”,&n);

push(&s,n);

}

break;

case 2 : if(s->top== -1)

printf(“Stack is empty”);

**else**

{

printf(“ The popped element is %d”, pop(&s));

break;

}

}while(choice!=3);

getch( );

}

**11) Convert the given infix expression to postfix expression using stack and the details of stack at each step of conversion**

**Expression: a↑ b*c-d+e/f/ (g+h)**

**Note: ↑ indicates exponent operator.**

**(Correct Postfix Expression -8 Marks; Stepwise solution shall be consider)**

**2) Convert the following infix expression to its postfix form (2 marks each)**

**i) A+B-C*D/E+F**

Sr.No. | Symbol scanned | Stack | Expression |
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 |

ii)A*B-C^D+E/F

Sr.No. | Symbol scanned | Stack | Expression |
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 |

**12) Find out infix equivalent of the following postfix expression.**

**(i) AB + C * D –**

**(ii) ABC * + D – (For each correct infix expression – 2 Marks)**

**Ans:**

**(i) ((A+B)*C) – D**

Sr.No. | Symbol scanned | Stack | Expression |
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 |

(ii) A+(B*C)–D

Sr.No. | Symbol scanned | Stack | Expression |
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 |

**13) Covert the following infix expression into a postfix expression and show details of stack at each step of conversion.(Correct postfix expressions – 2 Marks, For steps – 6 Marks)**

**Expression: ((A+B)*D) ^(E – F)**

**Ans:**

**Assignment on Infix to Postfix**

**NOTE:**

**INSERT BRACKET FIRST AND EVALUATE FROM LEFT SIDE FOR INFIX TO POSTFIX**

**1) Q= (A+B)*C-D/E*(F/G)**

**2) (A*B+C/D)*(E+F^G)**

**3) ((A-Z)*B+C)/D*E)+F**

**4) A-(B/C+(D%E*F)/G)*H**

**5) (A+B)/(C-D)-(D*E)**

**6) (A+(B*C))/(C-(D*B))**

**14) Convert the given string to prefix expression and shows the details of stack at each step. (A-B/C) * (D*E-F)(8 Mark for correct prefix string)**

**Ans:**

Sr.No. | Symbol scanned | Stack | Expression |
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 | |||

17 | |||

18 | |||

19 | |||

20 | |||

**Assignment on Infix to Postfix**

**NOTE:**

**INSERT BRACKET FIRST AND EVALUATE FROM RIGHT SIDE FOR INFIX TO PREFIX**

**1) ((A+B)*(C-D))**

**2) A$B*C-D+E/F/(G+G)**

**3) (A+(B*C))/(C-(D*B))**

**15) Convert the following arithmetic expression P written in postfix notation into infix. P: 5, 6, 2, +, *, 12, 4, /, – also evaluate P for final value.(Each 2step carries-1M)**

**Ans:**

Postfix to infix form:

Postfix expression (P): 5, 6, 2, +,*, 12, 4, /,-

Step 1: Grouping of tokens as per the sequence of evaluation.

Step 2: Operators are moved between the two operands of the group

5*(6+2)-12/4

**16)Evaluate the given postfix expression to find its value.**

**( Every 4 correct step carries 1 mark)**

**( 6 , 2 , 3 , +, – ,3 , 8 , 2 , + , + , 2 , ↑ , 3 , + , * )**

**Ans:**

Sr.no | Value | Stack | Opnd1 | Opnd2 | Result |
---|---|---|---|---|---|

1) | 6 | – | – | – | – |

2) | 2 | 6,2 | – | – | – |

3) | 3 | 6,2,3 | – | – | – |

4) | + | 6,5 | 2 | 3 | 5 |

5) | – | 1 | 6 | 5 | 1 |

6) | 3 | 1,3 | – | – | – |

7) | 8 | 1,3,8 | – | – | – |

8) | 2 | 1,3,8,2 | – | – | – |

9) | + | 1,3,10 | 8 | 2 | 10 |

10) | + | 1,13 | 3 | 10 | 13 |

11) | 2 | 1,13,2 | – | – | – |

12) | ↑ | 1,169 | 13 | 2 | 169 |

13) | 3 | 1,169,3 | – | – | – |

14) | + | 1,172 | 169 | 3 | 172 |

15) | * | 172 |
172 | 1 | 172 |

**17)Evaluate the given postfix expressions to find its value.**

**A) 5,6,2,+,*,12,4,/,-**

Sr.no | Value | Stack | Opnd1 | Opnd2 | Result |
---|---|---|---|---|---|

1) | 5 | ||||

2) | 6 | ||||

3) | 2 | ||||

4) | + | ||||

5) | * | ||||

6) | 12 | ||||

7) | 4 | ||||

8) | / | ||||

9) | – | ||||

10) |

**B) 12,7,3,-,1,2,1,5,+,*,+**

Sr.no | Value | Stack | Opnd1 | Opnd2 | Result |
---|---|---|---|---|---|

1) | 12 | ||||

2) | 7 | ||||

3) | 3 | ||||

4) | – | ||||

5) | 1 | ||||

6) | 2 | ||||

7) | 1 | ||||

8) | 5 | ||||

9) | + | ||||

10) | * | ||||

11) | + | ||||

12) |

**C) 4,2,^,3,*,3,-,8,4,/,1,1,+,/,+**

Sr.no | Value | Stack | Opnd1 | Opnd2 | Result |
---|---|---|---|---|---|

1) | 4 | ||||

2) | 2 | ||||

3) | ^ | ||||

4) | 3 | ||||

5) | * | ||||

6) | 3 | ||||

7) | – | ||||

8) | 8 | ||||

9) | 4 | ||||

10) | / | ||||

11) | 1 | ||||

12) | 1 | ||||

13) | + | ||||

14) | / | ||||

15) | + |