Prerequisite – Queues
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.
In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we can not insert the next element even if there is a space in front of queue.
Operations on Circular Queue:
- Front: Get the front item from queue.
- Rear: Get the last item from queue.
- enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.
- Steps:
- Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
- If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.
- deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.
- Steps:
- Check whether queue is Empty means check (front==-1).
- If it is empty then display Queue is empty. If queue is not empty then step 3
- Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.
C++
// C or C++ program for insertion and // deletion in Circular Queue #include<bits/stdc++.h> using namespace std; struct Queue { // Initialize front and rear int rear, front; // Circular Queue int size; int *arr; Queue( int s) { front = rear = -1; size = s; arr = new int [s]; } void enQueue( int value); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue( int value) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { printf ( "
Queue is Full" ); return ; } else if (front == -1) /* Insert First Element */ { front = rear = 0; arr[rear] = value; } else if (rear == size-1 && front != 0) { rear = 0; arr[rear] = value; } else { rear++; arr[rear] = value; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { printf ( "
Queue is Empty" ); return INT_MIN; } int data = arr[front]; arr[front] = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } // Function displaying the elements // of Circular Queue void Queue::displayQueue() { if (front == -1) { printf ( "
Queue is Empty" ); return ; } printf ( "
Elements in Circular Queue are: " ); if (rear >= front) { for ( int i = front; i <= rear; i++) printf ( "%d " ,arr[i]); } else { for ( int i = front; i < size; i++) printf ( "%d " , arr[i]); for ( int i = 0; i <= rear; i++) printf ( "%d " , arr[i]); } } /* Driver of the program */ int main() { Queue q(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); // Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue printf ( "
Deleted value = %d" , q.deQueue()); printf ( "
Deleted value = %d" , q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20); return 0; } |
Python 3
class CircularQueue(): # constructor def __init__( self , size): # initializing the class self .size = size # initializing queue with none self .queue = [ None for i in range (size)] self .front = self .rear = - 1 def enqueue( self , data): # condition if queue is full if (( self .rear + 1 ) % self .size = = self .front): print ( " Queue is Full
" ) # condition for empty queue elif ( self .front = = - 1 ): self .front = 0 self .rear = 0 self .queue[ self .rear] = data else : # next position of rear self .rear = ( self .rear + 1 ) % self .size self .queue[ self .rear] = data def dequeue( self ): if ( self .front = = - 1 ): # codition for empty queue print ( "Queue is Empty
" ) # condition for only one element elif ( self .front = = self .rear): temp = self .queue[ self .front] self .front = - 1 self .rear = - 1 return temp else : temp = self .queue[ self .front] self .front = ( self .front + 1 ) % self .size return temp def display( self ): # condition for empty queue if ( self .front = = - 1 ): print ( "Queue is Empty" ) elif ( self .rear > = self .front): print ( "Elements in the circular queue are:" , end = " " ) for i in range ( self .front, self .rear + 1 ): print ( self .queue[i], end = " " ) print () else : print ( "Elements in Circular Queue are:" , end = " " ) for i in range ( self .front, self .size): print ( self .queue[i], end = " " ) for i in range ( 0 , self .rear + 1 ): print ( self .queue[i], end = " " ) print () if (( self .rear + 1 ) % self .size = = self .front): print ( "Queue is Full" ) # Driver Code ob = CircularQueue( 5 ) ob.enqueue( 14 ) ob.enqueue( 22 ) ob.enqueue( 13 ) ob.enqueue( - 6 ) ob.display() print ( "Deleted value = " , ob.dequeue()) print ( "Deleted value = " , ob.dequeue()) ob.display() ob.enqueue( 9 ) ob.enqueue( 20 ) ob.enqueue( 5 ) ob.display() # This code is contributed by AshwinGoel |
Output:
Elements in Circular Queue are: 14 22 13 -6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 13 -6 Elements in Circular Queue are: 13 -6 9 20 5 Queue is Full
Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) as there is no loop in any of the operation.
Applications:
- Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
- Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
- CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments