Department of Information Technology Data Structure [ITG310]

STACK

STACK: Hello Hii

The stack is linear data structure in which items may be added or

removed only at one end.
For example, stack of dishes, stack of folded towels.
Observed that, an item may be added or removed from the top of the stack. This
means that the last element to be added to the stack is the first element to be
removed so it is calle d t out’(LIFO) list. Other names used for stacks
are PILES or PUSHDOWN LIST.
The stack is a list of element in which an element may be inserted or
deleted at one end called top of the stack. This means in particular that element
removed from the stack in reverse order in which they were inserted into a stack.
Special terminology is used for basic operation associated with stack.
A push: It is a term used to insert an element into a stack.
A pop: It is the term used to delete an element from stack.
For example, suppose the following six elements are pushed in order on to an
empty stack. AAA, BBB, CCC, DDD, EEE, FFF.
Fig shows three base of picturing stack:
FFF -top AAA

EEE BBB

DDD CCC

CCC DDD
BBB EEE
AAA FFF-
Top

1
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

AAA BBB CCC DDD EEE FFF

Top
The indigestion is that the rightmost element is the top element. The
insertion and deletion of element at only top of the stack.
This means that EEE can’t be deleted before FFF & DDD and so on.
The element may pop only in reverse order of a stack in which they were pushed
into a stack.
Array representation of a stack:
Stack may be represent in the computer by means of one way list or
linear array. Unless otherwise stated each of our stack will e maintained by a
linear array “Stack”. A pointer variable, ’Top’, which contain location of top
element of a stack. Variable, ‘MAXSTACK’, which gives the maximum
number of element that, can be held by stack.
The addition top=0 or top=NULL will indicate stack is empty.
Fig shows such an array representation of stack since top=3 .The stack has three
elements A, B, C and MAXSTACK=7. So there is a room for four elements.
1 2 3 4 5 6 7
A B C

TOP=3 MAXSTACK=7
Algorithm:-
1) Push:
Push(stack, top, Max, Maxstack, item)

Step-1
[stack already filled?]
If top=Maxstack
Then print overflow and return.

2
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Step-2
Set top=top+1
[Increase top by 1]

Step-3
Set stack[top]=item

Step-4
Return

2)Pop:

Pop(stack, top, item)

Step-1
[stack has an item to be removed?]
If top=0
Then print stack is underflow and return

Step-2
Set item=stack[top]
[Assign top element to the item]

Step-3
top=top-1;

step-4
Return.

Program: Implementation of Stack

#include<stdio.h>

int main(){

int item,top, max,arr[20],cmd,i;

top =0;

3
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

max =5;
while (1)
{
printf("\n\n****Stack****");
printf("\n Enter the option to perform
:\n\t1.push\n\t2.pop\n\t3.display\n");
scanf("%d",&cmd);

switch (cmd)
{
case 1:
if(top==max){
printf("Stack Overflow");
}
else {
top++;
printf("Enter the element to push: ");
scanf("%d",&item);
arr[top]=item;
}
break;

case 2:
if(top==0){
printf("Stack underflow");
}
else {
item = arr[top];
printf("The pop element is : %d",item);
top--;
}
break;

case 3:
printf("Stack Elements are: \n");
for(i = 1; i <= top; i++)
{
printf("%d\t",arr[i]);

4
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

}
break;

default:
printf("Enter Correct choice\n");
break;
}
}

return 0;
}
Application of stack:

Some of the uses of stack are described below:

1) Reversal of a string.
2) Checking validity of an expression containing nested parentheses.
3) Conversion of infix expression to postfix and prefix forms.
4) Evaluation of postfix and prefix forms.

Reversal of string:
We can reverse the string that pushing each character on the
stack. When the string is pushed in the stack we will pop the character of the
stack and we will gate reverse string.
/*program of reversing a string using stack*/
#include<stdio.h>
#define MAX 20
#include<string.h>
#include<conio.h>
int top=0;
Char stack[MAX];
Char pop();
push(char);
main()
{
char str[20];
int i;
printf(“enter the string: “);

5
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

gets(str);

/*push characters of the string str on the stack*/

for(i=0;i<strlen(str);i++)
{
push(str[i]);
}

/*pop characters from the stack and store in string str*/

for(i=0;i<strlen(str);i++)
str[i]=pop();
printf(“Reversed string is:”);
puts(str);
getch();
}

push(char item)
{
if(top==(MAX-1))
printf(“Stack Overflow\n”);
else
stack[++top]=item;
}/*End of push()*/

