Circular Buffer Examples in C++

[Linux Hint]

Circular buffer or Circular queue is the advanced version of the normal queue where the last index and tail index are connected in a circular structure. Circular buffer in C++ follows two methods: enqueue() and dequeue(). We perform the circular buffer or circular queue operation based on these methods.

• The enqueue() method checks to see if the buffer is filled. Otherwise, verify that the end index is the last one. If so, set the tail value to 0. If not, increase the tail value by the value at that index.
• The dequeue() function takes the value from the front index in the circular queue. If the queue is empty, a message will display that empty queue. Otherwise, it gets the last value and deletes it from the queue.

Program to Implement a Circular Buffer in C++

Following the mentioned two methods, we implement the circular buffer in C++. Let’s consider all the steps for the circular queue implementation in C++.

#include<bits/stdc++.h>

using namespace std;

struct MyQueue

{

int head, tail;

int Qsize;

 

int *NewArr;

 

MyQueue (int sz){

 

head = tail = -1;

Qsize = sz;

NewArr = new int[sz];

}

 

void enQueue (int val);

 

int deQueue ();

 

void showQueue ();

 

};

 

Beginning with the code, we first create the “MyQueue” struct to initialize the head and tail variables. The head variable represents the front indices and the tail represents an array’s rear back indices. After that, the circular queue’s size, denoted by the variable “Qsize”, is defined.

Then, we define the dynamically allocated array of “NewArr” which stores the values of the circular queue. Next, we call the MyQueue() which is a constructor and pass the “sz” parameter for the circular queue size. Inside the MyQueue() constructor, we assign the “-1” value to the head and tail pointers. This negative value indicates that the queue is empty now. Moving ahead, we assign the “sz” value that represents the size of the circular queue. The “NewArr” circular queue is set with a new keyword to create the array of integers within the specified “sz” size.

Then, we define the enQueue() and dequeue() functions. The enqueue() inserts the values into the defined circular queue from the tail. However, the elements in the circular queue’s head are eliminated by the dequeue() function. The showQueue() member function displays the values of the circular queue.

Step 1: Create a Function to Insert the Elements in a Circular Buffer

In the earlier step, we set a class where the private members are initialized and the private member functions are set to implement the circular queue. Now, we set the function to create the circular queue and insert the values inside the circular queue using the algorithm.

void MyQueue::enQueue (int val)

{

if ((head == 0 && tail == Qsize - 1) || (tail == (head - 1) % (Qsize - 1)))

{

cout << "\nQueue is Filled";

return;

}

 

else if (head == -1)

{

head = tail = 0;

NewArr[tail] = val;

}

 

else if (tail == Qsize - 1 && head != 0)

{

tail = 0;

NewArr[tail] = val;

}

 

else{

tail++;

NewArr[tail] = val;

}

}

 

Here, we call the “enqueue()”function from the “MyQueue” class to insert the element in the circular queue if the queue is empty or underflow. The “enqueue()” function is passed with the “val” parameter and insert the value from the tail of the circular queue. We set the “if-else” condition to insert the values in the circular queue for this. The first “if” statement which is “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” checks two conditions whether the head is at the beginning position and the tail is at the end position of the circular queue. Then, it checks whether the tail is in one position at the back of the head position. If any of these conditions are fulfilled, the queue is not empty and the prompt generates the message.

Next, we have the “else-if” condition that identifies whether the queue is empty. If so, the value is inserted in the queue. As the head is kept equal to -1, that shows that the queue is empty and the value is required to be inserted in the circular queue. For this, we set the head and tail equal to 0. Then, we insert the value from the tail position into the “NewArr” circular queue.

Then, we have our third “else-if” condition which checks whether the tail is at the last position of the queue and the head is not the starting position of the queue. This condition applies when the tail reaches the end and the starting position still has space. For this, we need to set the head at 0, and the element is added from the tail position. Lastly, if all the given conditions are not met, the queue is neither empty nor full. For this case, we increment the tail by 1 and the value is added from the new tail position.

