A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.
Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:
Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:
- if the "front" points where "rear" is pointing and the queue holds a not NULL value for it, then its a "queue overflow" state, so quit; else go to step-4.2
- insert the new value for the queue position pointed by the "rear"
Algorithm for deletion:-
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one
/****** C Program For Impelmetation Of Circular Queue *******/
#define MAX 5
struct queue
{
int arr[MAX];
int rear,front;
};
int isempty(struct queue *p)
{
if(p->front ==p->rear)
return 1;
else
return 0;
}
void insertq(struct queue *p,int v)
{
int t;
t = (p->rear+1)%MAX;
if(t == p->front)
printf("\nQueue Overflow\n");
else
{
p->rear=t;
p->arr[p->rear]=v;
}
}
int removeq(struct queue *p)
{
if(isempty(p))
{
printf("\nQueue Underflow");
exit(0);
}
else
{
p->front=(p->front + 1)%MAX;
return(p->arr[p->front]);
}
}
void main()
{
struct queue q;
char ch;
int no;
clrscr();
q.rear=q.front =0;
insertq(&q,7);
insertq(&q,10);
insertq(&q,12);
insertq(&q,15);
insertq(&q,8);
printf("\n%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
removeq(&q);
getch();
}
/************** OUTPUT ****************
Queue Overflow
7
10
12
15
Queue Underflow */
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one
/****** C Program For Impelmetation Of Circular Queue *******/
#define MAX 5
struct queue
{
int arr[MAX];
int rear,front;
};
int isempty(struct queue *p)
{
if(p->front ==p->rear)
return 1;
else
return 0;
}
void insertq(struct queue *p,int v)
{
int t;
t = (p->rear+1)%MAX;
if(t == p->front)
printf("\nQueue Overflow\n");
else
{
p->rear=t;
p->arr[p->rear]=v;
}
}
int removeq(struct queue *p)
{
if(isempty(p))
{
printf("\nQueue Underflow");
exit(0);
}
else
{
p->front=(p->front + 1)%MAX;
return(p->arr[p->front]);
}
}
void main()
{
struct queue q;
char ch;
int no;
clrscr();
q.rear=q.front =0;
insertq(&q,7);
insertq(&q,10);
insertq(&q,12);
insertq(&q,15);
insertq(&q,8);
printf("\n%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
removeq(&q);
getch();
}
/************** OUTPUT ****************
Queue Overflow
7
10
12
15
Queue Underflow */
17 comments:
Nice job.
Yes,it's really...,really...too good........
-G.P.Sharma
Askum,,,,
Thx ya artikelnya bermanfaat banget,,,,,
:)
Thank you so very much for the program on circular queue. It was of great help to me.
at first typedef struct queue cqueue;
then
int isEmpty(cqueue * q){
return(if(q->front==q->rear));
}
will also work.
menu driven the program.
otherwise good.
not bad but comlexe i can solve it in easly way :P
well this algo has a very big bug..
make a queue of size 3 and do this
insert(1);
insert(2);
insert(3); - At this line it will say FULL, which is wrong..
Do you keep always one slot unallocated?
i think it has no bug...consider f=r=0 nt pointing to queue n when R=1 it means 1 element has been inserted...so its fine this way
This could worked fine for me. You just have to remember to make MAX equal to one more than you actually want the queue to be able to hold since there's always one unallocated slot.
previous sorry .. how about J2ME programs are reading java / lang / nullpointer exception .. what it means .. please answer via email muhienj90@gmail.com.
nice bt plz post it in easy way so that i can understand properly .....................
i need more....
Hello,
I have to build a Message Queue System for the University, like Amazon SQS. Whe have n queues, p producers and q consumers. The idea: for example, we have 5 producers and 4 consumers for the queue 1. Messages are delivered from the queue to any consumer when they ask for them. On that moment, the message is setted as "unvisible" in order not to be transferred to other(s) consumer(s). Each consumer has x seconds to process the message. If that time is exceeded, the message is marked "visible" and re-enters to the head of the queue. If the message is processed before x seconds, it is deleted (the queue receives an ACK signal). Doing so, messages are never lost (system requirement).
Messages are in plain text and others like pdf, xml, etc. But they are small (no longer than 100KB). MIME is suggested, and the use of meta-information. The programming language should be C, and should use UNIX domain sockets (Linux operating system). Also, there will be an administrator who will manage the queues (creation, destruction, etc), using other IPC protocols like pipes and/or signals
My question is, what kind of implementation would you suggest for and why (linked list, circular buffer, etc)?
Thanks,
Gabriel
check for the condition when front is moving as you pop and after that push elements until queue full conditon occurs, it ll b showing up a small mistake....
its not 8 to be removed first, its seven, i think your implementation is wrong.
is it applicable in c++ ?
Post a Comment