Circular Queue
It's going to be a static implementation of queues and good for limited elements to be handled, as you know array size has to be pre-defined and can't be changed dynamically. Here, every time you insert a new element in the queue you'll check for the queue 'overflow' condition as we are using a static array to implement the queue.
Here, I'll take rear as -1 and front as 0 when the Queue is empty.
Algorithm:-
Step-1: Increment the 'rear' by 1
Step-2: Check for the 'queue overflow' condition. If queue not overflowing then go to step-3 else say "queue overflow" and quit
Step-3: Put the new element at the position pointed by 'rear'
C implementation:- static int queue[max]; int front = 0, rear = -1;
..
.. insert(int new)
{
rear = rear + 1; if(rear < max) queue[rear] = new; else printf("Queue overflow");
}
When an element leaves the queue the 'front' gets incremented by one. Every time before deletion we'll check for the 'queue empty' condition. If the queue is not empty, put a NULL value at the position pointed by 'front' and increment the value of 'front' by 1.
Algorithm:-
Step-1: If the queue is empty then quit else go to step-2
Step-2: Put a NULL value at the position pointed by 'front'. Increment the 'front' by 1.
C implementation:- static int queue[max]; int front = 0, rear = -1; /*when the queue is empty*/
..
.. int delete( )
{
int del_val =0; /*holds the deleted value*/ if(front > rear) printf("Queue empty"); else { del_val = queue[front]; queue[front] = NULL; /*this represents that the element has been deleted*/ front = front + 1; } return(del_val); }
Haven't you realised that the regular, static queues we saw have a very big drawback that once the queue is FULL, even though we delete few elements from the "front" and relieve some occupied space, we are not able to add anymore elements, as the "rear" has already reached the Queue's rear most position. The solution lies in
Here, I'll take rear as -1 and front as 0 when the Queue is empty.
Algorithm:-
Step-1: Increment the 'rear' by 1
Step-2: Check for the 'queue overflow' condition. If queue not overflowing then go to step-3 else say "queue overflow" and quit
Step-3: Put the new element at the position pointed by 'rear'
C implementation:- static int queue[max]; int front = 0, rear = -1;
..
.. insert(int new)
{
rear = rear + 1; if(rear < max) queue[rear] = new; else printf("Queue overflow");
}
When an element leaves the queue the 'front' gets incremented by one. Every time before deletion we'll check for the 'queue empty' condition. If the queue is not empty, put a NULL value at the position pointed by 'front' and increment the value of 'front' by 1.
Algorithm:-
Step-1: If the queue is empty then quit else go to step-2
Step-2: Put a NULL value at the position pointed by 'front'. Increment the 'front' by 1.
C implementation:- static int queue[max]; int front = 0, rear = -1; /*when the queue is empty*/
..
.. int delete( )
{
int del_val =0; /*holds the deleted value*/ if(front > rear) printf("Queue empty"); else { del_val = queue[front]; queue[front] = NULL; /*this represents that the element has been deleted*/ front = front + 1; } return(del_val); }
Haven't you realised that the regular, static queues we saw have a very big drawback that once the queue is FULL, even though we delete few elements from the "front" and relieve some occupied space, we are not able to add anymore elements, as the "rear" has already reached the Queue's rear most position. The solution lies in