Data Structures and Applications: Unit - 2

STACKS
Outline:
 Definition

 Representation of Stack in C

 Basic operations on Stack

 PUSH

 POP

 PEEP/PEEK

 DISPLAY

 Expressions - Infix, Prefix and Postfix

 Applications of Stack

 Evaluation of Prefix/Postfix expression

 Conversion of expression from one form to another

 Recursion

o Towers of Hanoi Problem

STACK
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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 1

 Data Structures and Applications: Unit - 2

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.

 Assume, MAXSIZE is 3 and the data to be inserted are 10, 5, 3, 7

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 2

 Data Structures and Applications: Unit - 2

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.

 Assume, MAXSIZE is 3

PEEP/PEEK Operation on Stack:

 Retrieving the topmost element from the stack is referred to as
Peep/Peek operation.

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 3

 Data Structures and Applications: Unit - 2

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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 4

 Data Structures and Applications: Unit - 2

}
void PUSH(STACK *s,int data)
{
s->items[++s->top]=data;
printf("\n%d is pushed onto stack",data);
}

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

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 5

 Data Structures and Applications: Unit - 2

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");
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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 6

 Data Structures and Applications: Unit - 2

return 0;
}

void PUSH(STACK *s,char name[])

{
strcpy(s->items[++s->top],name);
printf("\nName %s is pushed on to the stack",name);
}

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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 7

 Data Structures and Applications: Unit - 2

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;
case 4: exit(0);

default: printf("\nInvalid choice");

}
}
return 0;
}

Expressions
 Sequence of operands and operators that reduces to a single value
after evaluation is referred to as an expression.
 Operands can be either a constant or a variable.
 Operators can be +, -, *, /, % and $ or ^.

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.
 Infix expression can be either parenthesized or unparenthesized.
 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.
 Prefix expression is always unparenthesized.
 Examples: +ab, *+abc etc.

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 8

 Data Structures and Applications: Unit - 2

Postfix expression/Reverse Polish expression/Suffix expression:

 An expression in which the operator follows the two operands is

referred to as Postfix expression.
 Postfix expression is always unparenthesized.
 Examples: ab+, ab+c* etc.

Problems:
Convert the following Infix expressions into its equivalent Prefix and
Postfix expressions:

1. a + b

2. a + b * c

3. a * (b + c)

4. (A + B) * (C - D)

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 9

 Data Structures and Applications: Unit - 2

5. 2 $ 3 $ 2

6. a + ((b + c) * d)

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

8. ( ( A + ( B – C ) * D) ^ E + F)

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 10

 Data Structures and Applications: Unit - 2

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

Evaluation of Postfix expression

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 11

 Data Structures and Applications: Unit - 2

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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 12

 Data Structures and Applications: Unit - 2

case '*': return op1*op2;

case '/': return op1/op2;
case '$':
case '^': return pow(op1,op2);
}
}

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;
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 13

 Data Structures and Applications: Unit - 2

Evaluation of Prefix expression

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 14

 Data Structures and Applications: Unit - 2

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');

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 15

 Data Structures and Applications: Unit - 2

else if(isalpha(symb))
{
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

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 16

 Data Structures and Applications: Unit - 2

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;

void PUSH(STACK *s,char data)

{
s->items[++s->top] = data;
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 17

 Data Structures and Applications: Unit - 2

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))
postfix[j++]=symb;
else
{

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 18

 Data Structures and Applications: Unit - 2

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;
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 19

 Data Structures and Applications: Unit - 2

Conversion of Infix expression to Prefix

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 20

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 21

 Data Structures and Applications: Unit - 2

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 It uses conditional constructs such
such as while, do while and for. as if, if-else, switch.
It terminates when loop condition It terminates when the base case is
fails. reached.
It becomes infinite when there is no
It becomes infinite when loop
base case or base case is never
condition never fails.
reached.
It consumes less memory space and It takes more time and consumes
executes faster. more memory space.
It is not suitable for applications It is best suitable for applications
such as Towers of Hanoi, Tree such as Towers of Hanoi, Tree
traversals etc. traversals etc.
Tracing and debugging is easy Tracing and debugging is difficult

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 22

 Data Structures and Applications: Unit - 2

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

}

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
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 23

 Data Structures and Applications: Unit - 2

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

}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 24

 Data Structures and Applications: Unit - 2

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

}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 25

 Data Structures and Applications: Unit - 2

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

}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 26

 Data Structures and Applications: Unit - 2

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));
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 27

 Data Structures and Applications: Unit - 2

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

}

