Your Ad Here

Thursday, July 5, 2007

Circular Queue

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:
  1. 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
  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 */

17 comments:

Anonymous said...

Nice job.

Anonymous said...

Yes,it's really...,really...too good........
-G.P.Sharma

levygreen23 said...

Askum,,,,
Thx ya artikelnya bermanfaat banget,,,,,
:)

Anonymous said...

Thank you so very much for the program on circular queue. It was of great help to me.

Anonymous said...

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.

3afshiko said...

not bad but comlexe i can solve it in easly way :P

Tahir Raf said...

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

Anonymous said...

Do you keep always one slot unallocated?

Anonymous said...

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

Anonymous said...

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.

indra said...

previous sorry .. how about J2ME programs are reading java / lang / nullpointer exception .. what it means .. please answer via email muhienj90@gmail.com.

arooj fatima said...

nice bt plz post it in easy way so that i can understand properly .....................

VEB said...

i need more....

bolso103 said...

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

Anonymous said...

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

anth0ny989 said...

its not 8 to be removed first, its seven, i think your implementation is wrong.

Anonymous said...

is it applicable in c++ ?

Your Ad Here