FINAL PPT OF CIRCULAR QUEUE

Views:

Category: Education

CIRCULAR QUEUE

Presentation Transcript

CIRCULAR QUEUE

QUEUE:

QUEUE Also called as First-In-First-Out. It mean “Among the various Items the item that are pushed inside the BOX earliest of all will come of the box in the first time after getting processed. C D B A TICKET

QUEUE:

QUEUE The place of entrance is called REAR(R). The place of coming out is called FRONT(F). 1.Insert(A) 2.Insert(B) 3.Delete(A) A F R A B F R B F R

circular QUEUE

Circular Queue:

Circular Queue Use Linear Array to implement a queue . Waste of memory: The deleted elements can not be re-used. Solution: to use circular queue. Two implementations: Using n-1 space. Using n space + full tag

What is circular queue ?:

What is circular queue ? In circular queue, the elements are physically arranged in sequential manner but logically they are treated as they are circularly arranged.

In detail,:

In detail, The rear and front move about in clockwise direction. Circular queue is another form of a linear queue in which last position is connected to the first position of the list. It can be viewed as a mesh or loop of wire , in which the two ends of the wire are connected together. A circular queue is one in which the first element comes just after the last element.

In short ,:

In short , If all the elements are inserted properly and again deleted then the front and rear will show the same position. So we cannot insert and delete any element from the simple queue because the queue is already full. Hence we go for a circular queue.

In a circular queue,:

In a circular queue, The front will always be pointing to the first element. If front=rear , the queue is empty. Each time a new element is inserted into the queue the rear is incremented by one (rear=rear+ 1) Each time an element is deleted from the queue the value of front is incremented by one (front=front+ 1)

Circular queue v/s Linear queue:

Circular queue v/s L inear queue 1 . Linear queues by theory do not have a specific capacity and new elements can always be added to the queue; queues that have a fixed capacity are called bounded queues. In practical usage queues are bounded. 2. Circular queues have a fixed size, like bounded queues. 3. The end of a linear queue points to NULL indicating the end of the queue, while the end of a circular queue points to the beginning of the queue, thus completing the circle. 4. Linear queues do not allow overwriting of existing data. When the queue is full, new data cannot be inserted until old data is freed. Linear queues must pass both “Queue Empty” test before dequeue operation and “Queue Full” test before enqueue operation. 5.Circular queues are only required to pass “Queue Empty” test, and depending on the application the “Queue Full” test is optional. When new data is enqueued into a circular queue, the oldest data of the queue is overwritten.

Circular Queue:

Circular Queue   [ 4] [ 1] [ [ 4 ]     front = 0 front = 0 rear = 0 rear = 3 Can be seen as a circular queue J2 J1 J3  [ 2] 

Circular Queue:

Circular Queue Leave one empty space when queue is full Why? FULL QUEUE FULL QUEUE  [ 3] [ 2]   [ 4 ] [ 1]    [ 0] [5 ] front =0 rear = 5 front =4 rear =3 J2 J3 J1 J4 J5 J6 J5 J7 J8 J9 How to test when queue is empty ? How to test when queue is full ?

How it works ?:

How it works ? A circular queue first starts empty and of some predefined length. For example, this is a 7-element queue : Assume that a 1 is written into the middle of the queue (exact starting location does not matter in a circular queue ): Then assume that two more elements are added — 2 & 3 — which get appended after the 1:

PowerPoint Presentation:

If two elements are then removed from the queue, the oldest values inside the queue are removed. The two elements removed, in this case, are 1 & 2 leaving the queue with just 3: If the queue has 7 elements then it is completely full: A consequence of the circular queue is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In this case, two more elements — A & B — are added and they  overwrite  the 3 & 4 :

PowerPoint Presentation:

Finally, if two elements are now removed then what would be returned is  not  3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the queue with :

PowerPoint Presentation:

Implementation of Circular queue with (n-1) space used Routine to create an empty queue void create(queue*q) { q.front =-1; q.rear =-1; } 0 1 2 … n-1 R  R = ( R+1)MAXQ Queue (item, Q) Queue begin rear = (rear+1) MAXQ ; //rear moves forward; if rear = front QueueFull ; // Queue i s full. rear = rear-1 MAXQ; // rear back to the previous position; else Q[rear]=item; end;

Routine to check an empty queue:

Routine to check an empty queue int IsEmpty (queue*q) { if( q.front ==-1) return 1; else return 0; }

Routine to check if queue is full:

Routine to check if queue is full int IsFull (queue*q) { if( q.rear ==(q.rear+1)%MAXQ) return 1; else return 0; } F R eg :- R =4 q.rear =(4+1)%5 = (5)%5 = 0 F R 5 10 20 Q(0) Q(1) Q(2) Q(3) Q(4) 5 10 30 20 40 Q(0) Q(1) Q(2) Q(3) Q(4)

Routine to insert an element in queue:

Routine to insert an element in queue void insert(queue* q,int x) { if( IsFull (q)) { printf (“Queue Overflow”); return; } if( q.front ==-1) { q.front =0; q.rear =0; } q.rear =(q.rear+1)%MAXQ; q.item [ q.rear ]=x; }

PowerPoint Presentation:

Eg :- q.rear =(q.rear+1)%MAXQ =(3+1)%6 =4%6 =4 11 44 22 33       rear=3 22 33 25 11  rear=4 front=0 front=0      The new element is inserted at 4 th position. NOTE:- If front=rear(f=r), then queue is full .

Routine to delete an element:

Routine to delete an element int delete(queue*q) { int x; if( IsEmpty (q)) printf (“Queue Empty”); exit (0); } x= q.items [ q.front ]; if( q.front == q.rear ) { q.front =-1; q.rear =-1; else q.front =(q.front+1)%MAXQ; return x; }

Eg:-:

Eg :- q.front =(q.front+1)%MAX =(0+1)%5 =1%5 =1 [ 4 ] [ 3 ] 44 11 [ 0 ] [ 2 ] [ 1 ] 33 22 rear=3 front=0 f=(f+1)%MAXQ [ 4 ] rear=3 front=1 [ 2 ] [ 1 ] [ 3 ] 44 [ 0 ] 33 22 It is deleted from Q,position and front is at Q position

Program of circular queue:

Program of circular queue #include< stdio.h > # include< conio.h > # define maxq 100 typedef struct { int front,rear ; int item[ maxq ]; }queue; int ISEMPTY(queue*q); int ISFULL(queue*q); void insert (queue*,int); int delete(queue*); void display(queue*); queue q;

PowerPoint Presentation:

void main () { int x; char ch ='1'; clrscr (); q.rear =-1; q.front =0; while( ch !='4') { printf("\n 1-inserted"); printf("\n 2-delete"); printf("\n 3-display"); printf("\n 4-quit"); printf("\n\n enter your choice"); ch = getchar (); switch( ch )

PowerPoint Presentation:

{ case'1': printf("\n enter element to be inserted"); scanf ("% d",&x ); insert(& q,x ); break; case'2': x=delete(&q); printf("\n enter element to be deleted %d\ n",x ); break; case'3': display(&q); break; case'4': break; default: printf("\n wrong choice ! try again"); } } }

PowerPoint Presentation:

int ISEMPTY(queue* q) { if(q->front==-1) return 1; else return 0; } int ISFULL(queue*q) { if(q->front==(q->rear)% maxq ) return 1; else return 0; }

PowerPoint Presentation:

void insert(queue* q,int x) { if(ISFULL(q)) printf("overflow"); if(q->front==-1) { q->front=0; q->rear=0 ; } q->rear=(q->rear)% maxq ; q->item[q->rear]=x; } int delete(queue*q) { int x; if(ISEMPTY(q)) { printf("queue is empty"); exit (0); }

PowerPoint Presentation:

x=q->item[q->front]; if(q->front==q->rear) { q->front=-1; q->rear=-1; } else q->front=(q->front+1)% maxq ; return x; } void display(queue*q) { int i; if(ISEMPTY(q)) { printf("stack is empty"); return; }

PowerPoint Presentation:

printf("\n element in queue are \n"); for(i=q-> front;i <=q-> rear;i --) printf("%d\ n",q ->item [ i ]); }

OUTPUT:-

Made by S.Y.C.O(II SHIFT) SS12CO001 – SS12C0010:

Made by S.Y.C.O(II SHIFT) SS12CO001 – SS12C0010 