Tracing:

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

}

int main()
{
int i,n;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 28

 Data Structures and Applications: Unit - 2

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
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 29

 Data Structures and Applications: Unit - 2

a[0] a[1] a[2] a[3]

10 20 30 40

Problem11: To print the array elements in reverse order.

In main() function:
print(a,0,4);

int print(int a[],int i,int n)

{
if(i == n) //Base Case
return;
print(a,i+1,n); //General Case
printf(“%d “,a[i]);
}

Problem12: To search for the key element using Binary search

technique.

//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;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 30

 Data Structures and Applications: Unit - 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:
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
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 31

 Data Structures and Applications: Unit - 2

Problem14: To search for a character in a string.

In main() function:
search(str,0,ch);

//Recursive Function
int search(char str[],int i,char ch)
{
if(str[i]==‘\0’) //Base Case for failure
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
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 32

 Data Structures and Applications: Unit - 2

Towers of Hanoi
Initial Setup for Towers of Hanoi

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

Examples: If n = 1 then, no. of moves required = 21-1 = 1

If n = 2 then, no. of moves required = 22-1 = 3
If n = 3 then, no. of moves required = 23-1 = 7
If n = 4 then, no. of moves required = 24-1 = 15

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 33

 Data Structures and Applications: Unit - 2

Recursive Solution for Towers of Hanoi Problem:

Base Case:
If the number of disks is 1, then transfer the disk from Peg A to Peg C.

General Case:
 Recursively transfer n-1 disks from Peg A to Peg B using Peg C as
auxiliary.
 Transfer the nth disk from Peg A to Peg C.
 Recursively transfer n-1 disks from Peg B to Peg C using Peg A as
auxiliary.

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;
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 34

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 35

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 36

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 37

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 38

 Data Structures and Applications: Unit - 2

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 39

 Data Structures and Applications: Unit - 2

QUEUES

Outline:
 Definition
 Representation of Queue in C
 Types of Queues
 Linear Queue/Ordinary Queue
 Circular Queue
 Priority Queue
 Double Ended Queue
 Basic operations on Linear Queue
 INSERT, DELETE, DISPLAY
 Basic operations on Circular Queue
 INSERT, DELETE, DISPLAY
 Basic operations on Priority Queue
 INSERT, DELETE, DISPLAY
 Basic operations on Double ended Queue
 INSERT, DELETE, DISPLAY

QUEUE
 Definition: It is a non-primitive linear data structure in which a new
element can be inserted at one end called the rear end and an
element can be deleted from the other end called the front end.

 Queue is also called as FIFO (First In First Out) data structure since
the first element inserted will be the first to be removed from the
Queue.

Representation of Queue in C:
#define MAXSIZE 4
typedef struct
{
int items[MAXSIZE];
int f,r;
}QUEUE;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 40

 Data Structures and Applications: Unit - 2

Types of Queues:
 Linear Queue/Ordinary Queue

 Circular Queue

 Priority Queue

 Double Ended Queue

LINEAR QUEUE

Insertion Operation on Queue:

 We can insert a new element at the rear end of the Queue.
 If the Queue is full and an attempt is made to insert an element to the
Queue then it results in a situation called “Queue Overflow” !!!
 Condition to test for “Queue Overflow” : if(r == MAXSIZE-1)
If this condition is true then it indicates that queue is full.
 Assume, MAXSIZE is 3 and the data to be inserted are 10, 5, 3, 7

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 41

 Data Structures and Applications: Unit - 2

Since, Queue is full, data 7 cannot be inserted. This operation has resulted
in Queue Overflow.

Deletion Operation on Linear Queue:

 We can remove an element at the front end of the queue.

 If the Queue is empty and an attempt is made to delete an element
from the queue then it results in a situation called
“Queue underflow” !!!

 Condition to test for “Queue underflow” : if(f == -1)

If this condition is true then it indicates that Queue is empty.

 Assume, MAXSIZE is 3

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 42

 Data Structures and Applications: Unit - 2

Display Operation on Linear Queue:

 Display operation means listing the contents of the Queue either from
front end of the queue till rear end or from rear end of the queue till
front end of the queue.

 Check for queue empty: if(f == -1) printf(“Queue is Empty”);

 Print the Queue elements one by one:

for(i=f;i<=r;i++)
printf(“%d->”,items[i]);

Lab Program5: Develop a C program to implement Linear Queue of

characters to perform the insertion, deletion and display operations.

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 3

typedef struct
{
char items[MAXSIZE];
int f,r;
}QUEUE;

int isfull(QUEUE q)
{
if(q.r == MAXSIZE-1)
return 1;
return 0;
}

int isempty(QUEUE q)
{
if(q.f == -1)
return 1;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 43

 Data Structures and Applications: Unit - 2

return 0;
}

void INSERT(QUEUE *q,char data)

{
q->items[++q->r]=data;
printf("\nCharacter \'%c\' is inserted into queue",data);
if(q->f==-1)
q->f=0;
}

char DELETE(QUEUE *q)

{
char data;
data = q->items[q->f];
if(q->f == q->r)
q->f = q->r = -1;
else
q->f++;
return(data);
}

void DISPLAY(QUEUE q)
{
int i;
printf("\nQUEUE CONTENTS:\nFRONT->");
for(i=q.f;i<=q.r;i++)
printf("%c->",[Link][i]);
printf("REAR");
}

int main()
{
QUEUE q;
int choice;
char data;

q.f=q.r=-1;

while(1)
{
printf("\n\n1:Insert\n2:Delete\n3:Display\n4:Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: if(isfull(q))
printf("\nQueue Overflow !!!");
else

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 44

 Data Structures and Applications: Unit - 2

{
printf("\nEnter the character to be inserted: ");
getchar();
scanf("%c",&data);
INSERT(&q,data);
}
break;

case 2: if(isempty(q))
printf("\nQueue Underflow !!!");
else
printf("\nCharacter \’%c\’ is deleted from queue",DELETE(&q));
break;

case 3: if(isempty(q))
printf("\nQueue is Empty !!!");
else
DISPLAY(q);
break;

case 4: exit(0);

default: printf("\nInvalid choice");

}
}
return 0;
}

Limitations of Linear Queue:

 In Linear queue, f and r show linear motion.

 Once r reaches MAXSIZE-1, it is not possible to insert an element
even though there is free memory space.
This limitation can be overcome using Circular Queue.
 In circular queue, f and r show circular motion.

Insertion Operation on Circular Queue:

 The statement used to update r is as follows:
r = (r+1)%MAXSIZE;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 45

 Data Structures and Applications: Unit - 2

 Assume, MAXSIZE is 3 and the data to be inserted are 10, 20, 30, 40

Since queue is full, data 40 cannot be inserted. This operation has resulted
in Queue Overflow.

 Condition to check for Circular Queue overflow:

if(((f==0) && (r==MAXSIZE-1)) || (f==(r+1)))
printf(“Circular Queue Overflow”);
or
if(f == (r+1)%MAXSIZE)
printf(“Circular Queue Overflow”);

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 46

 Data Structures and Applications: Unit - 2

Deletion Operation on Circular Queue:

 The statement used to update f is as follows:
f = (f+1)%MAXSIZE;

 Consider the Queue of size 3:

 Condition to check for Circular Queue underflow:

if(f == -1)
printf(“Circular Queue Underflow”);

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 47

 Data Structures and Applications: Unit - 2

Display Operation on Circular Queue:

 If f <= r then elements can be displayed from f to r.

 If f > r then elements can be displayed from f to MAXSIZE-1 and

then from 0 to r.

Lab Program6: Develop a C program to implement Circular Queue of

integers to perform the insertion, deletion and display operations.
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 3
int count;

typedef struct
{
int items[MAXSIZE];
int f,r;
}QUEUE;

int isfull(QUEUE q)
{
if(q.f == (q.r+1)%MAXSIZE)
return 1;
return 0;
}

int isempty(QUEUE q)
{
if(q.f == -1)
return 1;
return 0;
}

void INSERT(QUEUE *q,int data)

{
q->r=(q->r+1)%MAXSIZE;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 48

 Data Structures and Applications: Unit - 2

q->items[q->r]=data;
printf("\n%d is inserted into circular queue",data);
count++;
if(q->f==-1)
q->f=0;
}

int DELETE(QUEUE *q)

{
int data;
data = q->items[q->f];
count--;
if(q->f == q->r)
q->f = q->r = -1;
else
q->f = (q->f +1)%MAXSIZE;
return(data);
}

void DISPLAY(QUEUE q)
{
int i;
printf("\nQUEUE CONTENTS:\nFRONT->");
for(i=1;i<=count;i++)
{
printf("%d->",[Link][q.f]);
q.f=(q.f+1)%MAXSIZE;
}
printf("REAR");
}

int main()
{
QUEUE q;
int choice;
int data;
q.f=q.r=-1;
while(1)
{
printf("\n\n1:Insert\n2:Delete\n3:Display\n4:Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: if(isfull(q))
printf("\nCircular Queue Overflow !!!");
else
{
printf("\nEnter the data to be inserted: ");

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 49

 Data Structures and Applications: Unit - 2

scanf("%d",&data);
INSERT(&q,data);
}
break;

case 2: if(isempty(q))
printf("\nCircular Queue Underflow !!!");
else
printf("\n%d is deleted from queue",DELETE(&q));
break;

case 3: if(isempty(q))
printf("\nCircular Queue is Empty !!!");
else
DISPLAY(q);
break;

case 4: exit(0);
default: printf("\nInvalid choice");
}
}
return 0;
}

Problem: Consider a circular queue of size 5 with following elements: 25, 4,

1 where, F=2 and R = 4. Insert 50 and 12 into the queue and delete one
element. Write the queue status indicating the positions of F and R after
each operation.
Solution:

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 50

 Data Structures and Applications: Unit - 2

Double Ended Queue (Dequeue)

Definition: It is a non-primitive linear data structure in which insertion and
deletion operations can be performed at both the ends of the queue.

Variants of Dequeue:
 Input-Restricted Dequeue
 Output-Restricted Dequeue

Input-Restricted Dequeue
Definition: It is a non-primitive linear data structure in which deletion
operation can be performed at both the ends of the queue but insertion
operation can be performed at only one end of the queue.

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 51

 Data Structures and Applications: Unit - 2

Output-Restricted Dequeue
Definition: It is a non-primitive linear data structure in which insertion
operation can be performed at both the ends of the queue but deletion
operation can be performed at only one end of the queue.

Program: Develop a C program to implement Double ended Queue of

integers to perform the insertion, deletion and display operations.
#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 4

typedef struct
{
int items[MAXSIZE];
int f,r;
}QUEUE;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 52

 Data Structures and Applications: Unit - 2

void ins_right(QUEUE *q,int data)

{
q->items[++q->r] = data;
if(q->f == -1)
q->f = 0;
}

void ins_left(QUEUE *q,int data)

{
if(q->f == -1)
{
q->items[++q->f] = data;
q->r = 0;
}
else
q->items[--q->f] = data;
}

int del_left(QUEUE *q)

{
int data;
data = q->items[q->f];
if(q->f == q->r)
q->f = q->r = -1;
else
q->f++;
return data;
}

int del_right(QUEUE *q)

{
int data;
data = q->items[q->r];
if(q->f == q->r)
q->f = q->r = -1;
else
q->r--;
return data;
}

void display(QUEUE q)
{
int i;
printf(“\nDequeue Contents:\nFront->”);
for(i = q.f;i<=q.r;i++)
printf(“%d->”,[Link][i]);
printf(“Rear”);
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 53

 Data Structures and Applications: Unit - 2

int main()
{
QUEUE q;
int choice,data;

q.f = q.r = -1;

while(1)
{
printf(“\n\n1:Ins_Right\n2:Ins_Left\n3:Del_Right\n4:Del_Left\n5:Display\n6:Exit”);
printf(“\nEnter your choice: “);
scanf(“%d”,&choice);

switch(choice)
{
case 1: if( q.r == MAZSIZE-1)
printf(“\nDequeue Overflow”);
else
{
printf(“\nEnter the data to be inserted: “);
scanf(“%d”,&data);
ins_right(&q,data);
printf(“\n%d is inserted at rear end of dequeue”,data);
}
break;

case 2: if( q.f == 0)

printf(“\nDequeue Overflow”);
else
{
printf(“\nEnter the data to be inserted: “);
scanf(“%d”,&data);
ins_left(&q,data);
printf(“\n%d is inserted at front end of dequeue”,data);
}
break;

case 3: if( q.r == -1)

printf(“\nDequeue Underflow”);
else
printf(“\n%d is deleted from rear end of dequeue”,del_right(&q));

break;

case 4: if( q.f == -1)

printf(“\nDequeue Underflow”);
else
printf(“\n%d is deleted from front end of dequeue”,del_left(&q));

break;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 54

 Data Structures and Applications: Unit - 2

case 5: if( q.f == -1)

printf(“\nDequeue is Empty”);
else
display(q);
break;

case 6: exit(0);
default: printf(“\nInvalid choice”);
}
}
return 0;
}

Priority Queue
Definition: It is a non-primitive linear data structure in which the elements
are inserted or deleted based on some priority.

Priority Queue Implementation

 Using Multiple Queues
 Using Single Queue

Implementation of Priority Queue using Multiple Queues

 Assume that the no. of queues are 3 and priority of queue0, queue1
and queue2 are 0, 1 and 2 respectively.

 Multiple queues are used to perform insertion and deletion operations

based on priority.

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 55

 Data Structures and Applications: Unit - 2

 Each queue exhibits FIFO behaviour.

 Each queue has its own pair of f and r.

Insertion Operation:
 The elements are inserted into the appropriate queue based on the
priority.

Deletion Operation:
 An element from queue0 is deleted first. Once queue0 becomes empty,
element from queue1 is deleted and so on.

Program: Implementation of Priority Queue using Multiple Queues

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 3

typedef struct
{
int items[MAXSIZE];
int f,r;
}QUEUE;

void INSERT(QUEUE q[3],int p)

{
int data;
if(q[p].r == MAXSIZE-1)
printf(“\n\nQueue %d overflow”,p);
else
{
printf(“\nEnter the data to be inserted: “);
scanf(“%d”,&data);

q[p].items[++q[p].r] = data;
printf(“\n%d is inserted into Queue %d”,data,p);

if(q[p].f == -1)
q[p].f = 0;
}
}

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 56

 Data Structures and Applications: Unit - 2

void DELETE(QUEUE q[3])

{
int i,data;

for(i=0;i<3;i++)
{
if(q[i].f == -1)
printf(“\n\nQueue %d Underflow”,i);
else
{
data = q[i].items[q[i].f];
printf(“\n%d is deleted from queue %d”,data,i);

if(q[i].f == q[i].r)
q[i].f = q[i].r = -1;
else
q[i].f++;
return;
}
}
}

void DISPLAY(QUEUE q[3])

{
int i,j;
for(i=0;i<3;i++)
{
if(q[i].f == -1)
printf(“\n\nQueue %d is Empty”,i);
else
{
printf(“\n\nQueue %d Contents:\nFront->”,i);
for(j=q[i].f;j<=q[i].r;j++)
printf(“%d->”,q[i].items[j]);
printf(“Rear”);
}
}
}

int main()
{
QUEUE q[3];
int i,p,choice;

for(i=0;i<3;i++)
q[i].f = q[i].r = -1;
while(1)
{
printf(“\n\n1:INSERT\n2:DELETE\n3:DISPLAY\n4:EXIT”);

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 57

 Data Structures and Applications: Unit - 2

printf(“\nEnter your choice: “);

scanf(“%d”,&choice);
switch(choice)
{
case 1: printf(“\nEnter the priority: “);
scanf(“%d”, &p);
if(p < 0 || p >2)
printf(“\nInvalid priority”);
else
INSERT(q,p);
break;

case 2: DELETE(q);
break;

case 3: DISPLAY(q);
break;

case 4: exit(0);
default: printf(“\nInvalid choice !!!”);
}
}
return 0;
}

Implementation of Priority Queue using Single Queue

 There are two types of priority queues:
 Ascending Priority Queue
 Descending Priority Queue

Ascending Priority Queue

 It is a non-primitive linear data structure into which element can be
inserted in any arbitrary order but while deleting, smallest element is
deleted first.

Descending Priority Queue

 It is a non-primitive linear data structure into which element can be
inserted in any arbitrary order but while deleting, largest element is
deleted first.

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 58

 Data Structures and Applications: Unit - 2

Program: Implementation of Ascending Priority Queue.

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 3

typedef struct
{
int items[MAXSIZE];
int f,r;
}QUEUE;

int isfull(QUEUE q)
{
if(q.r == MAXSIZE-1)
return 1;
return 0;
}

int isempty(QUEUE q)
{
if(q.f == -1)
return 1;
return 0;
}

void INSERT(QUEUE *q,int data)

{
int i;
q->r++;
i = q->r;
while(i > 0 && data < q->items[i-1])
{
q->items[i] = q->items[i-1];
i--;
}
q->items[i] = data;
printf(“\n%d is inserted into the queue”,data);
if(q->f == -1)
q->f = 0;
}

int DELETE(QUEUE *q)

{
int data;
data = q->items[q->f];
if(q->f == q->r)
q->f = q->r = -1;
else
q->f++;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 59

 Data Structures and Applications: Unit - 2

return(data);
}

void DISPLAY(QUEUE q)
{
int i;
printf("\nQueue Contents:\nFront->");

for(i=q.f;i<=q.r;i++)
printf("%d->",[Link][i]);
printf("Rear");
}

int main()
{
QUEUE q;
int choice,data;

q.f = q.r = -1;

while(1)
{
printf("\n\n1:Insert\n2:Delete\n3:Display\n4:Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);

switch(choice)
{
case 1: if(isfull(q))
printf("\nQueue Overflow !!!");
else
{
printf("\nEnter the data to be inserted: ");
scanf("%d",&data);
INSERT(&q,data);
}
break;

case 2: if(isempty(q))
printf("\nQueue Underflow !!!");
else
printf("\n%d is deleted from queue",DELETE(&q));
break;

case 3: if(isempty(q))
printf("\nQueue is Empty !!!");
else
DISPLAY(q);
break;

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 60

 Data Structures and Applications: Unit - 2

case 4: exit(0);

default: printf("\nInvalid choice");

}
}
return 0;
}

*************** END OF UNIT - 2 ***************

Smt. Kavitha M, Assistant Professor, Dept. of CSE, SIT, Tumakuru-3 Page 61