# Circular Queue | Set 1 (Introduction and Array Implementation)

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:

1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
2. 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:

1. Check whether queue is Empty means check (front==-1).
2. If it is empty then display Queue is empty. If queue is not empty then step 3
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 ` `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:

1. Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
2. 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.
3. 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.

This article is attributed to GeeksforGeeks.org

## tags:

Queue circular-array Queue

code

load comments