Circular queue is a queue in which all elements are connected to form a circular. Circular queue can be implemented with array and linked list. In array implementation, the front and rear wrap around (modulo operation) to the beginning of the array. In linked list implementation, the last node links back to the front node. In this post, circular queue implementation is using array.
Table of Content
Map of queue implementations
Part 1 – Queue implementation with linked list
Part 2 – Circular queue implementation with array
Part 3 – Circular linked list (Circular queue)
Part 4 – Doubly linked list (Deque)
Enqueue in circular queue implementation
First we declare an array. In Java, if you use array (not ArrayList), you have to specify the maxSize. If the array reaches the maxSize, you cannot add more element. The frontIndex and rearIndex is the index of the front element and rear element. When the queue is empty, they are -1. The length is to keep track of the numbers of elements in the queue.
To enqueue is to add element at the rear. The rearIndex is increased by 1. If the rearIndex exceeds the maxSize, we use modulo operation (or “mod”, “%”) to get the new rearIndex with the maxSize range.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class CircularQueueArray<T> { private T[] queueArray; private int maxSize; // Size of Circular Queue private int frontIndex, rearIndex; private int length = 0; //constructor, Time O(1), Space O(1) @SuppressWarnings("unchecked") public CircularQueueArray(int size) { maxSize = size; frontIndex = -1; rearIndex = -1; queueArray = (T[])new Object[maxSize]; } //Add at the rear, Time O(1), Space O(1) public void enqueue(T value) { if (isFull()) { System.out.println("Queue is full, cannot enqueue "+ value); return; } if (frontIndex == -1) //empty frontIndex = 0; rearIndex = (rearIndex + 1) % maxSize; queueArray[rearIndex] = value; length++; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class CircularQueueArray { //constructor, Time O(1), Space O(1) constructor(size) { this.maxSize = size; this.frontIndex = -1; this.rearIndex = -1; this.queueArray = []; this.length = 0; } //Add at the rear, Time O(1), Space O(1) enqueue(value) { if (this.isFull()) { console.log("Queue is full, cannot enqueue "+ value); return; } if (this.frontIndex == -1) this.frontIndex = 0; this.rearIndex = (this.rearIndex + 1) % this.maxSize; this.queueArray[this.rearIndex] = value; this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class CircularQueueArray: #constructor, Time O(1), Space O(1) def __init__(self, size): self.maxSize = size self.queueArray = [None] * size self.frontIndex = self.rearIndex = -1 self.length = 0 #Add at the rear, Time O(1), Space O(1) def enqueue(self, value): if self.isFull(): #full print("The circular queue is full, cannot enqueue " + str(value)) return if (self.frontIndex == -1): #empty self.frontIndex = 0 self.rearIndex = (self.rearIndex + 1) % self.maxSize self.queueArray[self.rearIndex] = value self.length += 1 |
Doodle
Dequeue in circular queue implementation
The dequeue operation is to remove the front node from the queue. First we check whether the queue is empty. If it is empty, the method should return. We also check whether there is only one element in the queue. If it is, we should reset the frontIndex and rearIndex to -1 after removing the last element.
To dequeue, we increases the frontIndex by 1. Like enqueue, if the frontIndex exceeds the maxSize, we have to put the element back to index 0. We use modulo operation (or “mod”, “%”) to get the new frontIndex. Please note to dequeue element, we only update the frontIndex. The original value stays in the spot until it is replaced with new value.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Remove from the front, Time O(1), Space O(1) public T dequeue() { if (isEmpty()) { System.out.println("Queue is empty"); return null; } T item = queueArray[frontIndex]; if (frontIndex == rearIndex) { //last one, reset frontIndex = -1; rearIndex = -1; } else { frontIndex = (frontIndex + 1) % maxSize; } length--; return (item); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Remove from the front, Time O(1), Space O(1) dequeue() { if (this.isEmpty()) { console.log("Queue is empty"); return null; } var item = this.queueArray[this.frontIndex]; if (this.frontIndex == this.rearIndex) { //one element left this.frontIndex = -1; this.rearIndex = -1; } else { this.frontIndex = (this.frontIndex + 1) % this.maxSize; } this.length--; return (item); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Remove from the front, Time O(1), Space O(1) def dequeue(self): if self.isEmpty(): print("The circular queue is empty, cannot dequeue") return item = self.queueArray[self.frontIndex] if (self.frontIndex == self.rearIndex): #one item left self.frontIndex = -1 self.rearIndex = -1 return item else: self.frontIndex = (self.frontIndex + 1) % self.maxSize self.length -= 1 return item |
Doodle
Peek
Peek is to return the value at the firstIndex. The same as dequeue, we should check whether the queue is empty. If it is not empty, return the value.
Java
|
1 2 3 4 5 6 7 8 |
//Return front value, Time O(1), Space O(1) public T peek() { if (isEmpty()) { System.out.println("Queue is empty"); return null; } return queueArray[frontIndex]; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return front value, Time O(1), Space O(1) peek() { if (this.isEmpty()) { console.log("Queue is empty"); return null; } return this.queueArray[this.frontIndex]; } |
Python
|
1 2 3 4 5 6 |
#Return front value, Time O(1), Space O(1) def peek(self): if self.isEmpty(): print("The circular queue is empty, cannot dequeue") return return self.queueArray[self.frontIndex] |
Print
Print is to print all elements in the circular queue. Starting from the frontIndex, a for loop or while loop is used to iterate through each slots till to the rearIndex. Like enqueue and dequeue, the index i is increased by 1, then mod the maxSize.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Print all, Time O(n), Space O(1), n is number of items in queue public void print() { if (isEmpty()) { System.out.println("Queue is empty"); return; } System.out.print("Circular queue: "); int i; for (i = frontIndex; i != rearIndex; i = (i + 1) % maxSize) System.out.print(queueArray[i] + " "); System.out.println(queueArray[i]); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Print all, Time O(n), Space O(1), n is number of items in queue print() { if (this.isEmpty()) { console.log("Queue is empty"); return; } var str = "Queue: "; var i; for (i = this.frontIndex; i !=this.rearIndex; i = (i + 1) % this.maxSize) str += this.queueArray[i] + " "; str += this.queueArray[i]; console.log(str); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Print all, Time O(n), Space O(1), n is number of items in queue def print(self): if self.isEmpty(): print("The circular queue is empty") return print("Circular queue: ", end="") i = self.frontIndex while i != self.rearIndex: print(str(self.queueArray[i]) , end=" ") i = (i + 1) % self.maxSize print(self.queueArray[i]) |
Free download
Download circular queue implementation in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python
When to implement circular queue using array and when to use linked list?
When there is a lot dequeue and enqueue at the same time, it is better to use array. The discard space can be reused. This makes better use of memory space. When you cannot predict how long the circular queue will be, you use circular linked list. It is flexible to expand or shrink.
What is the formula of circular queue using array?
In the array implementation, you declare frontIndex and rearIndex to keep track the position of the front and rear element. They both start at -1. To wrap around so that the frontIndex and rearIndex are within the range of the array length, you use modulo operator %. To enqueue, the formula is rearIndex = (rearIndex + 1) % maxSize. To dequeue, it is frontIndex = (frontIndex + 1) % maxSize.