In a standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue
Circular queue is a linear data structure. It follows FIFO principle.
Circular Queue can be created in three ways they are
· Using single linked list
· Using double linked list
· Using arrays
Using single linked list:
It is an extension for the basic single linked list. In circular linked list Instead of storing a Null value in the last node of a single linked list, store the address of the 1st node (root) forms a circular linked list. Using circular linked list it is possible to directly traverse to the first node after reaching the last node.
The following figure shows circular single linked list:
Using double linked list
In double linked list the right side pointer points to the next node address or the address of first node and left side pointer points to the previous node address or the address of last node of a list. Hence the above list is known as circular double linked list.
The following figure shows Circular Double linked list :-
Algorithm for creating circular linked list :-
Step 1) start
Step 2) create anode with the following fields to store information and the address of the next node.
Structure node
begin
int info
pointer to structure node called next
end
Step 3) create a class called clist with the member variables of pointer to structure nodes called root, prev, next and the member functions create ( ) to create the circular linked list and display ( ) to display the circular linked list.
Step 4) create an object called 'C' of clist type
Step 5) call C. create ( ) member function
Step 6) call C. display ( ) member function
Step 7) stop
Algorithm for create ( ) function:-
Step 1) allocate the memory for newnode
newnode = new (node )
Step 2) newnode->next=newnode. // circular
Step 3) Repeat the steps from 4 to 5 until choice = 'n'
Step 4) if (root=NULL)
root = prev=newnode // prev is a running pointer which points last node of a list
else
newnode->next = root
prev->next = newnode
prev = newnode
Step 5) Read the choice
Step 6) return
Algorithm for display ( ) function :-
Step 1) start
Step 2) declare a variable of pointer to structure node called temp, assign root to temp
temp = root
Step 3) display temp->info
Step 4) temp = temp->next
Step 5) repeat the steps 6 until temp = root
Step 6) display temp info
Step 7) temp=temp->next
Step 8) return
Using array
In arrays the range of a subscript is 0 to n-1 where n is the maximum size. To make the array as a circular array by making the subscript 0 as the next address of the subscript n-1 by using the formula subscript = (subscript +1) % maximum size. In circular queue the front and rear pointer are updated by using the above formula.
The following figure shows circular array:
Algorithm for Enqueue operation using array
Step 1. start
Step 2. if (front == (rear+1)%max)
Print error "circular queue overflow "
Step 3. else
{ rear = (rear+1)%max
Q[rear] = element;
If (front == -1 ) f = 0;
}
Step 4. stop
Algorithm for Dequeue operation using array
Step 1. start
Step 2. if ((front == rear) && (rear == -1))
Print error "circular queue underflow "
Step 3. else
{ element = Q[front]
If (front == rear) front=rear = -1
Else
Front = (front + 1) % max
}
Step 4. stop
Simple queue is a linear queue having front & rear var to insert & delete elements from the list.But there is a boundary that we have to insert at rear & have delete from front.For this reason instead of having space in the queue if there is a single element in the rear,the queue is full.the other space is wasted.To utilize space properly,circular queue is derived.In this queue the elements are inserted in circular manner.So that no space is wasted at all.
Add weights to the elements of the queue and use an algorithm to sort the queue every time an element is added.
What is the difference between linear and circular queue? In: http://wiki.answers.com/Q/FAQ/2545-37 [Edit categories]The Queue by Default is Linear, it would be termed as Circular if the Last Element of the Queue pointsto the first element of the List
It doesn't.
The Method To Add an element in Circular Queue # define MAXQUEUE 100 struct queue{ int items[MAXQUEUE]; int front, rear; } struct queue q; q.front=q.rear=MAXQUEUE -1; void ENQ(struct queue *pq, int x) { /* make room for new element*/ if(pq ->rear = MAXQUEUE - 1) pq-> rear = 0; else (pq->rear)++; /* check for overflow */ if(pq ->rear==pq->front) { printf("queue overflow); exit(1); } pq->items[pq->rear]=x; return; }/* end of ENQ*/ A Method to Delete an element from Circular Queue int DQ(struct queue *pq) { if(pq-> rear == pq-> front) { printf("queue underflow"); exit(1); }/*end if*/ if(pq->front = = MAXQUEUE-1) pq->front=0; else (pq->front)++; return(pq->items[pq->front]);
Simple queue is a linear queue having front & rear var to insert & delete elements from the list.But there is a boundary that we have to insert at rear & have delete from front.For this reason instead of having space in the queue if there is a single element in the rear,the queue is full.the other space is wasted.To utilize space properly,circular queue is derived.In this queue the elements are inserted in circular manner.So that no space is wasted at all.
Circular queue is a linear data structure that follows the First In First Out principle. A re-buffering problem often occurs for each dequeue operation in a standard queue data structure. This is solved by using a circular queue which joins the front and rear ends of a queue.
Add weights to the elements of the queue and use an algorithm to sort the queue every time an element is added.
|
For the Complete Implementation of Circular Queue Check out www.codeuniverse.tk
circular queue
In circular queue the memory of the deleted process can be used by some other new process..
A circular queue is similar to the normal queue with the difference that queue is circular queue ; that is pointer rear can point to beginning of the queue when it reaches at the end of the queue. Advantage of this type of queue is that empty location let due to deletion of elements using front pointer can again be filled using rear pointer. There are 2 conditions for queue full if queue is implemented using arrays. First condition is Front = 1 and Rear = N Second condition is Front = Rear + 1
What is the difference between linear and circular queue? In: http://wiki.answers.com/Q/FAQ/2545-37 [Edit categories]The Queue by Default is Linear, it would be termed as Circular if the Last Element of the Queue pointsto the first element of the List
A circular queue uses the same conventions as that of linear queue. Using Front will always point one position counterclockwise from the first element in the queue.
It doesn't.
The Method To Add an element in Circular Queue # define MAXQUEUE 100 struct queue{ int items[MAXQUEUE]; int front, rear; } struct queue q; q.front=q.rear=MAXQUEUE -1; void ENQ(struct queue *pq, int x) { /* make room for new element*/ if(pq ->rear = MAXQUEUE - 1) pq-> rear = 0; else (pq->rear)++; /* check for overflow */ if(pq ->rear==pq->front) { printf("queue overflow); exit(1); } pq->items[pq->rear]=x; return; }/* end of ENQ*/ A Method to Delete an element from Circular Queue int DQ(struct queue *pq) { if(pq-> rear == pq-> front) { printf("queue underflow"); exit(1); }/*end if*/ if(pq->front = = MAXQUEUE-1) pq->front=0; else (pq->front)++; return(pq->items[pq->front]);