DS Unit 3 Notes

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.

pop


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

push
Elements of stack accessed only through TOP of stack.
Push : Push operation is used to insert an element into the stack.

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

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

stackoverflow

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.

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

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

poparray
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)

infixtoprefix
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:
infixtopostfix
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.
postfixnotation
Step 2: Operators are moved between the two operands of the group
5*(6+2)-12/4
operation

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) +

Leave a Reply

Your email address will not be published. Required fields are marked *