Algorithm
A circular queue is a data structure that follows the First-In-First-Out (FIFO) principle, but with a twist. In a standard queue, when an element is dequeued (removed from the front), the space it occupied becomes available for a new element. However, in a circular queue, the front and rear pointers wrap around to the beginning of the queue when they reach the end. This creates a circular arrangement of elements.
Here are the key features of a circular queue:
-
Front and Rear Pointers: It has two pointers, front and rear, pointing to the front and rear of the queue, respectively.
-
Circular Arrangement: When the rear pointer reaches the end of the queue, it wraps around to the beginning if there is space, making the queue circular.
-
Empty and Full Conditions: Similar to a regular queue, a circular queue can be empty or full. The queue is empty when the front and rear pointers are the same, and it is full when the rear is just behind the front.
-
Operations:
- Enqueue (Insert): Adds an element to the rear of the queue.
- Dequeue (Delete): Removes an element from the front of the queue.
- Front: Gets the element at the front of the queue without removing it.
- IsFull: Checks if the queue is full.
- IsEmpty: Checks if the queue is empty.
-
Advantages:
- Efficient use of memory as it utilizes the entire array by wrapping around.
- Avoids the shifting of elements as in the case of a regular queue.
-
Implementation:
- Typically implemented using an array or a linked list.
- The modulo operation is often used to handle the circular wrapping.
Code Examples
#1 Example of a circular queue implemented using an array in Python:
Code -
Python Programming
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * 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.")
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
removed_item = self.queue[self.front]
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity
return removed_item
def peek(self):
if self.is_empty():
print("Queue is empty. Cannot peek.")
return None
return self.queue[self.front]
# Example usage:
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print("Front of the queue:", cq.peek())
print("Dequeue:", cq.dequeue())
print("Dequeue:", cq.dequeue())
cq.enqueue(4)
cq.enqueue(5)
cq.enqueue(6) # This will be rejected as the queue is full
#2 Example of a circular queue implemented using an array in Java:
Code -
Java Programming
public class CircularQueue {
private int front, rear, size;
private int[] queue;
public CircularQueue(int capacity) {
size = capacity + 1; // One extra space to differentiate between full and empty states
queue = new int[size];
front = rear = 0;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % size == front;
}
public void enqueue(int data) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue element.");
return;
}
queue[rear] = data;
rear = (rear + 1) % size;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue element.");
return -1; // Assuming -1 is not a valid element in the queue
}
int data = queue[front];
front = (front + 1) % size;
return data;
}
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot peek element.");
return -1; // Assuming -1 is not a valid element in the queue
}
return queue[front];
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
int i = front;
do {
System.out.print(queue[i] + " ");
i = (i + 1) % size;
} while (i != rear);
System.out.println();
}
public static void main(String[] args) {
CircularQueue queue = new CircularQueue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
System.out.println("Queue after enqueue operations:");
queue.display();
System.out.println("Dequeue operation. Removed element: " + queue.dequeue());
System.out.println("Queue after dequeue operation:");
queue.display();
System.out.println("Peek operation. Front element: " + queue.peek());
}
}
#3 Example of implementing a circular queue using an array in C:
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
// Structure to represent the circular queue
struct CircularQueue {
int front, rear;
int array[MAX_SIZE];
};
// Function to initialize the circular queue
void initializeQueue(struct CircularQueue* queue) {
queue->front = queue->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(struct CircularQueue* queue) {
return (queue->front == -1 && queue->rear == -1);
}
// Function to check if the queue is full
int isFull(struct CircularQueue* queue) {
return (queue->rear + 1) % MAX_SIZE == queue->front;
}
// Function to enqueue an element into the circular queue
void enqueue(struct CircularQueue* queue, int data) {
if (isFull(queue)) {
printf("Queue is full. Cannot enqueue.\n");
return;
} else if (isEmpty(queue)) {
queue->front = queue->rear = 0;
} else {
queue->rear = (queue->rear + 1) % MAX_SIZE;
}
queue->array[queue->rear] = data;
printf("%d enqueued to the queue.\n", data);
}
// Function to dequeue an element from the circular queue
int dequeue(struct CircularQueue* queue) {
int data;
if (isEmpty(queue)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1;
} else if (queue->front == queue->rear) {
data = queue->array[queue->front];
queue->front = queue->rear = -1;
} else {
data = queue->array[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE;
}
printf("%d dequeued from the queue.\n", data);
return data;
}
// Function to display the elements in the circular queue
void display(struct CircularQueue* queue) {
int i;
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
printf("Elements in the queue: ");
for (i = queue->front; i != queue->rear; i = (i + 1) % MAX_SIZE) {
printf("%d ", queue->array[i]);
}
printf("%d\n", queue->array[i]);
}
int main() {
struct CircularQueue queue;
initializeQueue(&queue);
enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);
enqueue(&queue, 4);
enqueue(&queue, 5);
display(&queue);
dequeue(&queue);
dequeue(&queue);
display(&queue);
enqueue(&queue, 6);
enqueue(&queue, 7);
display(&queue);
return 0;
}
#4 Example of implementing a circular queue using an array in C++
Code -
C++ Programming
#include <iostream>
using namespace std;
class CircularQueue {
private:
int front, rear, maxSize;
int* arr;
public:
CircularQueue(int size) {
maxSize = size + 1; // One extra space for the circular behavior
arr = new int[maxSize];
front = rear = 0;
}
~CircularQueue() {
delete[] arr;
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return (rear + 1) % maxSize == front;
}
void enqueue(int data) {
if (isFull()) {
cout << "Queue is full. Cannot enqueue." << endl;
return;
}
arr[rear] = data;
rear = (rear + 1) % maxSize;
}
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
return -1; // Return a special value to indicate an error
}
int data = arr[front];
front = (front + 1) % maxSize;
return data;
}
void display() {
int i = front;
while (i != rear) {
cout << arr[i] << " ";
i = (i + 1) % maxSize;
}
cout << endl;
}
};
int main() {
CircularQueue cq(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
cout << "Queue elements: ";
cq.display();
cout << "Dequeue operation. Removed: " << cq.dequeue() << endl;
cout << "After dequeue, queue elements: ";
cq.display();
cq.enqueue(6);
cout << "After enqueue, queue elements: ";
cq.display();
return 0;
}
Demonstration
Circular Queue Data Structure-DevsEnv