首先要明确,在本文中的条件下使用环状队列时候,我们认为队满时会浪费一个位置,一个元素位
从头开始分析,在一开始时,队列呈这个样子
当开始入队时候,real尾部指针开始向后移动
从此刻开始,real就会开始增长
当不断的入队,尾指针到队尾时,就会出现
这种情况我们视为,队列满,为什么会这么判断,要记住,我们这个队列real所在的位置一定是空的,这代表预留的一个空间,所以一定会浪费一个空间
根据计算公式:(real + 1)% maxsize = front 时,我们就认为队列满
为什么要用求模呢?
是这样的,环状队列中,使用Java实现时,我们认为尾指针real是无限自增的,为了保证他不断的递增时候也能判断正确的位置,因此我们使用求模来算出尾指针的真正位置,比如说
注意:这时候:real走了两圈,front必定走了一圈(不出队怎么能入队),同样的计算方法,也能计算队列是满的****
最后一点,为什么判断real = front 时就判断队列为空呢?
因为如果real不相等,就相当于front没有删除real在队中所在的那个元素,就如下:
如果队列为空,即real = front 时,其实就是下列情况:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)