Circular Queue | CrackEase

Circular Queues using Array

Overview

Circular queues implemented with arrays overcome the limitation of linear queues where free space is lost after repeated dequeues. In a circular queue, the array is treated as circular so that when rear reaches the end it wraps to the start (index 0) if there is free space.

Code for Circular Queue (array-based)

  
// 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() {
  return ((front == rear + 1) || (front == 0 && rear == SIZE - 1));
}

// Check if the queue is empty
int isEmpty() {
  return (front == -1);
}

// Adding an element
void enQueue(int element) {
  if (isFull())
    printf("\nQueue is full!!\n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\nInserted -> %d\n", element);
  }
}

// Removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\nQueue is empty!!\n");
    return -1;
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } else {
      front = (front + 1) % SIZE;
    }
    printf("\nDeleted element -> %d\n", element);
    return element;
  }
}

// Display the queue
void display() {
  int i;
  if (isEmpty())
    printf("\nEmpty Queue\n");
  else {
    printf("\nFront -> %d \n", front);
    printf("Items -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE)
      printf("%d ", items[i]);
    printf("%d \n", items[i]);
    printf("Rear -> %d \n", rear);
  }
}

int main() {
  deQueue(); // Fails because front = -1

  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  enQueue(6); // Fails to enqueue because queue is full

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  enQueue(8); // Fails to enqueue because queue is full

  return 0;
}

  
// C++ code to perform circular queue operations (array-based)

#include <iostream>
#include <cstdlib>
#define SIZE 5
using namespace std;

class Queue {
  private:
    int items[SIZE], front, rear;
  public:
    Queue() { front = -1; rear = -1; }

    bool isFull() { return (front == 0 && rear == SIZE - 1) || (front == rear + 1); }
    bool isEmpty() { return (front == -1); }

    void enQueue(int element) {
      if (isFull()) { cout << "Queue is full" << endl; }
      else {
        if (front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        cout << "Inserted " << element << endl;
      }
    }

    int deQueue() {
      if (isEmpty()) { cout << "Queue is empty" << endl; return -1; }
      int element = items[front];
      if (front == rear) { front = -1; rear = -1; }
      else { front = (front + 1) % SIZE; }
      return element;
    }

    void display() {
      if (isEmpty()) { cout << "Empty Queue" << endl; }
      else {
        cout << "Front -> " << front << endl;
        cout << "Items -> ";
        for (int i = front; i != rear; i = (i + 1) % SIZE) cout << items[i] << " ";
        cout << items[rear] << endl;
        cout << "Rear -> " << rear << endl;
      }
    }
};

int main() {
  Queue q;
  q.deQueue();
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);
  q.enQueue(6);
  q.display();
  int elem = q.deQueue();
  if (elem != -1) cout << "Deleted Element is " << elem << endl;
  q.display();
  q.enQueue(7);
  q.display();
  q.enQueue(8);
  return 0;
}

  
// Java implementation of Circular Queue (array-based)

public class CQueue {
  int SIZE = 5;
  int front, rear;
  int items[] = new int[SIZE];

  CQueue() { front = -1; rear = -1; }

  boolean isFull() { return (front == 0 && rear == SIZE - 1) || (front == rear + 1); }
  boolean isEmpty() { return (front == -1); }

  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);
    }
  }

  int deQueue() {
    if (isEmpty()) { System.out.println("Queue is empty"); return -1; }
    int element = items[front];
    if (front == rear) { front = -1; rear = -1; }
    else { front = (front + 1) % SIZE; }
    return element;
  }

  void display() {
    if (isEmpty()) { System.out.println("Empty Queue"); }
    else {
      System.out.println("Front -> " + front);
      System.out.print("Items -> ");
      for (int i = front; i != rear; i = (i + 1) % SIZE) System.out.print(items[i] + " ");
      System.out.println(items[rear]);
      System.out.println("Rear -> " + rear);
    }
  }

  public static void main(String[] args) {
    CQueue q = new CQueue();
    q.deQueue();
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);
    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();
    q.enQueue(8);
  }
}

	
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!!

	
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 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

	
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 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

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Circular Queues using Array

Overview