正文
循环队列实现(C++) Ring Buffer
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
循环队列：队列有着先入先出的特性。但是对于队列如果删除队头以后剩下的空间将不会被释放，又由于队列只能由队尾插入这就导致
被删除部分的空间被浪费。解决这个问题就是循环队列。循环队列顾名思义就是将队列串起来形成一个类似与环的结构。如图所示。对照着图很容易理解:
对于原来队列里的操作自然有不同的地方：
1.判断满：循环队列的满不再是rear=front 而是改成(rear-front+maxn)%maxn。
2.入队操作: data[rear] = x; rear = (rear+1)%maxn;
总体思想就是不让rear和front的值超过maxn的大小。于是就在rear和front自增时候模maxn。
其实就是Ring Buffer
空队时指针（下标）front和rear在一起都指向队前方，当有元素进队，则rear后移；有元素出队，则front后移，最后，开始时分配给队的前端不再被利用。（查看动画演示）
为了充分利用队列，顺序队列总是做成一个逻辑上的循环队列。
注意：空队时rear等于front，满队时必须空一个位置。
#include <iostream> using namespace std; template <class T>
class cycleQueue
{
private:
unsigned int m_size;
int m_front;
int m_rear;
T* m_data;
public:
cycleQueue(unsigned size)
:m_size(size),
m_front(),
m_rear()
{
m_data = new T[size];
} ~cycleQueue()
{
delete [] m_data;
} bool isEmpty()
{
return m_front == m_rear;
} bool isFull()
{
return m_front == (m_rear + )%m_size;
} void push(T ele)throw(bad_exception)
{
if(isFull())
{
throw bad_exception();
}
m_data[m_rear] = ele;
m_rear = (m_rear + )%m_size;
} T pop() throw(bad_exception)
{
if(isEmpty())
{
throw bad_exception();
}
T tmp = m_data[m_front];
m_front = (m_front + )%m_size;
return tmp;
}
}; int main()
{
cycleQueue<int> q();
q.push();
q.push();
q.push();
q.push();
for (int i = ; i < ; i++)
cout << q.pop() << endl;
q.push();
q.push();
q.push();
cout << q.pop() << endl;
cout << q.pop() << endl;
cout << q.pop() << endl;
cout << q.pop() << endl;
return ;
}
