七叶笔记 » java编程 » 算法系列15天速成 第九天 队列

算法系列15天速成 第九天 队列

三:常用操作

      队列的操作一般分为:

      ①: 初始化队列。

      ②:   出队。

      ③: 入队。

      ④: 获取队头。

      ⑤: 获取队长。

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类。

      改造后代码如下:

相关文章