博客

最近在项目中需要用到循环队列，发现自己很多地方还没理解透彻，因此梳理了一下相关知识，加深自己的理解。


1.循环队列的概述

循环队列就是改进的顺序队列。我们在循环队列中设置两个指针，队尾指针rear指向刚进队元素的位置，队首指针front指向刚出队元素的位置。当元素进队时，rear要向后移动；当元素出队时，front也要向后移动；下图是循环队列元素进队/出队示意图：

• 由空队进入三个元素，此时front指向0，rear指向3；
• 进队三个元素，出队三个元素，此时front指向3，rear指向6；
• 进队四个元素，出队六个元素，此时front指向9，rear指向0；

从1到3的变化过程可以看出经过元素的进进出出，即使front和rear都到了数组的尾端，但依然可以让运算继续入队，因为两个指针是沿着一个环走。

要实现指针在递增的过程中沿着环走，可以循环执行语句：front=(front+1)%10,则front的取值为 0，1，2，3，4，5，6，7，8，9，0，1，2，3… …,即以0~9为周期的无限循环数。下图展现了两个特殊的状态：队满、队空。


根据队满和队空的状态可知，循环队列必须损失一个存储空间,若没有损失空间，则队空队满的条件都是：front==rear。

• 队空条件为：front==rear
• 队满条件为：（rear+1）%maxSize==front

2.循环队列的要素

2.1循环队列的两个状态

• 队空状态：queue.rear==queue.front
• 队满状态：(queue.rear+1)%maxSize==queue.front

2.2循环队列的两个操作

• 元素x进队操作：queue.rear=(queue.rear+1)%maxSize; queue.data[qu.rear]=x;
• 元素x出队操作：queue.front=(queue.front+1)%maxSize; x=queue.data[queue.front];

3.初始化及判断队空

初始化队列算法：

void initQueue(SqQueue &qu)
{
     qu.front=qu.rear=0;
}

判断循环队列是否为空

bool isQueueEmpty(SqQueue qu)
{
    if(qu.front==qu.rear)
         return Ture;
     else
        return False;
}