队列

循环队列

如何判断循环队列是空是满?
办法一:设置一个标志变量flag,当front == rear,且flag = 0时为队列空,当front == rear,且flag = 1时为队列满;
办法二:当队列空时,条件就是front == rear,当队列为满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元。

好像通常都用第二种!
由于rear可能比front大,也可能比front小,所以,尽管它们只相差一个位置时就说满的情况,但也有可能是相差整整一圈。所以,若队列的最大尺寸为N,那么队列满的条件是(rear + 1) % N == front

通用的计算循环队列长度的公式:(rear - front + N) % N