对环形队列为空留一方式判满与有有效值的理解

对环形队列为空留一方式判满与有有效值的理解

关键就是数组会留一个位置不放值。

判满:

(rear + 1) % maxSize;

当rear大于front时,结果为0。

当rear小于front时,结果为front。

有效值:

(rear + maxSize - front) % maxSize;

% maxSize是为了去掉情况二时加上的maxSize,对情况一结果无影响。

---------------------------------------------------------------------------------------------

rear + maxSize - front:可以看成(rear - front ) + maxSize

涉及到盒子模型

问题:求下方盒子中有数的盒子个数:

情况一: rear 小于 front

对环形队列为空留一方式判满与有有效值的理解

下方元素个数:rear

对环形队列为空留一方式判满与有有效值的理解

 

上方元素个数:maxSize - front

情况二:rear 大于 front

 对环形队列为空留一方式判满与有有效值的理解

 

元素个数: rear - front

至于加上maxSize,是为了与情况一算式格式统一。

 

上一篇:QT小Demo——自制Q群聊天室


下一篇:数据结构与算法——队列