一、数组循环队列
简述一下思想,该循环队列用数组实现,数组大小初始化为5(MaxSize),有头索引(front)和尾索引(rear)。
1.初始状态,头尾索引指向一起,都为0。此时队列为空,判空的依据就是头尾索引是否相等,相等就为空。
2.当入队时,先根据rear入队,而后将rear后移一位,即尾索引其实一直指向队列最后一个元素的下一位。根据这一点和前一点,可知当数组的大小为5时,该队列最多可容纳四个元素,因为如果装入第五个元素,rear将会绕一圈又重新回到front的位置,这时候我们就无法判断是队空还是队满了。
3.这时候就要考虑数组越界问题了,毕竟不能让尾索引一直后移,所以要用到一个小公式(rear+1)%MaxSize,这个公式可以确保尾索引一直在0~4的位置循环。即如果当前尾索引位置是4,那么再移动就是(4+1)%5=0,便又指向0的位置了。入队时注意判队满,队满条件(rear+1)%MaxSize == front;
4.出队时,先将front指向位置的元素取出,而后front后移,后移时依旧采用公式(front+1)%MaxSize。最后注意判队空,队空条件(front==rear)
(1)队列定义
(2)方法声明
(3)方法实现
(4)测试
二、链表普通队列(无头节点链表)
思路与普通的链表没有太大差异,利用头指针和尾指针,入队时采用尾插法,出队时从头部删除。