Step 2: Create a function to Delete the Elements from the Circular Buffer

We set the previous code to create and insert the elements in the circular queue using the enqueue() function. Now, we define the implementation of removing the elements from the circular buffer if it overflows.

int MyQueue::deQueue ()

{

if (head == -1)

{

cout << "\nQueue is Free";

return INT_MIN;

}

 

int MyData = NewArr[head];

NewArr[head] = -1;

 

if (head == tail)

{

head = -1;

tail = -1;

}

 

else if (head == Qsize - 1)

head = 0;

 

else

head++;

 

return MyData;

 

}

 

In the given code, we call the dequeue() function from the “Myqueue” class to remove the element from the head index. So, we have the “if” statement that checks whether the queue is empty. The head is set with the “-1” value that represents the empty queue. The message is generated that the queue is empty and then return the INT_MIN which is the constant minimum value for an int. The “if” statement determines whether the queue is unoccupied. For this, we define the “MyData” variable and set the element’s value at the queue’s head. Then, we set the head at the -1 position which indicates that this value is removed from the queue. After this, we check whether the head and tail are equal or not. If both are equal, we assign the “-1” value to both, representing the empty circular queue. Lastly, we check if the dequeue() functions if the head is at the last index of the queue. For this, we set it with the value of “0” which loops around at the start of the array. If none of the given conditions are true, the value of the head isincremented and the dequeued element is returned.

Step 3: Create a Function to Show the Elements of the Circular Buffer

In this section, we call the showQueue() function to display the elements of the “NewArr” circular queue.

void MyQueue::showQueue ()

{

if (head == -1)

{

cout << "\nQueue is Free";

return;

}

 

cout << "\nCircular Queue elements: ";

 

if (tail >= head)

{

for (int i = head; i <= tail; i++)

cout<<NewArr[i]<<" ";

}

 

else

{

for (int i = head; i < Qsize; i++)

cout<<NewArr[i]<<" ";

 

for (int i = 0; i <= tail; i++)

cout<<NewArr[i]<<" ";

}

}

 

The queue’s empty status is first verified. An indication that the circular queue is free is displayed if the queue is free. Otherwise, the function will show the elements of the circular queue. For this, we define the “if” statement where we have the tail that is greater than or equal to the head. This condition is set to handle the case when the circular queue is not completed.

For this case, we use the “for” loop to iterate from head to tail and print the values of the circular queue. The next case is where the circular queue is completed.  For this, we check using the “if” condition where the tail is less than the head. Then, we need to use two loops where the first one iterates from the head to the end of the queue and the second one iterates from the start of the tail.

Step 4: Create the Main() Function of the Circular Queue Program

Lastly, we create the program’s main() function where we insert five integers in the circular queue and display the integers of the queue. After that, we show the deleted integers from the circular queue by calling the dequeue() function. After dequeuing a few elements, we fill the queue again by inserting the new elements using the enqueue() function.

int main ()

{

MyQueue que (5);

 

// Inserting elements in Circular Queue

que.enQueue (11);

que.enQueue (12);

que.enQueue (13);

que.enQueue (14);

que.enQueue (15);

 

// Display elements present in Circular Queue

que.showQueue ();

 

// Deleting elements from Circular Queue

cout << "\nDeleted Element = " << que.deQueue ();

cout << "\nDeleted Element = " << que.deQueue ();

 

que.showQueue ();

 

que.enQueue (16);

que.enQueue (17);

que.enQueue (18);

 

que.showQueue ();

 

return 0;

 

}

 

Output:

The results of the circular queue implementation are shown on the C++ prompt screen.

Conclusion

In conclusion, the circular buffer topic is deeply explained in this article. We created the circular buffer first, then explained how to delete from the circular queue, and then displayed the elements of the circular in C++.

View the full article