首页 > 技术文章 > 数组模拟循环队列有效长度计算公式推导(个人理解)

qsbnj 2020-08-27 21:33 原文

关于数组模拟循环队列的有效长度的计算公式,自己参考了一些博客和书上的描述,写了一段推导过程。

 

1.准备

front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素。
front 的初始值 = 0。
rear 指向队列的最后一个元素的后一个位置.,因为希望空出一个空间做为约定。
rear 的初始值 = 0。
arrSize为循环数组长度。
 

2.推导

由于循环队列可循环使用,所以循环队列的有效长度为分为两种情况:

  1.rear > front

  有效长度 = rear - front

  2.rear < front

  有效长度 = front - rear

简而言之就是有效长度为rear与front之间差的绝对值,有效长度 = | rear - front |。

但是计算机中无法使用取绝对值的运算,但是可以利用取模运算符巧妙地实现有效长度的运算:

  有效长度 = | rear - front | = | rear % arrSize - front % arrSize | =  | rear % arrSize - front % arrSize + 0 |  =  | rear % arrSize - front % arrSize  + arrSize % arrSize | = | (rear + arrSize - front) % arrSize | 

  由于rear + arrSize - front > 0,所以

                有效长度 =  (rear + arrSize - front) % arrSize 

推荐阅读