C++ circular queue implementation model

This article illustrates the C++ circular queue implementation model. Share with you for your reference. Specific analysis is as follows:

Some time ago, I saw such a small topic on zhihu:

Implement a queue with a primitive type that requires the size to be predefined. And requirements can not use the language's own API, such as C++ STL. Common implementations are simple, but now require optimization of time and space complexity as much as possible, comparing time and space with the language's native apis. The queue also supports the following operations:

Constructor: initializes a queue

The enqueue: team

To dequeue: out of the team

Queue is a kind of basic data structure, which is widely used in common applications. However, for this problem, the implementation of linked list has such a problem: because each node has at least one pointer to the previous node or the next node, this brings an increase in space complexity, so it is not suitable for the requirements.

This brings me to boost in boost::circular_buffer, a circular buffer implemented through an underlying structure similar to an array. The advantage of arrays is that the space complexity is small enough (excluding the index items that maintain the data structure, the space complexity is linear), and the realization of a circular structure can maximize the use of space. Moreover, in the case of queue, which is only inserted and deleted at the front and rear ends, the time complexity of push and pop is only O(1).

The basic implementation is as follows:

#ifndef __CIRCULAR_QUEUE_H__

#define __CIRCULAR_QUEUE_H__
#include <stddef.h>
template<typename T>

class circular_queue

{

public:

    explicit circular_queue(size_t maxsize)

        : maxsize_(maxsize + 1), head_(0), rear_(0)

    {

        array_ = new T[maxsize_];

    }
    circular_queue(size_t maxsize, const T& val)

        : maxsize_(maxsize + 1), head_(0), rear_(0)

    {

        array_ = new T[maxsize_];

        for (size_t i = 0; i != maxsize; ++i)

        {

            array_[i] = val;

        }

        rear_ = maxsize;

    }
    circular_queue(const circular_queue& rhs)

        : maxsize_(rhs.maxsize_), head_(rhs.head_), rear_(rhs.rear_)

    {

        array_ = new T[maxsize_];

        for (int i = 0; i != maxsize_; ++i)

        {

            array_[i] = rhs.array_[i];

        }

    }
    ~circular_queue()

    {

        delete [] array_;

    }
    circular_queue& operator=(const circular_queue& rhs)

    {

        if (this == &rhs)

        {

            return *this;

        }

        delete [] array_;

        maxsize_ = rhs.maxsize_;

        head_ = rhs.head_;

        rear_ = rhs.rear_;

        array_ = new T[maxsize_];

        for (int i = 0; i != maxsize_; ++i)

        {

            array_[i] = rhs.array_[i];

        }

        return *this;

    }
    bool empty() const

    {

        return head_ == rear_;

    }
    size_t size() const

    {

        return (rear_ - head_ + maxsize_) % maxsize_;

    }
    T& front()

    {

        return array_[head_];

    }
    const T& front() const

    {

        return array_[head_];

    }
    void push(const T& val)

    {

        if ((rear_ + 1) % maxsize_ != head_)

        {

            array_[rear_] = val;

            rear_ = (rear_ + 1) % maxsize_;

        }

    }
    void pop()

    {

        if (head_ != rear_)

        {

            head_ = (head_ + 1) % maxsize_;

        }

    }
private:

    size_t  maxsize_;

    int     head_;

    int     rear_;

    T*      array_;

};
#endif

Queue length = array length -1

An array element space of one unit is reserved for the end of the queue.

This is a crude implementation that doesn't take into account things like thread safety, STL algorithms, and compatibility with function objects. The code is just a simple test, if there is an error welcome :)

In general, the circular queue of this kind of thinking has the following advantages:

1, use fixed memory, no implicit or unexpected memory allocation.

2. Fast constant-time insertion and deletion of elements from the front end or back end.

3, fast constant time random access to elements. (define operator[] if necessary)

4. For real-time and performance-critical applications.

When the queue is full, the data from one end will be overwritten and washed off. Such a model can be applied to these situations:

Save the recently received sample data and overwrite the oldest data when the new sample data arrives.
A quick buffer to hold a specific number of last inserted elements.
Efficient fixed-capacity FIFO(FIFO) or LIFO(LIFO) queues that remove the oldest (that is, the earliest) elements when the queue is full.

Hope that the article described in the C++ programming algorithm design is helpful.