char pop()
{
if(top==0)
printf(“Stack Underflow\n”);
else

6
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

return stack[top--];
}/*end of pop()*/

Checking validity of an expression containing nested parentheses:

We can use stack to check the validity of an expression which
uses nested parentheses. An expression will be valid if it satisfies these two
conditions-
1. The total number of left parentheses should be equal to the total number
of right parentheses in the expression.
2. For every right parenthesis there should be left parenthesis of the same
type.
Some valid and invalid mathematical expressions are given below.
[19-5*(9+4) invalid
(1+5} invalid
[5+4*(9-2)] valid
{3+2-[9%2)] invalid
[2+ (4*2)-{6%4}] valid
The procedure is as-
Take a Boolean variable valid which will be true if the expression is valid and will
be false if the expression is invalid. Initially let valid is true.
1. Scan the symbols of expression from left to right.
2. If the symbol is a left parenthesis then push it on the stack.
3. If the symbol is right parenthesis
If the stack is empty
Valid=false
else
pop an element from stack
if popped parenthesis does not match the parenthesis begin scanned

7
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

valid=false.
4. After scanning all the symbols if stack is not empty then make valid=false.

Polish Notation with arithmetic expression-

In any language, arithmetic support is needed which is same as
mathematical expression. But writing data structure for understanding arithmetic
expression have so many complications, like scanning direction , operators priority
and after that how to decide the priority if an parenthesis is coming. So designing
compiler for any language has need to take care of these complications. But
support of arithmetic expression is one of basic requirement of any language. Let
us take an arithmetic expression-
a + b/3
Suppose a=9 and b=6. Suppose we are taking divide operation first then add. So
the resultant value will be-
9 + b/3
=9+2
=11
Now, suppose we are taking add operation first then divide operation. So the
resultant value will be-
9+6/3
=15/3
=5
Here we can see that priority of operation is giving different result. So it is decided
that scanning will be from left to right and each operator will have some
precedence level. Now suppose we are taking parenthesis in expression. Let us
take the same expression with parenthesis –
(a +b)/3

8
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Here first the operation will be for expression inside the parenthesis. So we have a
need to decide the priority for parenthesis. First expression inside the parenthesis
should be evaluated so its priority should be highest.
Here we will take five operators ‘+’,’-’,’*’,’/’and ‘^’ (for exponentiation) and
based on that all the expression will be given.
Level 2 ^ (Exponentiation)
Level 1 *(Multiplication) and / (Division)
Level 0 + (Addition) and - (Subtraction)

Here Level 2 is highest priority and Level 0 is the lowest. We can see ‘*’ and ‘/’
have same precedence level. We are scanning from left to right, so whichever
operator in both will come first that will be evaluated first.
Let us take an arithmetic expression-
5 + 3^2 - 2 * 6/2- 6/ (3-1)
5 + 3 ^ 2 – 2 * 6 / 2 – 6 / (3 – 1)
2 3 1
6 4 5

8
Here we can see that the expression inside the parenthesis is evaluated first and
after that evaluation is on the basis of operator precedence.
We can see each time we have a need to know the information of parenthesis and
precedence of operators for evaluating expression and every time we are traversing
to different place in expression for evaluation. So now we have a need of the
process of evaluation where parenthesis should not come and evaluation should be

9
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

based on scanning the expression from left to right and the operator which is
coming first should be evaluated with its operands.

Polish Notation-
The great polish mathematician Jan Lukasiewich came with new
technique for representation of arithmetic expression where operator will be before
or after operands called polish notation in his honour.

Now we have three ways to represent the arithmetic expression –

Infix - A+B
Prefix - +AB
Postfix- AB+
First one where operator is in between operands is called infix, second one where
operator is before operands called prefix or polish notation and third one where
operator is after operands is called postfix (suffix) or reverse polish notation. Here
we have no need of parenthesis, which will increase the efficiency in evaluation of
expression. Let us take some infix expressions and convert them in prefix and
postfix expression –
Infix – (A + B)/C*D-E
Prefix – {+AB}/C*D-E
{/+ABC}*D-E
{*/+ABCD}-E
-*/+ABCDE
Postfix - {AB+}/C*D-E
{AB+C/}*D-E
{AB+C/D*}-E
AB+C/D*E-

10
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Let us take another expression-

Infix- A + B / C – D* E+F
Prefix- A + {/BC}-{* DE} +F
{+A/BC} - {+*DEF}
-+A/BC+*DEF
Postfix- A+ {BC/}-{DE*} +F
{ABC/+} - {DE*F+}
ABC/+DE*F+-
Here we can see the prefix and postfix expression are not a mirror image of each
other. In polish notation we don’t have a need of any parenthesis and by scanning
from left to right can evaluate the expression one by one. There is no need of
traversal in expression at different place for evaluation.
So computer takes the input in infix form and converts them in postfix from then it
evaluates expression efficiently.

Converting infix expression into postfix expression-

Before converting the infix expression into postfix expression we
have a need to take some assumption. Here we are scanning from left to right and
operators involved are only ‘^’ (exponentiation), ‘+’, ‘-’, ‘*’ and ‘/’. We will be in
need to implement stack for temporary placement of operators and information of
operator is also required. For getting the information of end of arithmetic
expression, addition of one unique symbol is needed at the end.
Let us take an array infix has arithmetic expression in infix form and array postfix
will contain the arithmetic expression in postfix form. The steps involved to
convert the infix expression into postfix expression will be –

Step 1-
Add the unique symbol ‘#’into stack and at the end of array infix.

11
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Step2-
Scan the symbol of array infix one by one from left to right.
Step3-
If symbol is left parenthesis ‘(’ then add into the stack.
Step4-
If symbol is operand then add it to array postfix.
Step5-
(i) If symbol is operator then pop the operators which have same precedence
or higher precedence than the operator which occurred.
(ii) Add the popped operator which occurred.
(iii) Add scanned symbol operator into stack.
Step 6-
(i) If symbol is right parenthesis ‘)’ then pop all the operators from stack
until left parenthesis ‘(’in stack.
(ii) Remove left parenthesis ‘(’ from stack.
Step 7-
If symbol is ‘#’ then pops all the symbols from stack and add them to array postfix
except ‘#’.
Step 8-
Do the same process until ‘#’comes in scanning array infix’

Let us take an infix expression and convert it into postfix-

A*(B+C^D)-E^F*(G/H)
Initially ‘#’ will be added in stack and the end of infix expression.
So now the infix expression will be-
A*(B+C^D)-E^F*(G/H) #

12
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Step symbol operator in stack postfix expression

1. A # A
2. * #* A
3. ( #*( A
4. B #*( AB
5. + #*(+ AB
6. C #*(+ ABC
7. ^ #*(+^ ABC
8. D #*(+^ ABCD
9. ) #* ABCD^+
10. - #- ABCD^+*
11. E #- ABCD^+*E
12. ^ #-^ ABCD^+*E
13. F #-^ ABCD^+*EF
14. * #-* ABCD^+*EF^
15. ( #-*( ABCD^+*EF^
16. G #-*( ABCD^+*EF^G
17. / #-*(/ ABCD^+*EF^G
18. H #-*(/ ABCD^+*EF^GH
19. ) #-* ABCD^+*EF^GH/
20. # ABCD^+*EF^GH/*-

So now the postfix expression is –

ABCD^+*EF^GH/*-

13
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

We can see that the resultant postfix expression is parenthesis free and operators
are in order of sequence of evaluation with operands.
Evaluation of postfix expression
Evaluation of postfix expression also maintains the stack but here stack contains
the operands instead of operators. Whenever any operator occurs in scanning, we
evaluate with last two elements of stack. Initially one unique symbol will be added
at the end of arithmetic expression for termination of scanning. Here we have no
need of information of operator precedence.
Let us take an array infix has arithmetic expression in postfix form. The steps
involved to evaluate the postfix expression will be
Step 1
Add the unique symbol ‘#’ at the end of array postfix.
Step2
Scan the symbol of array postfix one by one from left to right.
Step3
If symbol is operand then push it to stack.
Step4
If symbol is operator then pop last two element of stack and evaluate it as
[top-1] operator [top]
and push it to stack.
Step5
Do the same process until '#' comes in scanning.
Step6
Pop the element of stack which will be value of evaluation of postfix arithmetic
expression.
Step Symbol

14
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Let us take a postfix expression and evaluate it

4, 5, 4, 2, ^, +, *, 2, 2, ^, 9, 3, /, *, -
Initially ‘#’ will be added at the end of postfix expression, so now the postfix
expression will be
4, 5, 4, 2, ^, +, *, 2, 2, ^, 9, 3, /, *, -
Operator in
Step Symbol
Stack
1 4 4
2 5 4’5
3 4 4,5,4
4 2 4,5,4,2
5 ^ 4,5,16
6 + 4,21
7 * 84
8 2 84,2
9 2 84,2,2
10 ^ 84,4
11 9 84,4,9
12 3 84,4,9,3
13 / 84,4,3
14 * 84,12
15 - 72
16 #

So after evaluation of the postfix expression it’s value is 72. Let us take the same
postfix expression in infix form and evaluate it.

15
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

4* (5+4^2)-2^2* (9/3) = 4* (5+16) - 4*3

= 4 * 21-12
= 84-12
= 72
We can see the same result but in postfix evaluation we have no need to take care
of parenthesis and sequence of evaluation.
Recursion:
Recursion is an important concept in computer science. Many
algorithms can be best described in terms of recursion. Suppose to p is a procedure
containing either a call statement to itself or call statement to process that may
eventually result in a call statement back to the original procedure p. Then p is
called a recursive procedure. A recursive procedure must have the following two
properties.
1) There must be certain criteria called best criteria for which the procedure
does not call itself.
2) Each time the procedure does calls itself (directly or indirectly); it must be
closer to the best criteria.
Similarly a function is said to be recursively defined if the function
definition refer to itself. It must have the following two properties.
1) There must be certain arguments called based value. For which the function
does not refer to itself.
2) Each time, the function does refer to itself; the argument of the function
must be closer to a based value.
Direct Recursion
When in the body of a method there is a call to the same method, we say that the
method is directly recursive. That means Direct recursion occurs when a method
invokes itself.
Indirect Recursion or mutually recursive
If method A calls method B, method B calls method C, and method C calls method
A we call the methods A, B and C indirectly recursive or mutually recursive.

16
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Direct Recursion Indirect Recursion

In the direct recursion, only one In indirect recursion more than one
function is called by itself. function are by the other function and
number of times.

direct recursion makes overhead. The indirect recursion does not make any
overhead as direct recursion

The direct recursion called by the While the indirect function called by the
same function other function

In direct function, when function but in indirect recursion, value will

called next time, value of local automatically lost when any other function
variable will stored is called local variable

Direct function engaged memory while local variable of indirect function

location not engaged it

Structure of direct function Structure of indirect function

int num()
int num()
{
{
int sum();
int num();
}
}
int sum(){int num();}

Factorial function:-
The product of positive integer from 1ton, inclusive is called n
factorial and is usually denoted by n!
n! =1*2*3*…*(n-2)*(n-1)*(n)

17
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

It is also called convenient to define 0! =1 so that the function is

defined for all non negative integer. Thus we have
0! =1
1! =1
2! =2*1=2
3! =3*2*1=6
4! =4*3*2*1=24
5! =5*4*3*2*1=120
6! =6*5! =720
According the factorial function may also defined as n! =n*(n-1)!
1) Procedure:
Factorial (fact, n)
This procedure calculates n! And returns the value in the variable fact
Step-
1. if (n=0) then set fact=1 and return
2. set fact=1[Initialize fact for loop]
3. Repeat for k=1 to n
Set fact=k*fact
[End of loop]
4. Return

2) Procedure:
Factorial (fact, n)
This procedure calculates n! And returns the value in variable fact.
Step-

18
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

1. If n=0 then set fact=1 and return

2. Call factorial(fact,n-1)
3. Set fact=n*fact
4. Return
Fibonacci sequence:
The celebrated Fibonacci sequence usually denoted by (f0, f1, f2,)
Is as follow
0,1,1,2,3,5,8,13,21,34,55,89,144
i.e.
f0=0 and f1=1 and each success siding term is sum of two preceding term
55+34=89
A formula definition of this function follows
a) If n=0 or n=1 then fn=n
b) If n>1 then fn=f(n-2)+f(n-1)
Procedure:
Fibonacci (FIB, n)
This procedure calculates fn and returns the value in the first parameter FIB
Step-
1. If n=0 or n=1 then
Set FIB=n and return
2. Call Fibonacci (FIBa,n-2)
3. Call Fibonacci(FIBb,n-1)
4. Set FIB=FIBa+FIBb
5. return

19
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Fibonacci Series
#include <stdio.h>
int fibonacci(int i) {
if(i == 0) {
return 0;
}
if(i == 1) {
return 1;
}
return fibonacci(i-1) + fibonacci(i-2);
}
int main() {
int i;
for (i = 0; i < 10; i++) {
printf("%d\t\n", fibonacci(i));
}
return 0;
}

20
Government Polytehnic, Kolhapur M.B.Patil
Department of Information Technology Data Structure [ITG310]

Factorial Program
#include<stdio.h>
int main()
{
int i,fact=1,number;
printf("Enter a number: ");
scanf("%d",&number);
for(i=1;i<=number;i++){ fact=fact*i; }
printf("Factorial of %d is: %d",number,fact);
return 0; }

21
Government Polytehnic, Kolhapur M.B.Patil