如何使用单链表实现队列

队列

队列是一种先进先出的数据结构。

现在有一组数据：12、23、34、45、56

将它们一次放入队列中是如下情况。

有图可以看出队列是从队尾进元素，队头出元素，也就是先进先出。

1.使用尾插法往队列中放一个元素

入队操作是相当于链表的插入一个节点操作。

1.1 入队的思路

• 如果链表是空的则直接让头结点和尾结点指向新的节点。
• 如果不是空的则要在队尾插入一个节点。
• 定义一个 uesdSize 来记录队列中元素个数。

1.2 代码思路

• 定义头结点、尾结点和 uesdSize。

 public ListNode head;//头
 public ListNode tail;//尾
 public int uesdSize = 0;//元素个数
1
2
3

• 定义一个新的节点。

 ListNode node = new ListNode(val);
1

• 判断链表是不是空的。

 if (this.head == null) {
 
 }
1
2
3

• 空的情况 - 头尾结点都指向新的节点。

 this.head = node;
 this.tail = node;
1
2

• 不为空的情况

  tail.next = node;
  tail = tail.next;
1
2

尾结点的地址域存新节点的地址，然后尾结点指向新节点。

关于链表尾插法详解请参考我的另一篇文章：

链接：

https://blog.csdn.net/m0_63033419/article/details/127355701?spm=1001.2014.3001.5501

• 每次插入后，队列的元素个数加一个

  this.uesdSize++;
1

1.3 整体代码展示

 //使用尾插法往队列里放元素
 public void offer(int val) {
     ListNode node = new ListNode(val);
     //如果链表是空的
     if (this.head == null) {
         //将头和尾指向node
         this.head = node;
         this.tail = node;
     }else {
         //链表不是空的 - 在队尾插入结点
         tail.next = node;//尾结点与node链接
         tail = tail.next;//尾结点指向下一个
     }
     this.uesdSize++;//个数加1
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.从队列头部弹出一个元素

出队操作就相当于是从链表的头部删除一个结点。

2.1 出队的思路

• 如果表示空的，就返回-1。
• 若链表不是空的，就定义一个变量来接收当前头结点的值。
• 头结点指向下一个。
• 返回头结点的值。（变量接收）
• 出队后元素个数要减1个

2.2 代码思路

• 判断链表是不是空的 - 为空就返回-1

if (this.head == null) {
    return -1;
}
1
2
3

• 不为空定义变量接收头结点的值

int ret = this.head.val;
1

• 头结点指向下一个结点

 this.head = this.head.next;
1

• 若此时链表为空，将尾部也指向null。

if (this.head == null) {
    this.tail = null;
}
1
2
3

2.3 整体代码展示

 //出队列 - 删除单链表的头结点
 public int poll() {
     //若链表为空
     if (this.head == null) {
         return -1;
     }
     //链表不为空
     int ret = this.head.val;//接受当前头结点的值
     this.head = this.head.next;//head指向下一个
     if (this.head == null) {
         this.tail = null;
     }
     this.uesdSize--;//个数减1
     return ret;//ret就是出队的值
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.获取队头元素但不删除

3.1 获取思路

• 如果链表是空的，直接返回-1.
• 不是空的就返回当前头结点的值。
• 需要注意的是只是接收头结点的值，不改指向。

3.2 代码思路

• 如果链表是空

if (this.head == null) {
    return -1;
}
1
2
3

• 不为空的情况 - 直接返回头结点的值

return this.head.val;
1

3.3 整体代码展示

 public int peek() {
     if (this.head == null) {
         return -1;
     }
     //不为空 - 返回值但不改变指向
     return this.head.val;//返回当前头结点的值
 }
1
2
3
4
5
6
7