栈和队列的应用 —— 循环队列

栈和队列的应用 —— 循环队列

到达尾部又向前存储的队列被称为循环队列，为了避免“假溢出”，顺序队列通常采用循环队列。

【循环队列】

① 队空

无论队头和队尾在什么位置，只要Q.rear和Q.front指向同一个位置，就认为队空。
如果将循环队列中的一维数组画成环形图，则队空的情况：

循环队列队空的判定条件为Q.front==Q.rear。

② 队满

采用浪费一个空间的方法，当队尾Q.rear的下一个位置是Q.front时，就认为队满。但是Q.rear向后移动一个位置（Q.rear+1）后，很可能超出了数组的最大下标，这时它的下一个位置应该为0，队满（临界状态）的情况如下图所示。

其中，队列的最大空间为Maxsize，当Q.rear=Maxsize-1时，Q.rear+1=Maxsize。而根据循环队列的规则，Q.rear的下一个位置为0才对，怎么才能变为0呢？可以考虑取余运算，即(Q.rear+1)%Maxsize=0，而此时Q.front=0，即(Q.rear+1)%Maxsize=Q.front，为队满的临界状态。

对于队满的一般状态是否也适用此方法呢？

例如，循环队列队满（一般状态）的情况如下图所示。

其中，假如最大空间数Maxsize=100，当Q.rear=1时，Q.rear+1=2。取余后，(Q.rear+1)%Maxsize=2， 而此时Q.front=2，即(Q.rear+1)%Maxsize=Q.front。

对一般状态也可以采用此公式判断是否队满，因为一个不大于Maxsize的数，与Maxsize取余运算，结果仍然是该数本身，所以在一般状态下，取余运算没有任何影响。只有在临界状态下（Q.rear+1=Maxsize），取余运算(Q.rear+1)%Maxsize才会变为0。

因此，循环队列队满的判定条件可以作为：

(Q.rear+1)%Maxsize==Q.front。

③ 入队

入队时，首先将元素x 放入Q.rear所指的空间，然后Q.rear后移一位。

a、b、c 依次入队：

对于入队操作，当Q.rear后移一位时，为了处理临界状态（Q.rear+1=Maxsize），需要加1后进行取余运算。

Q.base[Q.rear] = x;  //将元素 x 放入Q.rear 所指的空间
Q.rear = (Q.rear + 1) % Maxsize;  //Q.rear 后移一位
1
2

④ 出队

先用变量保存队头元素，然后队头Q.front后移一位。

对于出队操作，当Q.front后移一位时，为了处理临界状态（Q.front+1=Maxsize），需要在加1后进行取余运算。

e = Q.base[Q.front]; //用变量记录Q.front 所指元素
Q.front = (Q.front + 1) % Maxsize; //Q.front 后移一位
1
2

注意： 对循环队列无论是入队还是出队，在队尾、队头加1后都要进行取余运算, 主要是为了处理临界状态。

⑤ 队列元素个数计算

在循环队列中到底存了多少个元素呢？循环队列中的内容实际上是从Q.front到Q.rear-1这一区间的数据元素，但是不可以直接用两个下标相减得到。

因为队列是循环的，所以存在两种情况：Q.rear≥Q.front，

Q.rear

在第二种情况中，

Q.rear=4，Q.front=Maxsize-2，Q.rearQ.front=6-Maxsize。但是可以看到循环队列中的元素实际上为6个，那怎么办呢？

当两者之差为负数时，可以将差值加上Maxsize计算元素个数，即Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize=6，元素个数为6。

在计算元素个数时，可以分两种情况进行判断：

①Q.rear≥Q.front，元素个数为Q.rear-Q.front；

②Q.rear 也可以采用取余的方法把两种情况巧妙地统一为一个语句，即

(Q.rear - Q.front+Maxsize)%Maxsize
1

这个计算公式是否正确？

假如Maxsize=100，则在上图（a）中，Q.rear=4，Q.front=1，Q.rear-Q.front=3，(3+100)%100=3，元素个数为3；在上图（b）中，Q.rear=4，Q.front=98，Q.rear-Q.front=-94，(-94+100)%100=6，元素个数为6。所以计算公式正确。

当Q.rear-Q.front为正数时，加上Maxsize后超过了最大空间数，取余后正好是元素个数；当Q.rear-Q.front为负数时，加上Maxsize后正好是元素个数，因为元素个数小于Maxsize，所以取余运算对其无影响。

因此，%Maxsize用于防止出现Q.rear-Q.front为正数的情况，+Maxsize用于防止出现Q.rear-Q.front为负数的情况

【总结】

队空：

Q.front == Q.rear;  //Q.rear 和 Q.front 指向同一个位置
1

队满：

(Q.rear + 1) % Maxsize = Q.front;  //Q.rear 后移一位正好是Q.front
1

入队：

Q.base[Q.rear] = x;  //将元素 x 放入Q.rear 所指的空间
Q.rear = (Q.rear + 1) % Maxsize;   //Q.rear 后移一位
1
2

出队：

e = Q.base[Q.front]; //用变量记录Q.front 所指的元素
Q.front = (Q.front + 1) % Maxsize;  //Q.front 后移一位
1
2

队列中的元素个数：

(Q.rear - Q.front + Maxsize) % Maxsize;
1

【循环队列的基本操作】

循环队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。

（1）初始化。初始化时，首先分配一个大小为Maxsize的空间，然后令Q.front=Q.rear=0，即队头和队尾为0，队列为空。

[算法代码]

bool InitQueue(SqQueue &Q){ //注意使用引用，否则传值调用，改变无效
	Q.base = new int[Maxsize];  //分配Maxsize 大小的空间
	if(!Q.base){
		return false; //分配空间失败
	}
	Q.front = Q.rear = 0; //队头和队尾 为 0，队列为空
	return true;
}
1
2
3
4
5
6
7
8

（2）入队。入队时，判断队列是否已满，如果已满，则入队失败；如果未满，则将新元素插入队尾，队尾后移一位。

[算法代码]

bool EnQueue(SqQueue &Q , int e){ //入队，将元素e放入Q的队尾
	if((Q.rear + 1) % Maxsize == Q.front){ // 队尾后移一位等于队头，表示队满
		return false;
	}
	Q.base[Q.rear] = e; //将新元素插入队尾
	Q.rear = (Q.rear + 1) % Maxsize; //队尾后移一位
	return true;
}
1
2
3
4
5
6
7
8

（3）出队。出队时，判断队列是否为空，如果队列为空，则出队失败；如果队列不为空，则用变量保存队头元素，队头后移一位。

[算法代码]

bool Dequeue(SqQueue &Q , int &e){ //出队，删除Q的队头元素，用e返回其值
	if(Q.front == Q.rear){
		return false; //队空
	}
	e = Q.base[Q.front]; //保存队头元素
	Q.front = (Q.front + 1) % Maxsize; //队头后移一位
	return true;
}
1
2
3
4
5
6
7
8

（4）取队头元素。取队头元素时，只是把队头元素数据复制一份，并未改变队头的位置，因此队列中的内容没有改变

[算法代码]

int GetHead(SqQueue Q){ //取队头元素，不修改队头
	if(Q.front != Q.rear){ //队列非空
		return Q.base[Q.front];
	}
	return -1;
}
1
2
3
4
5
6

（5）求队列长度。通过前面的分析，我们已经知道循环队列中的元素个数为(Q.rear- Q.front+Maxsize)% Maxsize，循环队列中的元素个数为循环队列的长度。

[算法代码]

int QueueLength(SqQueue Q){
	return (Q.rear - Q.front + Maxsize) % Maxsize;
}
1
2
3