数组模拟循环队列有效长度计算公式推导(个⼈理解)
关于数组模拟循环队列的有效长度的计算公式,⾃⼰参考了⼀些博客和书上的描述,写了⼀段推导过程。
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