Question

数据结构问题

数据结构中的循环队列 队满判定条件是(q.rear+1)%maxsize=q.front 这个式子怎么来的？(q.rear+1)%maxsize是什么意思？为什么等于头指针？

Answer 1

Answer 2

严蔚敏的数据结构书上63页倒数第二段定义了判定队列空间是空还是满的方法：少用一个元素空间，判定队列呈“满”状态的标志是“队列头指针在队列尾指针的下一位置上（指环状的下一位置）”

意思就是说，循环队列留了一个元素空间，即当maxsize=100的时候，实际能存的数据只有99个，留一个不存的目的就是用来区分队列空还是满。因为空的时候q.rear=q.front，而满的时候就变成了(q.rear+1)%maxsize=q.front。

如果判定条件是q.rear%maxsize=q.front，就是判定头指针和尾指针是否在同一个位置上
如果判定条件是(q.rear+1)%maxsize=q.front，就是判定头指针在尾指针的下一个位置上

Answer 3

这个应该是以数组形式保存的环形队列，rear记录了尾部数据的位置，front记录了头部数据的位置，maxsize是数组的大小。
一般在尾部加入数据，在头部移走数据。
这样，如果加入数据快，移走数据慢，尾部追上头部时，如果rear + 1 等于 front了，就说明这个队列满了。
而 (rear + 1) % maxsize，是为了处理rear正好在最后一个数据（等于 maxsize -1）的情况

Answer 4

概念1：队列是尾部入队，头部出队的，先进先出表。
概念2：循环队列，是在同意地址空间能够首尾相接的环形队列。

实际内存是线性的，如果将线性内存在maxsize内看作是一个环，就要解决最大地址的数据的下一个是最小地址的数据。数组就是最大数组下标的下一个是0。
要完成这个计算 是 （（maxsize －1）＋1）％maxsize ＝ 0
要在循环队列中加入一个数据，就要看尾指针的下一个位置，为了正确表明下一个位置，除了＋1，还要循环（即对maxsize取模）。所以就成了(q.rear+1)%maxsize

循环队列的空和满的判断是这样
头 ＝ 尾，说明没有数据入队，所以是空
在不断的有数据入队后，尾转一圈就要追上头了，单绝不可以追上，因为追上原来头存储的数据就会被后入队的数据给破坏，所以循环队列的最大存储是尾还差一个就要追上头
(q.rear+1)%maxsize ＝＝ q.front 则队满。（即尾的下一个位置是头）

Answer 5

%是求余数，一个循环队列，到了底部，数据又重新存储到了头部。
maxsize是最大容量。
实例化的循环队列q，他的队尾位置+1，除以总容量，如果余数是队头的位置，这就说明这个队列已经满了。举例来说，一个4格的队列，编号0 1 2 3.如果放满了，就是（3+1）%4 = 0，就满足(q.rear+1)%maxsize=q.front 。如果没有放满，比如（2+1）%4 ！= 0.
明白了吧