数据结构--队列的链表实现

在上一篇数据结构--队列的数组实现我们了解到队列到底是什么,以及队列的数组实现。
用数组实现的队列,其实有一些问题,比如当你执行了很多次入队,出队操作的时候,数组的前面都是null,浪费了很多存储空间。
那么有没有其它的实现方式呢?
有,那就是队列的链表实现

1.队列的链表实现需要有哪些方法和属性呢?

  • head: 指向头部结点,初始时为null
  • tail: 指向尾部结点,初始时为null
  • length: 结点长度,初始时为0
  • enqueue: 入队操作,当length为0的时候,head和tail分别指向第一个结点;当length大于0的时候,在尾部添加结点,tail指向尾部结点
  • dequeue: 出队操作,当length为0的时候,直接返回;当length等于1的时候,返回头部结点,head和tail指向null;当length大于1的时候,tail不变,返回头部结点,head指向头部的下一个结点。

2.存储数据的结点有哪些属性呢?

我们需要结点去存储数据,而且它可以指向下一个结点,所以它有两个属性:

  • key: 存储数据
  • next: 指向下一个结点,初始化为null

代码如下:

3.初始化一个空的队列

4.入队操作

根据上面的方法描述我们来实现一下:

1、 当把jack加进队列的时候:
图一:

浅绿色区域代表一个结点。head和tail指向key为jack的第一个结点,第一个结点的next指向null,说明它后面没有结点

2、 当把love加进队列的时候:
图2:

head还是指向key为jack的结点;第一个结点的next指向key为love的结点;尾部结点往后移,指向第二个结点。最后一个结点的next指向null

3、 当把rose加进队列的时候:
图3:

head不变,tail继续往后移

最后在控制台打印出来的数据如下:

可以很清楚地看见结点之间next的指向,jack -> love -> rose

5.出队操作

泰坦尼克号沉了,jack也love不了rose了,我们让这段爱情移除我们的队列,装进我们的记忆里。
关于,dequeue的功能描述上面已经有概述了,我们实现一下:

然后我们,进行出队操作,看看结果:

绿线上面是,jack -> love -> rose的队列,3秒之后,我们进行出队操作,并打印队列,可以看见jack已经被淹死了,head指向了love.

入队,出队操作我们都已经实现了,那么剩下的大家感兴趣的可以去实现一下:

  • isEmpty: 判断它是否为空
  • peek: 返回头部结点存储的key值
    等.....

good night!

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复