在B站上看韩顺平老师关于数据结构与算法的视频时,在对环形队列进行实现的代码中,有一个公式 (rear + maxSize - front) % maxSize。虽然我认为可以定义一个成员变量,在添加和删除是分别对其进行++ 或 --,但是为了锻炼思维,所以研究了一下这个公式。在对算法的理解中,我主要是带入实例进行思考,所以下面将以实例进行讲解。
- 首先是关于 % maxSize 的的理解。假设数组的length 为4,front=2,rear = 3,当还想在队列中添加元素时,是不是要在下标为0的位置添加呢?因此需要rear = 3 再加1之后得到rear = 0,所以采用 %的方式,(rear + 1)%4 =0。同理, % maxSize在这个公式中的作用也是这样。
- - front的理解。首先 (rear + maxSize - front) % maxSize代表队列中有效元素的个数。举例解释:如果在队列中取走一个值,有效元素会减一,front下标(该处的front不是指公式中的front,而是指队列中的第一个元素)会加一,因此front与有效元素呈现负相关的关系,所以要以 - front的形式出现在该公式中。
- +rear的理解同上。