Circular
queue: The simple or in a straight line queue there are
several limitations we know even if memory locations at the beginning of queue
are available, elements cannot be inserted. We can efficiently utilize the
space available of straight-line queue by using circular queue.
In the circular queue, the first element is stored
immediately after last element. If the last location of the queue is occupied,
the new element is inserted at the first memory location of queue implementing
an array.
#include<stdio.h>
#define size 5 // Header files
int cque[size],f=-1,r=-1;
void main() //main function
{
int choice,item,val;
do{
printf("1.INSERT \n");
printf("2.DELETE \n");
printf("3.DISPLAY\n");
printf("4.EXIT \n");
printf("ENTER YOUR
CHOICE\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nENTER THE ITEM TO BE
INSERTED\n")
scanf("%d",&item);
insque(item); //function call
to insert number to circular queue
break;
case 2: item=delque();
//function call to delete number from circular queue
if(item!=-1)
printf("\n*********DELETED ELEMENT IS
%d*********",item);
break
case 3: printf("\n******CONTENTS OF
CQUEUE************\n");
display(); //function call to display the queue
break;
case 4: printf("TERMINATING\n");
break;
default: printf("invalid option! try
again\n");
break;
}
printf("\n");
}
while(choice!=4);
}
insque(int item)
{
if(cquefull())
printf("\n **********CQUEUE
OVERFLOW***********\n");
else {
if(f==-1)
f=0;
r=(r+1)%size;
cque[r]=item;
}
}
int delque()
{
int item;
if(cqueempty()){
printf("\n
****************** CQUEUE
UNDERFLOW************** \n");
return(-1);
}
else{
item=cque[f];
if(f==r){
f=r=-1;
}
else
f=(f+1)%size;
return(item);
}
}
int cquefull()
{
if((f==r+1)|(f==0&&r==size-1))
return 1;
return 0;
}
int cqueempty()
{
if(f==-1)
return 1;
return 0;
}
display()
{
int i;
if(cqueempty())
printf("\n *******QUEUE EMPTY******** \n");
else
printf("front[%d]->",f);
for(i=f;i!=r;i=(i+1)%size)
printf("\n%d",cque[i]);
printf("\n%d",cque[i]);
printf("\n<-[%d]rear",r);
}
Double ended queue:
The stack has only one end and can be used alternately to insert and delete
elements. On the other hand, the double ended queue has two ends, front and
rear. The front end is used to remove element and rear end is used to insert
the elements. Here in the double ended queues, insertion and deletion can be
performed from both rear and front end; therefore it is called as double ended
queue and in short dqueue.
PROGRAM 2: PROGRAM TO IMPLEMENT DOUBLE ENDED QUEUE
#include<stdio.h>
#include<stdlib.h>
#define Q_SIZE 5
void insert_rear(int item ,int
*rear,int q[])
{
if(*rear==Q_SIZE-1) /* checks
wheather queue is empty or not*/
{
printf("\n *** queue is
overflow ***");
return ;
}
q[++(*rear)]=item; /*
inserting the element*/
}
int delete_front(int *front,int
*rear,int q[])
{
if(*front>*rear)
return -1; /*returns -1 if queue is empty*/
return q[(*front)++];
}
void insert_front(int item,int
*rear,int *q,int *front) //insert
function at front end
{
int i;
if(*front==0) {
*rear=*rear+1;
for(i=*rear-1;i>=*front;i--)
q[i+1]=q[i];
q[*front]=item;
}
else
*front--;
q[*front]=item;
}
int delete_rear(int *front,int
*rear,int *q //delete function at rear
{
int i;
if(*front>*rear) {
return;
}
else
return q[(*rear)--];
if (*front >*rear) {
*front=0,*rear=-1;
}
}
void display(int front ,int
rear,int q[]) //display function
{
int i;
if(front >rear) /* checks
wheather queue is empty or not*/
{
printf("\n ***queue empty***");
return ;
}
printf("\n ************CONTENTS OF QUEUE ARE*************
"); for(i=front
;i<=rear;i++)
{
printf("\n %d",q[i]);
}
}
void main()
{
int i;
int choice;
int item;
int df_item;
int dr_item;
int front;
int rear;
int q[Q_SIZE];
front=0;
rear=-1;
for(;;)
{
printf("\n 1:insert AT rear END ");
printf("\n 2:delete AT rear END
");
printf("\n 3:insert AT front
END");
printf("\n 4:delete AT
front END");
printf("\n 5: display ");
printf("\n 6: exit ");
printf("\n ENTER THE CHOICE \n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\n ENETR THE
ELEMENT TO BE INSERTED AT REAR END \n ");
scanf("%d",&item);
insert_rear(item,&rear,q);
break;
case 2:
dr_item=delete_rear(&front,&rear,q);
if(dr_item==-1)
printf("\n *************QUEUE
underflow**************");
else
printf("\n *********DELETED ITEM IS =%d
*************",dr_item);
break;
case 3:printf("\n ENETR tHE ELEMENT
TO BE INSERTED AT FRONT END \n ");
scanf("%d",&item);
insert_front(item,&rear,q,&front);
break;
case 4:
df_item=delete_front(&front,&rear,q);
if(df_item==-1)
printf("\n **************QUEUE underflow
***********");
else
printf("\n ***********DELETED
ITEM IS =%d **********",df_item);
break;
case 5:display(front,rear,q);
break;
case 6: exit(0);
}
}
}
PROGRAM 3:
PROGRAM TO IMPLEMENT STACK
#include<stdio.h>
//header file
#include<stdlib.h> //header
file
#define STACK_SIZE 3
//defining stack size
int top;
int s[10]; //defining array size
int item;
void push()
{
if(top==STACK_SIZE-1)
{
printf("___________STACK
OVERFLOW____________\n");
return;
}
top=top+1;
s[top]=item;
}
int pop()
{
int item_deleted;
if(top==-1)
return (0);
item_deleted=s[top--];
top=top-1;
return item_deleted;
}
void display()
{
int i;
if(top==-1)
{
printf("__________________STACK
IS EMPTY__________________ \n");
return;
}
printf("___________________CONTENT
OF STACK________________\n");
for(i=0;i<=top;i++){
printf("%d\n",s[i]);
}
}
void main()
{
int item_deleted,choice;
top=-1;
for(;;)
{
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY\n");
printf("4.EXIT\n");
printf("enter your choice
\n");
scanf("%d",&choice);
//using switch conditon
switch(choice)
{
case 1:printf("enter the
item to be inserted \n");
scanf("%d",&item);
push();
break;
case 2:item_deleted=pop();
if(item_deleted==0)
printf("_______________STACK IS
EMPTY_______________\n");
else
printf(" ITEM_DELETED
=%d\n",item_deleted);
break;
case 3:display();
break;
default:
exit(0);
}
}
}
OUTPUT:
No comments:
Post a Comment
we are hear to discuss your queries ,so please feel free to ask any of your queries.