A circular queue is a queue in which all elements are connected to form a circular. A circular queue can be implemented with an array or a linked list. In the array implementation, the index of the rear element wraps around to the beginning of the array. In this post, you are going to implement a circular queue using an array in Java, JavaScript and Python.
Table of Content
Enqueue
First, you declare an array. maxSize is the max length of the array. frontIndex and rearIndex are the indices of the front and rear elements respectively. When the queue is empty, they are -1. length is to keep track of the number of elements in the queue.
Enqueue is to add an element at the back and increase rearIndex by 1. If rearIndex exceeds maxSize, you use modulo operation (“mod” or “%”) to get a new rearIndex within maxSize.
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 28 29 30 31 32 33 | public class CircularQueueArray<T> { private T[] queue; 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; queue = (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; queue[rearIndex] = value; length++; } // Check full, Time O(1), Space O(1) private boolean isFull() { return (rearIndex + 1) % maxSize == frontIndex; } |
Javascript
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 28 | class CircularQueueArray { //constructor, Time O(1), Space O(1) constructor(size) { this.maxSize = size; this.frontIndex = -1; this.rearIndex = -1; this.queue = []; 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.queue[this.rearIndex] = value; this.length++; } // Check if the queue is full, Time O(1), Space O(1) isFull() { return (this.rearIndex + 1) % this.maxSize == this.frontIndex; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class CircularQueueArray: #constructor, Time O(1), Space O(1) def __init__(self, size): self.maxSize = size self.queue = [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.is_full(): #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.queue[self.rearIndex] = value self.length += 1 #Check full, Time O(1), Space O(1) def is_full(self): return (self.rearIndex + 1) % self.maxSize == self.frontIndex |
Dequeue in circular queue implementation
The dequeue operation is to remove the front element from a queue. First, you check whether the queue is empty. If it is empty, the method should return. You also check whether there is only one element in the queue. If it is, you should reset frontIndex and rearIndex to -1 after removing the last element.
To dequeue, you increase frontIndex by 1. If frontIndex exceeds maxSize, you use the modulo operation to set frontIndex within maxSize. Please note: to dequeue elements, you only update frontIndex. The element in the original frontIndex stays in the spot until it is replaced by a new value.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //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 = queue[frontIndex]; if (frontIndex == rearIndex) { //last one, reset frontIndex = -1; rearIndex = -1; } else { frontIndex = (frontIndex + 1) % maxSize; } length--; return (item); } //Check empty, Time O(1), Space O(1) private boolean isEmpty() { return frontIndex == -1; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //Remove from the front, Time O(1), Space O(1) dequeue() { if (this.isEmpty()) { console.log("Queue is empty"); return null; } var item = this.queue[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); } //Check if the queue is empty, Time O(1), Space O(1) isEmpty() { return this.frontIndex == -1; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # Remove from the front, Time O(1), Space O(1) def dequeue(self): if self.is_empty(): print("The circular queue is empty, cannot dequeue") return item = self.queue[self.frontIndex] if (self.frontIndex == self.rearIndex): #one item left self.frontIndex = -1 self.rearIndex = -1 else: self.frontIndex = (self.frontIndex + 1) % self.maxSize self.length -= 1 return item #Check empty, Time O(1), Space O(1) def is_empty(self): return self.frontIndex == -1 |
Peek
Peek is to return the value at firstIndex. You 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 queue[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.queue[this.frontIndex]; } |
Python
1 2 3 4 5 6 | #Return front value, Time O(1), Space O(1) def peek(self): if self.is_empty(): print("The circular queue is empty, cannot dequeue") return return self.queue[self.frontIndex] |
Print
Print is to print all elements in the circular queue. Starting from frontIndex, you use a for loop to iterate through each slot till to rearIndex. In each iteration, the index i is increased by 1, then mod by maxSize.
Java
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 public void print() { if (isEmpty()) { System.out.println("Queue is empty"); return; } int i; for (i = frontIndex; i != rearIndex; i = (i+1) % maxSize) System.out.print(queue[i] + " "); System.out.println(queue[i]); } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 | //Print all, Time O(n), Space O(n), n is number of items in queue print() { if (this.isEmpty()) { console.log("Queue is empty"); return; } var str = ""; var i; for (i = this.frontIndex; i != this.rearIndex; i = (i+1) % this.maxSize) str += this.queue[i] + " "; str += this.queue[i]; console.log(str); } |
Python
1 2 3 4 5 6 7 8 9 10 | #Print all, Time O(n), Space O(1), n is number of items in queue def print(self): if self.is_empty(): print("The circular queue is empty") return i = self.frontIndex while i != self.rearIndex: print(str(self.queue[i]) , end = " ") i = (i + 1) % self.maxSize print(self.queue[i]) |
Free download
Download CircularQueueArray.java
Download CircularQueueArray.js
Download CircularQueueArray.py
