Module-2 Data Structure using C
STACKS
Definition: It is a non-primitive linear data structure into which a new element can be added
or from which an element can be deleted at only one end called the top of the stack. The other
end is called the bottom of the stack.
Stack is also called as LIFO (Last In First Out) data structure since the last element inserted
will be the first to be removed from the stack.
Representation of Stack in C:
#define MAXSIZE 4
typedef struct
{
int items[MAXSIZE];
int top;
}STACK;
Basic Operations on Stack:
• Push operation
• Pop operation
• Peep/peek operation
• Display operation
PUSH Operation on Stack:
• Inserting a new element onto the top of the stack is referred to as Push operation.
• If the stack is full and an attempt is made to insert an element onto the stack then it
results in a situation called “Stack Overflow” !!!
• Condition to test for “Stack Overflow” : if(top == MAXSIZE-1)
If this condition is true then it indicates that stack is full.
POP Operation on Stack:
• Deleting an element from the top of the stack is referred to as Pop operation.
• If the stack is empty and an attempt is made to delete an element from the stack then it
results in a situation called “Stack underflow”!!!
• Condition to test for “Stack underflow” : if(top == -1)
If this condition is true then it indicates that stack is empty.
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 1
Module-2 Data Structure using C
PEEP/PEEK Operation on Stack:
• Retrieving the topmost element from the stack is referred to as Peep/Peek operation.
Display Operation on Stack:
• Display operation means listing the contents of the stack either from bottom of the
stack till top or from top of the stack till bottom of the stack.
• Check for stack empty: if(top==-1) printf(“Stack is Empty”);
• Print the stack elements one by one:
for(i=0;i<=top;i++)
printf(“%d->”,items[i]);
Program: Develop a C program to implement stack of integers to perform push, pop, peek
and display operations.
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 3
typedef struct
{
int items[MAXSIZE];
int top;
}STACK;
int isfull(STACK s)
{
if([Link]==MAXSIZE-1)
return 1;
return 0;
}
int isempty(STACK s)
{
if([Link]==-1)
return 1;
return 0;
}
void PUSH(STACK *s,int data)
{
s->items[++s->top]=data;
printf("\n%d is pushed onto stack",data);
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 2
Module-2 Data Structure using C
int POP(STACK *s)
{
return(s->items[s->top--]);
}
int PEEK(STACK s)
{
return([Link][[Link]]);
}
void DISPLAY(STACK s)
{
int i;
printf("\nSTACK CONTENTS:\nBOS->");
for(i=0;i<=[Link];i++)
printf("%d->",[Link][i]);
printf("TOS");
}
int main()
{
STACK s;
int data,choice;
[Link] = -1;
while(1)
{
printf("\n\n1:Push\n2:Pop\n3:Peek\n4:Display\n5:Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: if(isfull(s))
printf("\nSTACK OVERFLOW");
else
{
printf("\nEnter the data to be pushed: ");
scanf("%d",&data);
PUSH(&s,data);
}
break;
case 2: if(isempty(s))
printf("\nSTACK UNDERFLOW");
else
printf("\n%d is popped from top of the stack",POP(&s));
break;
case 3: if(isempty(s))
printf("\nSTACK EMPTY");
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 3
Module-2 Data Structure using C
else
PEEK(s);
break;
case 4: if(isempty(s))
printf("\nSTACK EMPTY");
else
DISPLAY(s);
break;
case 5:exit(0);
default: printf("\nInvalid choice");
}
}
return 0;
}
Lab Program2: Develop a C program to implement Stack of names to perform the push,
pop and display operations.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 3
typedef struct
{
char items[MAXSIZE][25];
int top;
}STACK;
int isfull(STACK s)
{
if([Link]==MAXSIZE-1)
return 1;
return 0;
}
int isempty(STACK s)
{
if([Link]==-1)
return 1;
return 0;
}
void PUSH(STACK *s,char name[])
{
strcpy(s->items[++s->top],name);
printf("\nName %s is pushed on to the stack",name);
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 4
Module-2 Data Structure using C
char* POP(STACK *s)
{
return(s->items[s->top--]);
}
void DISPLAY(STACK s)
{
int i;
printf("\nSTACK CONTENTS:\nBOS->");
for(i=0;i<=[Link];i++)
printf("%s->",[Link][i]);
printf("TOS");
}
int main()
{
STACK s;
int choice;
char name[20];
[Link] = -1;
while(1)
{
printf("\n\n1:Push\n2:Pop\n3:Display\n4:Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: if(isfull(s))
printf("\nSTACK OVERFLOW");
else
{
printf("\nEnter the name to be pushed: ");
scanf("%s",name);
PUSH(&s,name);
}
break;
case 2: if(isempty(s))
printf("\nSTACK UNDERFLOW");
else
printf("\nName %s is popped from top of the stack",POP(&s));
break;
case 3: if(isempty(s))
printf("\nSTACK EMPTY");
else
DISPLAY(s);
break;
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 5
Module-2 Data Structure using C
case 4: exit(0);
default: printf("\nInvalid choice");
}
}
return 0;
}
Expressions
Different forms of expressions:
Infix expression:
• An expression in which the operator is in between the two operands is referred to as
an Infix expression.
• Examples: a+b, (a+b)*c etc.
Prefix expression/Polish expression:
• An expression in which the operator precedes the two operands is referred to as Prefix
expression.
• Examples: +ab, *+abc etc.
Postfix expression/Reverse Polish expression/Suffix expression:
• An expression in which the operator follows the two operands is referred to as Postfix
expression.
• Examples: ab+, ab+c* etc.
Applications of Stack
▪ Conversion of expression from one form to another
▪ Evaluation of Prefix/Postfix expression
▪ Recursion
▪ Checking for string palindrome
▪ Checking for validity of expression
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 6
Module-2 Data Structure using C
Evaluation of Postfix expression
Procedure/Algorithm:
1. Scan each symbol in the postfix expression from left to right and perform one of the
following operations till end of input is encountered:
a) If scanned symbol is an operand then push it on to the stack.
b) If the scanned symbol is an operator then
i. Pop top two elements from the stack. First popped is operand2 and
second popped is operand1
ii. Perform the indicated operation
result = operand1 operator operand2
i. Push the result back to the stack.
2. Pop the result of evaluation from the top of the stack.
Lab Program4: Develop a C program to evaluate the given postfix expression.
#include<stdio.h>
#include<ctype.h>
#include<math.h>
#define MAXSIZE 20
typedef struct
{
float items[MAXSIZE];
int top;
}STACK;
void PUSH(STACK *s,float data)
{
s->items[++s->top] = data;
}
float POP(STACK *s)
{
return(s->items[s->top--]);
}
float compute(float op1,char symb,float op2)
{
switch(symb)
{
case '+': return op1+op2;
case '-': return op1-op2;
case '*': return op1*op2;
case '/': return op1/op2;
case '$':
case '^': return pow(op1,op2);
}
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 7
Module-2 Data Structure using C
int main()
{
STACK s;
char postfix[30],symb;
float n1,n2,res,data;
int i;
[Link]=-1;
printf("\nEnter a valid postfix expression:\n");
scanf("%s",postfix);
for(i=0;postfix[i]!=‘\0’;i++)
{
symb=postfix[i];
if(isdigit(symb))
PUSH(&s,symb-'0');
else if(isalpha(symb))
{
printf("\n%c = ",symb);
scanf("%f",&data);
PUSH(&s,data);
}
else
{
n2=POP(&s);
n1=POP(&s);
res=compute(n1,symb,n2);
PUSH(&s,res);
}
}
printf("\nResult of evaluation: %f",POP(&s));
return 0;
}
Evaluation of Prefix expression
Procedure/Algorithm:
1. Scan each symbol in the prefix expression from right to left and perform one of the
following operations till end of input is encountered:
a) If scanned symbol is an operand then push it on to the stack.
b) If the scanned symbol is an operator then
i. Pop top two elements from the stack. First popped is operand1 and
second popped is operand2
ii. Perform the indicated operation
result = operand1 operator operand2
i. Push the result back to the stack.
2. Pop the result of evaluation from the top of the stack.
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 8
Module-2 Data Structure using C
Program: Develop a C program to evaluate the given prefix expression.
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#define MAXSIZE 20
typedef struct
{
float items[MAXSIZE];
int top;
}STACK;
void PUSH(STACK *s,float data)
{
s->items[++s->top] = data;
}
float POP(STACK *s)
{
return(s->items[s->top--]);
}
float compute(float op1,char symb,float op2)
{
switch(symb)
{
case '+': return op1+op2;
case '-': return op1-op2;
case '*': return op1*op2;
case '/': return op1/op2;
case '$':
case '^': return pow(op1,op2);
}
}
int main()
{
STACK s;
char prefix[30],symb;
float n1,n2,res,data;
int i;
[Link]=-1;
printf("\nEnter a valid prefix expression:\n");
scanf("%s",prefix);
for(i=strlen(prefix)-1;i>=0;i--)
{
symb=prefix[i];
if(isdigit(symb))
PUSH(&s,symb-'0');
else if(isalpha(symb))
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 9
Module-2 Data Structure using C
{
printf("\n%c = ",symb);
scanf("%f",&data);
PUSH(&s,data);
}
else
{
n1=POP(&s);
n2=POP(&s);
res=compute(n1,symb,n2);
PUSH(&s,res);
}
}
printf("\nResult of evaluation: %f",POP(&s));
return 0;
}
Conversion of Infix expression to Postfix
Procedure/Algorithm:
1. Push ‘#’ onto the stack.
2. Scan each symbol in the infix expression from left to right and perform one of the
following operations till end of input is encountered:
a) If the scanned symbol is an operand then, add it to the postfix expression.
b) If the scanned symbol is ‘(‘ (left parenthesis) then, push it onto the stack.
c) If the scanned symbol is ‘)’ (right parenthesis) then repeatedly pop each
operator from the top of the stack and add it to the postfix expression till left
parenthesis is encountered. Pop left parenthesis but don’t add it to postfix
expression.
d) If the scanned symbol is an operator then check the precedence of scanned
operator with top of the stack operator.
i. Repeatedly pop each operator from the stack and add it to postfix
expression if scanned operator has lower or same precedence as that of
top of the stack operator.
ii. Push the scanned operator onto the stack.
3. Pop the remaining operators one by one from the stack and add them to the postfix
expression.
Lab Program3: Develop a C program to convert infix expression to postfix.
#include<stdio.h>
#include<ctype.h>
#define MAXSIZE 25
typedef struct
{
char items[MAXSIZE];
int top;
}STACK;
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 10
Module-2 Data Structure using C
void PUSH(STACK *s,char data)
{
s->items[++s->top] = data;
}
char POP(STACK *s)
{
return(s->items[s->top--]);
}
char PEEK(STACK s)
{
return([Link][[Link]]);
}
int preced(char symb)
{
switch(symb)
{
case '#':
case '(': return 0;
case '+':
case '-': return 1;
case '*':
case '/':
case '%': return 2;
case '$':
case '^': return 3;
}
}
int main()
{
STACK s;
char infix[30],postfix[30],symb,ch;
int i,j=0;
[Link]=-1;
printf("\nEnter a valid infix expression:\n");
scanf("%s",infix);
PUSH(&s,'#');
for(i=0;infix[i]!='\0';i++)
{
symb=infix[i];
if(isalnum(symb))
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 11
Module-2 Data Structure using C
postfix[j++]=symb;
else
{
switch(symb)
{
case '(': PUSH(&s,'(');
break;
case ')': while((ch=POP(&s))!='(')
postfix[j++]=ch;
break;
default: while(preced(symb)<=preced(PEEK(s)))
{
if(symb==PEEK(s) && preced(symb)==3)
break;
postfix[j++] = POP(&s);
}
PUSH(&s,symb);
}
}
while(PEEK(s)!='#')
postfix[j++]=POP(&s);
postfix[j]='\0';
printf("\nResultant Postfix Expression:\n");
printf("%s",postfix);
return 0;
}
Conversion of Infix expression to Prefix
Procedure/Algorithm:
1. Push ‘#’ onto the stack.
2. Scan each symbol in the infix expression from right to left and perform one of the
following operations till end of input is encountered:
a) If the scanned symbol is an operand then, add it to the prefix expression.
b) If the scanned symbol is ‘)‘ (right parenthesis) then, push it onto the stack.
c) If the scanned symbol is ‘(’ (left parenthesis) then repeatedly pop each operator
from the top of the stack and add it to the prefix expression till right parenthesis is
encountered. Pop right parenthesis but don’t add it to prefix expression.
d) If the scanned symbol is an operator then check the precedence of scanned
operator with top of the stack operator.
i. Repeatedly pop each operator from the stack and add it to prefix
expression if scanned operator has lower precedence as that of top of the
stack operator.
ii. Push the scanned operator onto the stack.
3. Pop the remaining operators one by one from the stack and add them to the prefix
expression.
4. Reverse the prefix expression to get the final prefix expression.
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 12
Module-2 Data Structure using C
Recursion
Definition: The process in which a function calls itself directly or indirectly is referred to as
recursion and the corresponding function is called as a recursive function.
Properties of a recursive function
• It should have at least one base case that doesn’t involve call to itself.
• Each time a recursive function is called, the arguments passed must be updated so that
it comes closer to the base case.
Differences between Iteration and Recursion
Iteration Recursion
It uses looping control constructs such as It uses conditional constructs such as if, if-
while, do while and for. else, switch.
It terminates when loop condition fails. It terminates when the base case is reached.
It becomes infinite when loop condition It becomes infinite when there is no base case
never fails. or base case is never reached.
It consumes less memory space and executes It takes more time and consumes more
faster. memory space.
It is not suitable for applications such as It is best suitable for applications such as
Towers of Hanoi, Tree traversals etc. Towers of Hanoi, Tree traversals etc.
Tracing and debugging is easy Tracing and debugging is difficult
Problem1: To find the factorial of a number.
//Recursive Function
int fact(int n)
{
if(n==0) // Base Case
return 1;
return n*fact(n-1); //General Case
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 13
Module-2 Data Structure using C
Problem2: To compute product of two positive integers.
//Recursive Function
int mul(int a,int b)
{
if(a == 0 || b == 0) // Base Case
return 0;
return(a + mul(a,b-1)); //General Case
}
Problem3: To compute sum of first n natural numbers.
//Recursive Function
int sum(int n)
{
if(n == 1) // Base Case
return 1;
return(n + sum(n-1)); //General Case
}
Problem4: To compute sum of squares of first n natural numbers.
//Recursive Function
int sum(int n)
{
if(n == 1) // Base Case
return 1;
return(n*n+sum(n-1)); //General Case
}
Problem5: To compute sum of the series 1 + 1/2 +1/3+ . . . +1/n
//Recursive Function
float sum(int n)
{
if(n == 1) // Base Case
return 1;
return(1.0/n + sum(n-1)); //General Case
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 14
Module-2 Data Structure using C
Problem6: To compute sum of all the digits of a positive integer
//Recursive Function
int sum(int n)
{
if(n == 0) // Base Case
return 0;
return(n%10 + sum(n/10)); //General Case
}
Problem7: To compute xn
//Recursive Function
float find(int x,int n)
{
if(n == 0) // Base Case
return 1;
if(n>0)
return(x * find(x,n-1)); //General case
return(1.0/x * find(x,n+1));
}
Problem8: To find the nth Fibonacci number (0 1 1 2 3 5….)
//Recursive Function
int fibo(int n)
{
if(n == 0 || n==1) // Base Case
return n;
return(fibo(n-1)+fibo(n-2)); //General case
}
Program: Develop a C Program to generate first n Fibonacci numbers. Use recursive C
function to find nth Fibonacci number.
#include<stdio.h>
int fibo(int n)
{
if(n == 0 || n == 1) // Base Case
return n;
return(fibo(n-1) + fibo(n-2)); //General case
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 15
Module-2 Data Structure using C
int main()
{
int i,n;
printf(“\nEnter the value of n: “);
scanf(“%d”,&n);
printf(“\nFirst %d Fibonacci numbers:\n”,n);
for(i=0;i<n;i++)
printf(“%d ”,fibo(i));
return 0;
}
Problem9: To compute GCD of two integers.
//Recursive Function
int gcd(int m,int n)
{
if(n == 0) // Base Case
return m;
return(gcd(n,m%n)); //General Case
}
Problem10: To compute sum of all integers in an array of size n.
In main() function:
printf(“\nSum = %d”,sum(a,n-1));
//Recursive Function
int sum(int a[],int n)
{
if(n == 0) // Base Case
return a[n];
return(a[n] + sum(a,n-1)); //General Case
}
Problem11: To print the array elements in reverse order.
In main() function:
print(a,0,4);
void print(int a[],int i,int n)
{
if(i == n) //Base Case
return;
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 16
Module-2 Data Structure using C
print(a,i+1,n); //General Case
printf(“%d “,a[i]);
}
Problem12: To search for the key element using Binary search technique.
In main() function:
res = search(a,0,n-1,key);
//Recursive Function
int search(int a[],int low,int high,int key)
{
int mid;
if(low>high) //Base case for failure
return -1;
mid=(low+high)/2;
if(key == a[mid]) // Base case for success
return(mid+1);
if(key<a[mid])
return(search(a,low,mid-1,key));
return(search(a,mid+1,high,key);
}
Problem13: To find the length of the string.
In main() function:
printf(“\nLength = %d”,findLength(str,0));
//Recursive Function
int findLength(char str[],int i)
{
if(str[i]==‘\0’) //Base Case
return 0;
return(1+findLength(str,i+1)); //General Case
}
Problem14: To search for a character in a string.
In main() function:
res = search(str,0,ch);
//Recursive Function
int search(char str[],int i,char ch)
{
if(str[i]==‘\0’) //Base Case for failure
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 17
Module-2 Data Structure using C
return(-1);
if(str[i] == ch) //Base Case for success
return(i+1);
return(search(str,i+1,ch)); //General Case
}
Problem15: To check whether a given string is a palindrome or not.
In main() function:
res = checkPalindrome(str,0,strlen(str)-1);
//Recursive Function
int checkPalindrome(char str[],int i,int j)
{
if(i>=j) //Base Case for success
return(1);
if(str[i] != str[j]) //Base Case for failure
return(-1);
return(checkPalindrome(str,i+1,j-1)); //General Case
}
Towers of Hanoi
Initial Setup for Towers of Hanoi
n
disks
. . .
Peg A Peg B Peg C
• Three pegs are available named Peg A, Peg B and Peg C.
• n disks of varying diameter are placed on Peg A such that smaller disks are placed
over larger disks.
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 18
Module-2 Data Structure using C
• Problem: n disks are to be transferred from source Peg A to destination Peg C
using Peg B as auxiliary.
Rules for transferring the disks:
• Only one disk can be transferred at a time from any peg to any other peg.
• Larger disk can never be placed over the smaller disk.
Note: If n is the number of disks then the minimum (ideal) number of moves required to
transfer n disks from source to destination is 2n - 1.
C Program for Towers of Hanoi Problem
#include<stdio.h>
int moves;
void TOH(int n,char src,char temp,char dest)
{
if(n == 1)
{
printf(“\nTransfer disk %d from Peg %c to Peg %c”,n,src,dest);
moves++;
return;
}
TOH(n-1,src,dest,temp);
printf(“\nTransfer disk %d from Peg %c to Peg %c”,n,src,dest);
moves++;
TOH(n-1,temp,src,dest);
}
int main()
{
int n;
printf(“\nEnter the number of disks: “);
scanf(“%d”,&n);
TOH(n,’A’,’B’,’C’);
printf(“\nTotal number of moves taken = %d”,moves);
return 0;
}
[Link] B S, Associate Professor, Dept. of CSE, BIT, Bangalore 19