本文是一篇用 Java 实现的基于链表的动态队列，使用范型
首先了解一下什么是队列：
引用百度百科：队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
再了解一下什么是链表：
还是引用百度百科：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的 时间复杂度 分别是O(logn)和O(1)。
看完估计有明白的有不明白的，不明白的话就先去了解一下链表和队列吧，本文就不详细普及这两个概念了。
这是我的数据结构练习的github地址，里面会不断更新各种数据结构的java实现，喜欢的话记得star
队列接口YgzQueue
public interface YgzQueue<E> {
//获取队列长度
int size();
//队列是否为空
boolean isEmpty();
//给队尾添加一个元素
void enqueue(E e);
//取出队首元素
E dequeue();
//获取队首的元素
E getFront();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
基于链表的队列实现YgzLinkedQueue
/**
* 基于链表实现的队列
*/
public class YgzLinkedQueue<E> implements YgzQueue<E>{
/**
* 节点对象
*/
private class Node{
//链表的某个节点的实际值
public E e;
//链表某个节点的下一个节点
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@ Override
public String toString(){
return e.toString();
}
}
//链表的头节点和尾节点
private Node head, tail ;
private int size;
/**
* 无参构造
*/
public YgzLinkedQueue(){
head = null;
tail = null;
size = 0;
}
/**
* @Author: Ygz
* @Description:获取队列的内容数量
* @Date：2018/6/24 19:15
* @Param：[]
* @return int
*/
@Override
public int size() {
return size;
}
/**
* @Author: Ygz
* @Description:队列是否为空
* @Date：2018/6/24 19:15
* @Param：[]
* @return boolean
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* @Author: Ygz
* @Description:队列尾新增一个元素，即入队
* @Date：2018/6/24 19:15
* @Param：[e]
* @return void
*/
@Override
public void enqueue(E e) {
//下面描述一下 我这个基于链表队列，链表是有head和tail的，
// 但是在链表头新增和删除元素时间复杂度都是O(1)，在链表尾添加元素也是O(1)，但是在链表尾删除元素的时候
// 由于是单向链表 链表尾不知道它自己的前一个元素节点 所以删除链表尾的元素时间复杂度会变成O(n)
// 这样的话 这里做一个变换
// 我们从链表头删除元素(出队) 链表尾新增元素(入队)
// 这样根据队列先进先出的特性 这个基于链表的队列不管是出队还是入队
// 时间复杂度都是O(1) 操作如下：
if(tail == null){ //如果队尾为null 说明队列为空
tail = new Node(e); //new Node给队尾
head = tail; //队首和队尾一样
}else{
tail.next = new Node(e);//给队尾的下一个赋值new Node 相当于给队尾的位置添加一个元素
tail = tail.next; //更新tail队尾的值
}
size ++;
}
/**
* @Author: Ygz
* @Description:队列首出去一个元素，即出队
* @Date：2018/6/24 19:36
* @Param：[]
* @return E
*/
@Override
public E dequeue() {
if(this.isEmpty())
throw new IllegalArgumentException("队列为空，dequeue失败。");
Node res = head; //首先拿到队首的元素 准备出队留作return
head = head.next; //然后更新head为head的下一个(next)
res.next = null; //要出队的节点的下一个(next)变为null
if(head == null) //这里要注意 经过上一步 head == null 说明队列之前只有1个元素了
tail = null; //所以要更新tail也变成null
size--;
return res.e;
}
/**
* @Author: Ygz
* @Description:查看队列的队首元素
* @Date：2018/6/24 19:57
* @Param：[]
* @return E
*/
@Override
public E getFront() {
if(this.isEmpty())
throw new IllegalArgumentException("队列为空，getFront失败。");
return head.e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res. append ("YgzLinkedQueue: head ");
Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append(" tail");
return res.toString();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
好了 到这就完了 代码复制过去直接运行应该都是可以的 运行都有注释的 希望能帮助到大家 再说一下 我这个只是一个简单的实现 这个还可以做很多的优化 不喜勿喷
这是我的数据结构练习的github地址，里面会不断更新各种数据结构的java实现，喜欢的话记得star
