三:常用操作
队列的操作一般分为:
①: 初始化队列。
②: 出队。
③: 入队。
④: 获取队头。
⑤: 获取队长。
1:初始化队列
这个很简单,刚才也说过了,队列是用一个head和tail的指针来维护。分别设置为0即可。
2:出队
看着“队列”的结构图,大家都知道,出队肯定跟head指针有关,需要做两件事情,
第一: 判断队列是否为空,这个我想大家都知道。 第二: 将head头指针向后移动一位,返回head移动前的元素,时间复杂度为O(1)。
代码段如下:
3:入队
这个跟”出队“的思想相反,同样也是需要做两件事情。
第一:判断队列是否已满。
第二:将tail指针向后移动一位,时间复杂度为O(1)。
代码段如下:
4: 获取队头
知道”出队“和”入队“的原理,相信大家都懂的如何进行”获取队头“操作,唯一不一样的就是
他是只读操作,不会破坏”队列“结构,时间复杂度为O(1)。
代码段如下:
5: 获取队长
大家都知道,我们是用数组来实现队列,所以千万不要想当然的认为数组长度是XXX,
我们维护的是一个head和tail的指针,所以长度自然就是tail-head咯,时间复杂度为O(1)。
代码段如下:
然后上一下总的运行代码:
三:顺序队列的缺陷大家看这张图,不知道可有什么异样的感觉,在这种状态下,我入队操作,发现程序提示队列
已满,但是tnd我这个数组还有一个空间啊,是的,这就是所谓的“假溢出”。
四:循环队列
俗话说的好啊,“没有跨不过的坎”。
1: 概念
之所以叫“循环”,得益于神奇的“%”。他让队列的首位进行相连,形成了一个我们思维中的
“圈圈”。
2:循环公式
tail=(tail+1)%array.Length;
多看几眼,大家就看通了其中循环的道理,我要做成如下的图:
3:对循环的改造
先前看了一些资料,有的压根就是错的,有的说想要循环,就要牺牲一个单位的空间。
我觉得没必要。我既要循环又不牺牲空间,所以反射了一下framework中的Queue类。
改造后代码如下: