/
LinkedListQueue.java
128 lines (104 loc) · 2.67 KB
/
LinkedListQueue.java
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
package Queue;
public class LinkedListQueue<E> implements Queue<E> {
//将Node节点设计成私有的类中类
private class Node<E> {
public E e;
public Node next;
//两个参数的构造函数
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
//一个参数的构造函数
public Node(E e) {
this.e = e;
this.next = null;
}
//无参构造函数
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node<E> head, tail;
private int size;
//显示初始化
public LinkedListQueue() {
head = null;
tail = null;
size = 0;
}
//获取队列中节点个数
@Override
public int getSize() {
return size;
}
//队列中是否为空
@Override
public boolean isEmpty() {
return size == 0;
}
//链表尾部进队操作
@Override
public void enqueue(E e) {
if (tail == null) {
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
//链表头部出队操作
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("链表为空");
}
Node<E> retNode = head;
head = head.next;
retNode.next = null;
if (head == null) {//当链表只有一个元素时
tail = null;
}
size--;
return retNode.e;
}
//获取队首元素
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("链表为空");
}
return head.e;
}
//为了便于测试,重写object类toString()方法
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node<E> cur = head;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
//测试用例
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 == 2) {//每添加3个元素出队列一个
queue.dequeue();
System.out.println(queue);
}
}
}
}