前言

最近使用队列的时候，在实现大数据整体平移的时候还是用了内存copy虽然暂时达到性能要求，但是总感觉很笨重，最后用环形队列重构了部分代码，效果还行。

一、环形队列

循环队列是一种线性数据结构，其中的操作是基于FIFO（先进先出）原理执行的，最后一个位置又连接回第一个位置以构成一个闭合的环形队列。也称为“环形缓冲区”。
在普通队列中，我们可以插入元素，直到队列变满。但是，一旦队列已满,再无法插入下一个元素。因为在环形队列里面有两个索引计数器，每次插入队列rear会+1,每次出队操作,front索引会递增+1
应用场合：此环形队列的最佳实现形式就是固定长度的数组。

因为我们用数组来表示环形队列，数组第一个地址可以认为为头，正因为如此，实现环形结构，在rear位置就要判断是否已经满载了，从而将rear置为0操作。

二、环形队列基本操作

以一个大小为10的数组为例子
在这里插入图片描述
**空环（空载）😗*当front和rear计算器指向同一个元素级别的内存块,定义为空载,（但是不能让front=rear作为判断空载的条件）因此我们使其front或rear重置为一个负数，例如-1就是表示空环状态。
满环（满载）:当rear计数器随着在入队操作递增逼近front计数器，此时rear=size-1并且front=0（对应一直入环，此时头指针没有偏移），或者rear=front-1（有入队和出对操作，此时头和尾已经偏离之前0的位置）。
入队：需要判断当前队列信息（尾开始++）：
1、满载时候，直接退出；
2、空载，则需要将d_rear = d_front = 0；
3、rear == 9到队列最尾部并且front 不在0处（不为满载的情况），此时rear =0；
4、除上述情况 rear++；
出队：需要判断当前队列信息（头开始++）：
1、空载，直接返回一个空元素；
2、取出当前数据
2.1 rear = front 时候 rear = front=-1 （也就是刚插入一个元素就取出来）
2.2、front = 9（队列尾部时候）front =0；
2.3、除上述情况正常 front++；

二、示例

给出一个循环队列模板类

template <class T>
class CircleQueue
{
private:long mrear, mfront;                       //内部元素队列指针size_t msize;                             //可用大小size_t mmaxsize;                          //最大队列大小T *marr;
public:CircleQueue();                              //默认构造函数CircleQueue(size_t);                        //自定义构造函数~CircleQueue();                             //析构函数CircleQueue(const CircleQueue &);           //拷贝构造函数CircleQueue(CircleQueue &&);                //移动构造函数T deque();                                  //出队列void enque(const T &);                      //入队操作size_t size() const;                        //获取队列大小T front() const;                            //获取端首元素T rear() const;                             //获取末尾元素bool iEmpty() const;                        //队列是否非空bool isFull() const;                        //队列是否已满const size_t size();                        //返回队列已有数量const T *buffer();                          //对列头地址};
#endif

实现

#include "CircleQueue.h"
#define DEFAULT_SIZE 10template <class T>
CircleQueue<T>::CircleQueue()
{mfront = mrear = -1;mmaxsize = DEFAULT_SIZE;msize = 0;marr = new T[mmaxsize];
}//构造函数
template <class T>
CircleQueue<T>::CircleQueue(size_t size)
{msize = 0;mmaxsize = size;mfront = mrear = -1;marr = new T[mmaxsize];
}//析构函数
template <class T>
CircleQueue<T>::~CircleQueue()
{delete[] marr;
}//检查环形队列是否为满载
template <class T>
bool CircleQueue<T>::isFull() const
{return (mrear == mmaxsize - 1 && mfront == 0) || (mrear == mfront - 1);
}//判断环形队列是否为空
template <class T>
bool CircleQueue<T>::isEmpty() const
{return mfront == -1 || mrear == -1;
}//入队操作
template <class T>
void CircleQueue<T>::enque(const T &value)
{if (is_full()){std::cout << "环形队列已满" << std::endl;return;}else if (mfront == -1){mrear = mfront = 0;}else if (mrear == mmaxsize - 1 && mfront != 0){mrear = 0;}else{mrear++;}marr[mrear] = value;msize++;
}//出队操作
template <class T>
T CircleQueue<T>::deque()
{if (is_empty()){std::cout << "环形队列为空!!" << std::endl;return T();}T data = marr[mfront];if (mfront == mrear){mfront = -1;mrear = -1;}else if (mfront == msize - 1){mfront = 0;}else{mfront++;}msize--;return data;
}//获取队头部元素
template <class T>
T CircleQueue<T>::front() const
{return marr[mfront];
}//获取队尾元素
template <class T>
T CircleQueue<T>::rear() const
{return marr[mrear];
}//获取队列尺寸
template <class T>
const size_t CircleQueue<T>::size()
{return msize;
}//获取队列内部的缓存指针
template <class T>
const T *CircleQueue<T>::buffer()
{return marr;
}