Circular Queue
Overview
Imagine a circular queue like a closed loop or ring where you can add elements at one end (enqueue) and remove elements from the other end (dequeue). When the queue is full and a new element is enqueued, it overwrites the oldest element (as seen in the animation, the rear arrow moves back to the beginning - the end starts to chase the start like a circle), allowing the queue to efficiently reuse space without resizing or shifting elements.
The circular queue has the following essential characteristics:
Front: The index pointing to the first element in the circular queue. When the queue is empty, the front points to a special value (the -1 value in the animation) indicating that the queue is empty.
Rear: The index pointing to the last element in the circular queue. When the queue is empty, the rear also points to the special value (the -1 value in the animation) indicating an empty queue.
Capacity: The maximum number of elements that the circular queue can hold, which is determined when the queue is created.
Circular Arrangement: The circular queue forms a loop, allowing elements to wrap around from the last position to the first position, effectively creating a circular arrangement of elements (the wrap is visible after the enqueueing of '6' in the animation).
The circular queue is particularly useful in scenarios where you need a fixed-size buffer that continuously cycles through data, such as managing streaming data, input/output buffers, and applications with resource constraints.
Considering we already know the basics of queues, the operations for a circular queue are almost similar with some additional:
Enqueue: Add an element to the rear of the circular queue.
Dequeue: Remove an element from the front of the circular queue.
Is empty: Check if the circular queue is empty.
is full: Check if the circular queue is full.
Front: Get the front element without removing it.
Rear: Get the rear element without removing it.
In conclusion, what are the possible use cases of circular queues?
To efficiently manage memory buffers for ongoing data, schedule tasks, handle printer queues, control bounded resources like network connections, cache, input, and data streaming management. They're particularly effective for scenarios requiring memory efficiency and continuous processing without element shifting
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * self.capacity
self.front = self.rear = -1
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, item):
if self.is_full():
print("Queue is full. Cannot enqueue item:", item)
return
if self.is_empty():
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
def dequeue(self):
if self.is_empty():
print("Queue is empty. Cannot dequeue.")
return None
item = self.queue[self.front]
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
return item
# Initial circular queue of [1, 2, 3, 4, 5]
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
# Dequeue 1 and 2
print("Dequeued:", cq.dequeue())
print("Dequeued:", cq.dequeue())
# Enqueue 6 and 7
cq.enqueue(6)
cq.enqueue(7)
class CircularQueue {
constructor(capacity) {
this.capacity = capacity;
this.queue = new Array(this.capacity).fill(null);
this.front = this.rear = -1;
}
isEmpty() {
return this.front === -1;
}
isFull() {
return (this.rear + 1) % this.capacity === this.front;
}
enqueue(item) {
if (this.isFull()) {
console.log("Queue is full. Cannot enqueue item:", item);
return;
}
if (this.isEmpty()) {
this.front = this.rear = 0;
} else {
this.rear = (this.rear + 1) % this.capacity;
}
this.queue[this.rear] = item;
}
dequeue() {
if (this.isEmpty()) {
console.log("Queue is empty. Cannot dequeue.");
return null;
}
const item = this.queue[this.front];
if (this.front === this.rear) {
this.front = this.rear = -1;
} else {
this.front = (this.front + 1) % this.capacity;
}
return item;
}
}
// Initial circular queue of [1, 2, 3, 4, 5]
const cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
// Dequeue 1 and 2
console.log("Dequeued:", cq.dequeue());
console.log("Dequeued:", cq.dequeue());
// Enqueue 6 and 7
cq.enqueue(6);
cq.enqueue(7);
public class CircularQueue {
private int capacity;
private int[] queue;
private int front;
private int rear;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[this.capacity];
this.front = this.rear = -1;
}
public boolean isEmpty() {
return front == -1;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue item: " + item);
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % capacity;
}
queue[rear] = item;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1;
}
int item = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % capacity;
}
return item;
}
public static void main(String[] args) {
// Initial circular queue of [1, 2, 3, 4, 5]
CircularQueue cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
// Dequeue 1 and 2
System.out.println("Dequeued: " + cq.dequeue());
System.out.println("Dequeued: " + cq.dequeue());
// Enqueue 6 and 7
cq.enqueue(6);
cq.enqueue(7);
}
}
#include <stdio.h>
#include <stdbool.h>
#define MAX_CAPACITY 5
typedef struct {
int queue[MAX_CAPACITY];
int front;
int rear;
} CircularQueue;
void initializeQueue(CircularQueue *cq) {
cq->front = cq->rear = -1;
}
bool isEmpty(CircularQueue *cq) {
return cq->front == -1;
}
bool isFull(CircularQueue *cq) {
return (cq->rear + 1) % MAX_CAPACITY == cq->front;
}
void enqueue(CircularQueue *cq, int item) {
if (isFull(cq)) {
printf("Queue is full. Cannot enqueue item: %d\n", item);
return;
}
if (isEmpty(cq)) {
cq->front = cq->rear = 0;
} else {
cq->rear = (cq->rear + 1) % MAX_CAPACITY;
}
cq->queue[cq->rear] = item;
}
int dequeue(CircularQueue *cq) {
if (isEmpty(cq)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1;
}
int item = cq->queue[cq->front];
if (cq->front == cq->rear) {
cq->front = cq->rear = -1;
} else {
cq->front = (cq->front + 1) % MAX_CAPACITY;
}
return item;
}
int main() {
CircularQueue cq;
initializeQueue(&cq);
// Initial circular queue of [1, 2, 3, 4, 5]
enqueue(&cq, 1);
enqueue(&cq, 2);
enqueue(&cq, 3);
enqueue(&cq, 4);
enqueue(&cq, 5);
// Dequeue 1 and 2
printf("Dequeued: %d\n", dequeue(&cq));
printf("Dequeued: %d\n", dequeue(&cq));
// Enqueue 6 and 7
enqueue(&cq, 6);
enqueue(&cq, 7);
return 0;
}
class CircularQueue {
private $capacity;
private $queue;
private $front;
private $rear;
public function __construct($capacity) {
$this->capacity = $capacity;
$this->queue = array_fill(0, $this->capacity, null);
$this->front = $this->rear = -1;
}
public function isEmpty() {
return $this->front == -1;
}
public function isFull() {
return ($this->rear + 1) % $this->capacity == $this->front;
}
public function enqueue($item) {
if ($this->isFull()) {
echo "Queue is full. Cannot enqueue item: $item\n";
return;
}
if ($this->isEmpty()) {
$this->front = $this->rear = 0;
} else {
$this->rear = ($this->rear + 1) % $this->capacity;
}
$this->queue[$this->rear] = $item;
}
public function dequeue() {
if ($this->isEmpty()) {
echo "Queue is empty. Cannot dequeue.\n";
return null;
}
$item = $this->queue[$this->front];
if ($this->front == $this->rear) {
$this->front = $this->rear = -1;
} else {
$this->front = ($this->front + 1) % $this->capacity;
}
return $item;
}
}
// Initial circular queue of [1, 2, 3, 4, 5]
$cq = new CircularQueue(5);
$cq->enqueue(1);
$cq->enqueue(2);
$cq->enqueue(3);
$cq->enqueue(4);
$cq->enqueue(5);
// Dequeue 1 and 2
echo "Dequeued: " . $cq->dequeue() . "\n";
echo "Dequeued: " . $cq->dequeue() . "\n";
// Enqueue 6 and 7
$cq->enqueue(6);
$cq->enqueue(7);