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
网友评论