99网
您的当前位置:首页数组模拟循环队列有效长度计算公式推导(个人理解)

数组模拟循环队列有效长度计算公式推导(个人理解)

来源:99网
数组模拟循环队列有效长度计算公式推导(个⼈理解)

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

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

因篇幅问题不能全部显示,请点此查看更多更全内容