In this post we will learn on how we can implement circular queues purely using arrays. Circular queues are extension of linear queues where the max size of queue is always available for insertion. Unlike linear queues which faces the problem of reduction in available size for insertion with each iterative dequeue operation that happens, we will learn more about the same in this post.
// Circular Queue implementation in C
#include<stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
return 0;
}
// Check if the queue is empty
int isEmpty() {
if (front == -1) return 1;
return 0;
}
// Adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}
int main() {
// Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0;
}
#include<iostream>
#define SIZE 5 /* Size of Circular Queue */
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
// Check if the queue is full
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check if the queue is empty
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element,
// so we reset the queue after deleting it.
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
// Function to display status of Circular Queue
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << "Front -> " << front;
cout << endl
<< "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)
cout << items[i];
cout << items[i];
cout << endl
<< "Rear -> " << rear;
}
}
};
int main() {
Queue q;
// Fails because front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1)
cout << endl
<< "Deleted Element is " << elem;
q.display();
q.enQueue(7);
q.display();
// Fails to enqueue because front == rear + 1
q.enQueue(8);
return 0;
}
public class CQueue {
int SIZE = 5; // Size of Circular Queue
int front, rear;
int items[] = new int[SIZE];
CQueue() {
front = -1;
rear = -1;
}
// Check if the queue is full
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check if the queue is empty
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
/* Function to display status of Circular Queue */
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
} else {
System.out.println("Front -> " + front);
System.out.println("Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE)
System.out.print(items[i] + " ");
System.out.println(items[i]);
System.out.println("Rear -> " + rear);
}
}
public static void main(String[] args) {
CQueue q = new CQueue();
// Fails because front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1) {
System.out.println("Deleted Element is " + elem);
}
q.display();
q.enQueue(7);
q.display();
// Fails to enqueue because front == rear + 1
q.enQueue(8);
}
}
Output : C
Queue is empty !!
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Queue is full!!
Front -> 0
Items -> 1 2 3 4 5
Rear -> 4
Deleted element -> 1
Front -> 1
Items -> 2 3 4 5
Rear -> 4
Inserted -> 7
Front -> 1
Items -> 2 3 4 5 7
Rear -> 0
Queue is full!!
Output : C++
Queue is empty
Inserted 1
Inserted 2
Inserted 3
Inserted 4
Inserted 5
Queue is fullFront -> 0
Items -> 12345
Rear -> 4
Deleted Element is 1Front -> 1
Items -> 2345
Rear -> 4
Inserted 7
Front -> 1
Items -> 23457
Rear -> 0Queue is full
Output : Java
Queue is emptyInserted 1
Inserted 2
Inserted 3
Inserted 4
Inserted 5
Queue is full
Front -> 0
Items ->
1 2 3 4 5
Rear -> 4
Deleted Element is 1
Front -> 1
Items ->
2 3 4 5
Rear -> 4
Inserted 7
Front -> 1
Items ->
2 3 4 5 7
Rear -> 0
Queue is full