Best way of implementing a circular buffer

Question

I wanted to implement a circular buffer for learning purpose only.

My first option was to use a secondary status for rear and front pointers: (Like the ones I've seen in many websites)

#include <iostream>
using namespace std;
template<class T>
class ql
{
 public:
 ql(int size)
 {
 this->size = size;
 data = new T[size];
 front = NULL;
 rear = NULL;
 }
 ~ql()
 {
 delete[] data;
 }
 void enQueue(T item)
 {
 T *nf = nextPtr(rear);
 if (nf != front)
 {
 if (front == NULL)
 front = &data[0];
 *nf = item;
 rear = nf;
 cout << item << " Added. ^_^" << endl;
 }
 else
 cout << "OverFLO@#R$MR... X_X" << endl;
 }
 T *deQueue()
 {
 if (rear != NULL)
 {
 T *p = front;
 if (front == rear)
 {
 front = NULL;
 rear = NULL;
 } 
 else
 front = nextPtr(front);
 cout << *p << " is going to be returned. -_-" << endl;
 return p;
 }
 else
 cout << "Empty... >_<" << endl;
 }
 private:
 T *nextPtr(T *p)
 {
 if (p == &data[size - 1] || p == NULL)
 return &data[0];
 return p + 1;
 }
 T *data, *rear, *front;
 int size;
};
int main()
{
 ql<int> q(3);
 q.enQueue(1);
 q.enQueue(2);
 q.enQueue(3);
 q.enQueue(4);
 cout << endl;
 q.deQueue();
 q.deQueue();
 q.deQueue();
 q.deQueue();
 cout << endl;
 q.enQueue(5);
 q.enQueue(6);
 cout << endl;
 q.deQueue();
 q.deQueue();
 q.deQueue();
 return 0;
}

My second option was to sacrifice a space for the sake of distinguishing between empty and full circular buffers: (I saw this one on Ellis's Fundamentals of data structures)

template<class T>
class ql
{
 public:
 ql(int size)
 {
 this->size = size;
 data = new T[size];
 front = 1;
 rear = 0;
 }
 ~ql()
 {
 delete[] data;
 }
 void enQueue(T item)
 {
 if ((rear + 2) % size != front)
 {
 rear = (rear + 1) % size;
 data[rear] = item;
 cout << item << " Added. ^_^" << endl;
 }
 else
 cout << "OverFLO@#R$MR... X_X" << endl;
 }
 T *deQueue()
 {
 if ((rear + 1) % size != front)
 {
 T *p = &data[front];
 cout << *p << " is going to be returned. -_-" << endl;
 front = (front + 1) % size;
 return p;
 }
 else
 cout << "Empty... >_<" << endl;
 }
 private:
 T *data;
 int size, rear, front;
};

and my last option was to use another variable for storing used space in circular buffer:

template<class T>
class ql
{
 public:
 ql(int size)
 {
 this->size = size;
 data = new T[size];
 buffer = 0;
 front = 1;
 rear = 0;
 }
 ~ql()
 {
 delete[] data;
 }
 void enQueue(T item)
 {
 if (buffer != size)
 {
 buffer++;
 rear = (rear + 1) % size;
 data[rear] = item;
 cout << item << " Added. ^_^" << endl;
 }
 else
 cout << "OverFLO@#R$MR... X_X" << endl;
 }
 T *deQueue()
 {
 if (buffer != 0)
 {
 buffer--;
 T *p = &data[front];
 cout << *p << " is going to be returned. -_-" << endl;
 front = (front + 1) % size;
 return p;
 }
 else
 cout << "Empty... >_<" << endl;
 }
 private:
 T *data;
 int size, buffer, rear, front;
};

Which one of this approaches do you think is the best? I'm also looking for advises on how to change this class for practical using. thanks

• Zeta: If you're a language beginner you might want to add beginner to the tags.

Answer 1

Use better names and do not use using namespace in headers

The name q1 is rather arbitrary. queue or circular_queue is a lot better. That, by the way, is a perfect example why you shouldn't use using namespace std; when you write a header. There's already std::queue, so a queue would conflict with std::queue.

Since you're writing a template class all your code will reside in a header at some point, so using namespace is out of the question either way.

Use a smarter data store

Use std::vector<T> or std::deque<T> instead of raw pointers for the memory. Or re-use std::queue<T>, unless you want to practice writing a queue completely by hand.

Use return instead of cout

Instead of cout << ... << return bool or a custom enum in enQueue. If I want to store elements in a circular buffer, I need to know whether enQueue worked. I cannot check stdout for error messages.

Sizes are positive

Use size_t for sizes, not int.

Check all return paths

Return nullptr (C++11 or higher) or 0 in deQueue if the queue is empty. However, a pointer at that point is dangerous: the user must make a copy at some point, or they might end up with another object. Use std::optional if you have C++17 at hand instead, or

 bool deQueue(T & dest) {
 if(...) {
 // queue has elements
 dest = ...;
 ...
 return true;
 } else {
 // queue has no elements
 return false;
 }
 }

enQueue could use a const T& instead of a T, by the way. Or you could use std::move for movable types.

All at once

If you follow these guidelines, you will end up

#include <optional>
#include <queue>
#include <utility>
template<class T>
class queue
{
 public:
 explicit queue(size_t size) : m_size(size) { }
 queue(const queue<T> & other) = default;
 queue(queue<T> && other) = default;
 queue& operator=(const queue<T> & other) = default;
 queue& operator=(queue<T> && other) = default;
 bool enQueue(T item)
 {
 if(m_data.size() == m_size) {
 return false;
 } else {
 m_data.push(std::move(item));
 return true;
 }
 }
 std::optional<T> deQueue()
 {
 if(m_data.empty()) {
 return std::nullopt;
 } else {
 std::optional<T> result = m_data.front();
 m_data.pop();
 return result;
 }
 }
 size_t capacity() const
 {
 return m_size;
 }
 size_t size() const
 {
 return m_data.size();
 }
 private:
 size_t m_size;
 std::queue<T> m_data;
};

If you don't want to re-use std::queue or std::deque, I'd go with std::vector and your third approach.

Congratulations on your first approach, by the way. I've seen raw-pointer usage going wrong too many times, and it's refreshing to see some clever use there. Well done. But that's more or less the way you would do it in C (sans template and class, of course).

But you will probably admit that working with pointers at that point is somewhat a headache. Both front and rear (as pointers) can be expressed as data + x and data + y for two suitable int x and y, like you did in your second approach.

Either way, unless you really need to use raw pointers use either smart pointers (e.g. std::unique_ptr<T[]>) or (better) full containers like std::vector.