Summary
- 什么是环形队列
- 实现环形队列图示过程
- golang版本代码实现过程
- 参考全部代码
什么是环形队列
在一个指定大小的数组里循环写入数据,借用二个指针分别实现入队标记与出队标记.也体现了指针的大好用处,请深入体会.大有裨益.
如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针.
实现环形队列图示过程
初始化一个数组大小为6的环形队列, 头指针frOnt=0, 尾指针rear=0, 刚好frOnt=rear =0的状态,表示环形队列为空.
2.向环形队列里插入1个元素,则rear指针移动一格,frOnt=0,rear=1
3.继续添加a2,a3,a4,a5元素,rear指针指到末尾处,frOnt=0, reat=5
4.如果再继续添加a6元素,则rear=6,大于数组大小,发生数组溢出.
5.如上图所示添加a6时,rear指针发生溢出.我们使用一个小技巧,当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我们无法判断数组是否满&＃63;因为初始化时frOnt=rear=0, 现在数组满也是frOnt=rear=0
6.解决以上问题有三种办法,我们采用第3种方法实现.
使用第3种方法: 即当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素
golang版代码实现过程
a. 定义环形数据结构
b.初始化环形队列
c. 入队操作
d.出队操作
e:求当前的环形队列长度
参考全部代码
github
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。