Circular Queue Data Structure

We learned linear queue or simple queue last time, now its time to learn circular queue which will fix main issues with the linear queue. We will be able to reuse the empty space for more items. Here is a quick look at it:

The way it works is simple, any space left empty on front after dequeue can be reused to enqueue again. This way it goes circular way, hence the name “Circular queue”. Let’s implement it so we can better understand it:

const int MAX_SIZE = 5;

struct Queue {
private:
  int front = -1;
  int rear = -1;
  int count = 0;
  int items[MAX_SIZE];
}

Alright so we have similar pointers like front and rear as we had in simple queue. The items array stores data same way as linear queue also but we got a count variable this time. We can’t rely on rear or MAX_SIZE because it’s a circular queue. Rear can be at index 1 and Front at 2. So we will use this count to determine if we have any space left to enqueue.

Let’s move on to our enqueue method:

void enqueue(int value) {
  if (count == MAX_SIZE) {
    cout << "Queue Overflow: Cannot queue" << value << endl;
    return;
  }

  if (rear == -1) {
    rear = 0;
    front = 0;
  }

  items[rear] = value;
  rear = (rear + 1) % MAX_SIZE;
  count++;

  cout << "Enqueue: " << value << endl;
}

First we simply check if there is enough space in the queue by comparing the MAX_SIZE with count. After than we handle the case for first time enqueuing because when the first item is enqueued, both pointers front and rear are at -1. Which indicates that they are pointing to nothing. When we enqueue first item, both front and rear point to same item and same index.

Every new enqueued item will be the new rear so we will proceed with actually storing the value at rear. After that we got a special trick to help us circulate in available indexes. In rear = (rear + 1) % MAX_SIZE; we are doing exactly that. The technique/trick can be explain like this:

If you modulo a number by any number bigger than it, it will keep circulating within the range of bigger number. It’s known as cyclic indexing or modular indexing.

Here is the simplified version:

index % size = remainder within range [0,size−1]

Anyways, after that we simply increment the count as we need it for tracking whether the queue is full or not.

Next we got the dequeue method, which contains the same modular indexing technique. Here, take a look:

void dequeue() {
  if (count == 0) {
    cout << "Queue Underflow: No element to dequeue" << endl;
    return;
  }

  cout << "Dequeued: " << items[front] << endl;

  front = (front + 1) % MAX_SIZE;
  count--;
}

We are first making sure we have an element to dequeue. After that queue happens by using the modular indexing but this time we do this to figure out the next front pointer. After that we simply decrement the count.

Then we have another method to see next element which will be dequeued if we called the dequeue method.

int peek() {
  if (count == 0) {
    cout << "Queue Underflow: No element to dequeue" << endl;
    return 0;
  }

  return items[front];
}

Similar to dequeue method, we check if there is any element in the queue. If yes then we simply return it otherwise we return 0.

Here is the full code with tests:

// ignore/remove the 2 lines below if you don't want any tests
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

using namespace std;

const int MAX_SIZE = 5;

struct Queue {
private:
  int front = -1;
  int rear = -1;
  int count = 0;
  int items[MAX_SIZE];

public:
  void enqueue(int value) {
    if (count == MAX_SIZE) {
      cout << "Queue Overflow: Cannot queue" << value << endl;
      return;
    }

    if (rear == -1) {
      rear = 0;
      front = 0;
    }

    items[rear] = value;
    rear = (rear + 1) % MAX_SIZE;
    count++;

    cout << "Enqueue: " << value << endl;
  }

  void dequeue() {
    if (count == 0) {
      cout << "Queue Underflow: No element to dequeue" << endl;
      return;
    }

    cout << "Dequeued: " << items[front] << endl;

    front = (front + 1) % MAX_SIZE;
    count--;
  }

  int peek() {
    if (count == 0) {
      cout << "Queue Underflow: No element to dequeue" << endl;
      return 0;
    }

    return items[front];
  }
};

TEST_CASE("enqueue works correctly") {
  Queue *queue = new Queue();

  queue->enqueue(7);
  queue->enqueue(6);

  CHECK(queue->peek() == 7);
}

TEST_CASE("dequeue works as expected") {
  Queue *queue = new Queue();

  queue->enqueue(7);
  queue->enqueue(4);

  queue->dequeue();

  CHECK(queue->peek() == 4);
}

TEST_CASE("circulation works as expected") {
  Queue *queue = new Queue();

  // fill the queue
  queue->enqueue(22);
  queue->enqueue(54);
  queue->enqueue(23);
  queue->enqueue(159);
  queue->enqueue(87);

  // dequeue one to make spot
  queue->dequeue();

  // new item should be enqueued because we have an empty spot
  queue->enqueue(68);

  // make sure all the other items are being dequeued in order
  CHECK(queue->peek() == 54);

  queue->dequeue();

  CHECK(queue->peek() == 23);

  queue->dequeue();

  CHECK(queue->peek() == 159);

  queue->dequeue();

  CHECK(queue->peek() == 87);

  queue->dequeue();

  // now check if we have the item at the end that was inserted later
  CHECK(queue->peek() == 68);
}

Time Complexity

All the methods enqueue, dequeue and peek have time complexity of O(1) because we are directly using the pointers front and rear.