Hi everyone, I have to implement a circular queue using linked list here.
We imagine a queue in a circular shape where we break at a point such that now it has 2 ends
Now we have to perform insertion and deletion at both ends one at a time
I was able to perform this functionality below
Now i have to assume this queue has a size 5 , and if i insert the 6th element from any end left or right, the element on the other end should get deleted. I am unable to perform this task here efficiently.
Can anyone help me with this
For ex. the queue is 4 5 6 7 8 .....now if i insert 9 on the right end the new queue shud be 5 6 7 8 9
and vice-versa
/*Circular Queue implementation using linked list
Written by Srinivas Kolli
Date- 14-07-2012 */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node
{
struct node *lptr;
int info;
struct node *rptr;
}
*start=NULL,*last=NULL;
// Insert from Left End
void insert_front()
{
struct node *n;
n=(struct node*)malloc(sizeof(struct node));
if(n==NULL)
{
cout<<"\nOverflow\n";
getch();
}
if(n>=5)
{
delete_end();
}
else
{
cout<<"Item=";
scanf("%d",&n->info);
n->lptr=NULL;
if(start==NULL)
{
start=n;
last=n;
start->rptr=NULL;
}
else
{
n->rptr=start;
start->lptr=n;
start=n;
}
}
}// End of Insert from Left
//Insert from Right End
void insert_end()
{
struct node *n;
n=(struct node*)malloc(sizeof(struct node));
if(n==NULL)
{
cout<<"Overflow\n";
getch();
}
else
{
cout<<"Item=";
scanf("%d",&n->info);
n->rptr=NULL;
if(start==NULL)
{
start=n;
start->lptr=NULL;
last=n;
}
else
{
last->rptr=n;
n->lptr=last;
last=n;
}
}
} // End of Insert from Right
//Insert in Between Nodes
void insert_between()
{
struct node *n,*save;
int k,pos;
char o;
n=(struct node*)malloc(sizeof(struct node));
if(n==NULL)
{
cout<<"Overflow\n";
getch();
}
else
{
cout<<"Item=";
scanf("%d",&n->info);
cout<<"Enter the position ---> ";
scanf("%d",&pos);
if(start==NULL && pos>1)
{
printf("\nYou can insert data only at the first position\
as list is empty......\n");
cout<<"Do you want insert at first position ? ---> ";
scanf("%c",&o);
if(o=='y'||o=='Y')
{
start=n;
n->rptr=NULL;
n->lptr=NULL;
last=n;
}
else
{
exit(0);
}
}
else
{
save=start;
k=1;
while(save!=NULL && k<pos-1)
{
save=save->rptr;
k++;
}
if(save==last&&k==pos-1)
{
n->lptr=last;
last->rptr=n;
last=n;
}
else
{
save->rptr->lptr=n;
save->rptr->lptr->lptr=save;
save->rptr->lptr->rptr=save->rptr;
save->rptr=n;
}
}
}
}//End of Insert in between
// Delete from between
void delete_between()
{
struct node *save,*temp;
int pos,k;
if(start==NULL)
{
cout<<"Underflow\n";
exit(0);
}
else
{
cout<<"Give the position ---> ";
scanf("%d",&pos);
if(start->rptr==NULL)
{
save=start;
start=NULL;
last=NULL;
free(save);
}
else
{
k=1;
save=start;
while(save!=NULL && k<pos-1)
{
save=save->rptr;
k++;
}
if(start==last)
{
save=last;
last=last->lptr;
last->rptr=NULL;
}
else
{
temp=save->rptr;
save->rptr->rptr->lptr=save;
save->rptr=save->rptr->rptr;
free(temp);
}
}
}
}//End of Delete in between
// Delete from Left end
void delete_front()
{
struct node *save;
if(start==NULL)
{
cout<<"Empty List\n";
getch();
}
else
{
save=start;
start=start->rptr;
start->lptr=NULL;
free(save);
}
}//End of Delete from front
// Delete from the Right End
void delete_end()
{
struct node *save;
if(start==NULL)
{
cout<<"Empty List\n";
getch();
}
else
{
if(start->rptr==NULL)
{
save=start;
start=NULL;
free(save);
}
else
{
save=last;
last=last->lptr;
last->rptr=NULL;
free(save);
}
}
}//End of Delete frm Right End
// Display the Elements
void view()
{
struct node *save;
if(start==NULL)
{
cout<<"No data available\n";
getch();
}
else
{
save=start;
while(save!=NULL)
{
printf("%d ",save->info);
save=save->rptr;
}
}
}// End of Display
// Main Function
int main()
{
int opinion,temp;
//clrscr();
do
{
cout<<"\nYou can do the following\n\n";
cout<<"1.Insert_front\n2.Insert_end\n3.Insert Between\n";
cout<<"4.Delete_front\n5.Delete_end\n6.Delete Between\n";
cout<<"7.View\n8.Exit\n";
cout<<"Opinion= ";
scanf("%d",&opinion);
switch(opinion)
{
case 1:insert_front();
view();
break;
case 2:insert_end();
view();
break;
case 3:insert_between();
view();
break;
case 4:delete_front();
view();
break;
case 5:delete_end();
view();
break;
case 6:
{
delete_between();
view();
break;
}
case 7:view();
break;
case 8:break;
default:cout<<"Wrong Choice\n";
}
}
while(opinion!=8) ;
getch();
}
// End of Main
