数据结构之队列
1、队列Queue，队列也是一种线性结构，相比数组，队列对应的操作是数组的子集，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。队列是一种先进先出的数据结构（或者称为先到先得），First In First Out（简称FIFO）。
2、封装的数组的代码，可以实现增加，修改，删除，查询，动态扩容，缩容，判断是否为空等等方法。
1 package com.company;
2
3
4 /**
5 *
6 */
7 public class Array<E> {
8
9 private E[] data;//定义数组
10 private int size;//数组实际的长度
11
12 /**
13 * 构造函数，传入数组的容量capacity构造Array
14 *
15 * @param capacity 初始化数据的容量长度
16 */
17 public Array(int capacity) {
18 // 使用泛型，可以创建任意类型的数组类型
19 data = (E[]) new Object[capacity];
20 // 初始化数组的实际内容的长度为0
21 size = 0;
22 }
23
24 /**
25 * 无参数的构造函数，默认数组的容量capacity=10
26 */
27 public Array() {
28 // 无参构造函数，指定初始化数组容量长度为0
29 this(10);
30 }
31
32 /**
33 * 获取数组中的元素个数
34 *
35 * @return
36 */
37 public int getSize() {
38 // 获取到数组中的元素个数
39 return size;
40 }
41
42 /**
43 * 获取数组的容量
44 *
45 * @return
46 */
47 public int getCapacity() {
48 // 获取到数组的容量
49 return data.length;
50 }
51
52 /**
53 * 返回数组是否为空
54 *
55 * @return
56 */
57 public boolean isEmpty() {
58 // 判断数组的长度是否为空
59 return size == 0;
60 }
61
62
63 /**
64 * 向所有元素后添加一个新元素
65 *
66 * @param e
67 */
68 public void addLast(E e) {
69 // if (size == data.length) {
70 // throw new IllegalArgumentException("AddLast failed,Array is full......");
71 // } else {
72 // 在数组的末尾添加一个元素
73 // data[size] = e;
74 // 添加元素以后数组长度加一
75 // size++;
76 // }
77
78 // 调用公共的方法，其实就是在数组的实际长度后面添加指定的元素的。
79
80 // 调用添加数组的方法，参数一，传入数组实际的长度，参数二，添加的元素
81 add(size, e);
82 }
83
84 /**
85 * 在第一个位置添加元素，在所有元素前添加一个新元素
86 *
87 * @param e
88 */
89 public void addFirst(E e) {
90 // 在数组的第一个位置添加元素
91 add(0, e);
92 }
93
94
95 /**
96 * 在第index个位置插入一个新元素e
97 *
98 * @param index 在第index个位置
99 * @param e 添加的元素内容
100 */
101 public void add(int index, E e) {
102 // 判断位置index是否小于0或者索引index是否大于数组的实际长度size
103 if (index < 0 || index > size) {
104 throw new IllegalArgumentException("add failed,Require index >= 0 and index <= size.......");
105 }
106
107 // 判断实际长度size是否等于数组的长度
108 if (size == data.length) {
109 // 可以直接抛出异常
110 // throw new IllegalArgumentException("add failed,Array is full......");
111 // 调用数组扩容的方法，扩容的长度为元数组长度的2倍
112 resize(2 * data.length);
113 }
114
115 // 添加元素，就是在最后一个位置，将元素添加进去，即size的位置
116 // 从后向前移动，从后面的元素向后移动
117 // 如果传入的index是size，则初始化的位置是size-1，那么i的值大于等于传入的index(即size的值)，i递减
118
119 // int i = size - 1是数组的实际长度的，即最后一个位置的元素
120 // i >= index，是在指定索引位置添加索引
121 // i--是为了将前面的元素向后面移动的。
122 for (int i = size - 1; i >= index; i--) {
123 // 后一个索引位置赋予前一个索引位置的值
124 data[i + 1] = data[i];
125 }
126 // 将元素的内容插入到数组的index索引位置
127 data[index] = e;
128 // 数组的size递增
129 size++;
130 }
131
132 /**
133 * 私用扩容，扩容数组的长度
134 *
135 * @param newCapacity
136 */
137 private void resize(int newCapacity) {
138 // 使用泛型创建对象，使用new Object的方法创建泛型的对象
139 E[] newData = (E[]) new Object[newCapacity];
140 // 循环，将原数组里面的内容放入到新数组里面，新数组的长度为元素组的2倍
141 for (int i = 0; i < size; i++) {
142 // 将原数组的值赋值给新数组的值
143 newData[i] = data[i];
144 }
145 // 将原数组的值指向新数组，此操作，不影响原数组的正常使用
146 data = newData;
147 }
148
149 /**
150 * 获取Index索引位置的元素
151 *
152 * @param index
153 * @return
154 */
155 public E get(int index) {
156 // 如果索引index小于0或者索引的长度大于等于实际长度size，则抛出异常
157 if (index < 0 || index >= size) {
158 throw new IllegalArgumentException("add failed,Index is illegal......");
159 }
160 // 返回指定索引位置的数组元素
161 return data[index];
162 }
163
164 /**
165 * 获取到动态数组的第一个元素
166 *
167 * @return
168 */
169 public E getFirst() {
170 return get(0);
171 }
172
173 /**
174 * 获取到数组的最后一个元素
175 *
176 * @return
177 */
178 public E getLast() {
179 // 调用获取元素的方法
180 // 避免使用return data[size - 1]，可能会出现size=0的情况
181 return get(size - 1);
182 }
183
184 /**
185 * 修改index索引位置的元素e
186 *
187 * @param index
188 */
189 public void set(int index, E e) {
190 // 如果索引index小于0或者索引的长度大于等于实际长度size，则抛出异常
191 if (index < 0 || index >= size) {
192 throw new IllegalArgumentException("add failed,Index is illegal......");
193 }
194 // 则将元素放入到数组的索引index位置
195 data[index] = e;
196 }
197
198
199 /**
200 * @return
201 */
202 @Override
203 public String toString() {
204 // 封装数组遍历的内容
205 StringBuilder sb = new StringBuilder();
206 sb.append(String.format("Array : size = %d,capacity = %d\n", size, data.length));
207 sb.append('[');
208 for (int i = 0; i < size; i++) {
209 sb.append(data[i]);
210 if (i != size - 1) {
211 sb.append(", ");
212 }
213 }
214 sb.append(']');
215 return sb.toString();
216 }
217
218 /**
219 * 查找数据中是否包含元素e
220 *
221 * @param e
222 * @return
223 */
224 public boolean contains(E e) {
225 // 查看是否包含元素，进行遍历
226 for (int i = 0; i < size; i++) {
227 // 如果数组元素等于传入的元素e
228 if (data[i].equals(e)) {
229 // 返回true
230 return true;
231 }
232 }
233 return false;
234 }
235
236 /**
237 * 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
238 *
239 * @param e
240 * @return
241 */
242 public int find(E e) {
243 // 查看是否包含元素，进行遍历
244 for (int i = 0; i < size; i++) {
245 // 如果数组元素等于传入的元素e
246 if (data[i].equals(e)) {
247 // 返回该索引位置的索引
248 return i;
249 }
250 }
251 return -1;
252 }
253
254 /**
255 * 从数组中删除index位置的元素，返回删除的元素
256 *
257 * @param index 此参数是索引参数
258 * @return
259 */
260 public E remove(int index) {
261 // 如果索引位置小于等于0或者索引位置大于等于数组的实际长度size
262 if (index < 0 || index >= size) {
263 throw new IllegalArgumentException("remove failed,Index is illegal......");
264 }
265
266 // 返回删除的元素，先获取到要删除的元素
267 E result = data[index];
268 // System.out.println(result);
269
270 // 初始化值是要删除索引的位置加1，且i的值小于实际size的大小，i递减
271
272 // int i = index + 1，传入进去的删除索引位置的元素
273 // i < size，i小于数组的实际长度
274 // i++，i递增
275 for (int i = index + 1; i < size; i++) {
276 // 将数组元素的值赋值被删除元素的位置上面
277 // 即将数组元素向前移动，即第i位置的索引的数据移动到第i-1位置索引的数据
278 data[i - 1] = data[i];
279 }
280 // 删除元素以后，数组长度size递减1
281 size--;
282 // 将不可访问的位置置空
283 data[size] = null;
284
285 // 避免出现复杂度震荡
286 // 删除数组长度，缩小容量
287 // data.length / 2 != 0，避免出现创建数组长度为0的数组
288 if (size == data.length / 4 && data.length / 2 != 0) {
289 // 缩容数组的长度
290 resize(data.length / 2);
291 }
292 return result;
293 }
294
295 /**
296 * 删除数组的第一个元素的值
297 * <p>
298 * 从删除中删除第一个元素，返回删除的元素
299 *
300 * @return
301 */
302 public E removeFirst() {
303 // 删除数组的第一个位置的元素
304 return remove(0);
305 }
306
307 /**
308 * 从数组中删除最后一个元素，返回删除的元素。
309 *
310 * @return
311 */
312 public E removeLast() {
313 // 删除数组最后一个位置的元素
314 return remove(size - 1);
315 }
316
317 /**
318 * 从数组中删除元素e
319 *
320 * @param e
321 */
322 public void removeElement(E e) {
323 // 查看数组里面是否有该元素
324 int index = find(e);
325 // 如果查找到存在该元素
326 if (index != -1) {
327 // 调用删除数组元素的方法
328 remove(index);
329 }
330 }
331
332 public static void main(String[] args) {
333 // 数组添加元素
334 Array<Integer> array = new Array<>(20);
335 for (int i = 0; i < 10; i++) {
336 array.addLast(i);
337 }
338
339 System.out.println(array.toString());
340
341 // 在指定位置添加元素
342 array.add(1, 110);
343 System.out.println(array.toString());
344
345 // 在第一个位置添加元素
346 array.addFirst(-1);
347 System.out.println(array.toString());
348
349 // 修改index索引位置的元素e
350 array.set(1, 120);
351 System.out.println(array.toString());
352
353 // 是否包含某个元素
354 boolean contains = array.contains(9);
355 System.out.println(contains);
356
357 // 删除指定索引位置的元素
358 array.remove(2);
359 System.out.println(array);
360
361 // 删除第一个索引位置的元素
362 array.removeFirst();
363 System.out.println(array);
364
365 // 删除最后一个位置的元素
366 array.removeLast();
367 System.out.println(array);
368
369 // 从数组中删除元素e
370 array.removeElement(110);
371 System.out.println(array);
372 }
373
374 }3、使用泛型，可以接受任何数据类型的。声明队列的接口。
1 package com.queue;
2
3 /**
4 *
5 */
6 public interface Queue<E> {
7
8 /**
9 * 向队列中添加一个元素，入队。对应栈的入栈。
10 *
11 * @param e
12 */
13 public void enqueue(E e);
14
15 /**
16 * 从队列中取出一个元素，出队。对应栈的出栈。
17 *
18 * @return
19 */
20 public E dequeue();
21
22 /**
23 * 获取到队列中队首的元素。对应栈的查看栈顶的元素。
24 *
25 * @return
26 */
27 public E getFront();
28
29 /**
30 * 获取到队列的大小
31 *
32 * @return
33 */
34 public int getSize();
35
36 /**
37 * 判断队列是否为空
38 *
39 * @return
40 */
41 public boolean isEmpty();
42
43 }创建实现Queue自定义接口队列的类，QueueStack队列，结合创建的Array<E>动态数组来实现栈的入队，出队，查看队首元素，判断队列是否为空等等操作。
1 package com.queue;
2
3 import com.company.Array;
4
5 /**
6 * 队列是一种先进先出的数据结构（或者称为先到先得），First In First Out（简称FIFO）。
7 * <p>
8 * <p>
9 * 1、public void enqueue(E e)入队方法，时间复杂度0(1)，均摊时间复杂度。
10 * 2、public E dequeue()出队方法，时间复杂度0(n)。因为队首元素拿出去以后，后面所有元素前移一位。
11 * 如果数据量很大，这回造成执行很慢，使用循环队列可以使时间复杂度变成O(1)。
12 * 3、public E getFront()获取队首方法，时间复杂度0(1)。
13 * 4、public int getSize()获取队列大小，时间复杂度0(1)。
14 * 5、public boolean isEmpty()获取队列是否为空，时间复杂度0(1)。
15 *
16 * @param <E>
17 */
18 public class ArrayQueue<E> implements Queue<E> {
19
20 // 声明一个Array对象
21 private Array<E> array;
22
23
24 // Fn + Alt + Insert快捷键弹出构造函数
25
26 /**
27 * @param capacity 动态数组的容量大小
28 */
29 public ArrayQueue(int capacity) {
30 //
31 array = new Array<>(capacity);
32 }
33
34 /**
35 * 无参的栈构造函数，创建一个默认容量大小的动态数组
36 */
37 public ArrayQueue() {
38 array = new Array<>();
39 }
40
41 /**
42 * 入队
43 *
44 * @param e
45 */
46 @Override
47 public void enqueue(E e) {
48 // 即向数组的末尾添加元素，如果动态数组容量不够，会触发动态数组的扩容机制
49 array.addLast(e);
50 }
51
52 /**
53 * 出队
54 *
55 * @return
56 */
57 @Override
58 public E dequeue() {
59 // 队列，是先进先出的，所以出队，是将开始的元素进行删除即可
60 E first = array.removeFirst();
61 return first;
62 }
63
64 /**
65 * 获取队首元素
66 *
67 * @return
68 */
69 @Override
70 public E getFront() {
71 // 获取到队首元素
72 E first = array.getFirst();
73 return first;
74 }
75
76 /**
77 * 查看队列大小
78 *
79 * @return
80 */
81 @Override
82 public int getSize() {
83 // 返回队列的大小
84 return array.getSize();
85 }
86
87 /**
88 * 判断队列是否为空
89 *
90 * @return
91 */
92 @Override
93 public boolean isEmpty() {
94 // 返回队列是否为空
95 return array.isEmpty();
96 }
97
98 /**
99 * 获取到队列的容量大小
100 *
101 * @return
102 */
103 public int getCapacity() {
104 return array.getCapacity();
105 }
106
107 @Override
108 public String toString() {
109 StringBuilder sb = new StringBuilder();
110 sb.append("Queue: ");
111 sb.append("front [");
112 for (int i = 0; i < array.getSize(); i++) {
113 sb.append(array.get(i));
114 if (i != array.getSize() - 1) {
115 sb.append(", ");
116 }
117 }
118 sb.append("] tail");
119 return sb.toString();
120 }
121
122 public static void main(String[] args) {
123 ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
124 // 入队操作
125 for (int i = 0; i < 10; i++) {
126 arrayQueue.enqueue(i);
127 System.out.println(arrayQueue);
128 }
129
130 // 出队操作
131 arrayQueue.dequeue();
132 System.out.println("出队操作: " + arrayQueue);
133
134 // 获取到队列的大小
135 int size = arrayQueue.getSize();
136 System.out.println("获取到队列的大小: " + size);
137
138 // 获取到队首的元素
139 Integer front = arrayQueue.getFront();
140 System.out.println("获取到队首的元素: " + front);
141
142 // 判断队列是否为空
143 System.out.println("判断队列是否为空: " + arrayQueue.isEmpty());
144 }
145
146 }4、循环队列，初始的情况下，队列中无任何元素，front指向0位置，tail也指向0的位置。
1）、注意，front应该指向队列的第一个元素，tail指向的位置是指队列中最后一个元素的后一个位置。但是，当队列整体为空的时候，即队列中连第一个元素都没有的时候，此时，front和tail指向同一个位置，都是指向0的位置，即front和tail相等的时候，队列为空。 2）、如果队列不为空的时候，front和tail是不会相等的，如果此时，有一个元素入队了，此时，只要维护tail队尾就行了，tail指向下一次一个元素再入队时候的位置。如果是出队，只需要维护front即可，将front向下一个位置移动一个就行了。 3）、循环队列，如果出现出队操作，不再要求所有的元素都进行移动了，只需要front的指向改变即可，时间复杂度就变成了O(1)的操作。 4）、循环队列，如果队列的队尾tail移动到最后一个位置的时候，如果队列的队首front前面还有空闲的位置，那么队列的队尾tail可以指向队列的队首front的前面的位置。此时，队列可以看成是一个环形。 5）、front和tail相等的时候，队列为空。所以队列的队首front和队列的队尾tail之间会存在一个空闲的位置，是无法被填写元素的。队列的队满是tail + 1 == front，表示队列的队满，准确的说，是(tail + 1) % c == front表示队列队满了。 6）、tail指向的位置是指下一次有元素入队应该放入的位置，一旦有一个新的元素放入了，tail就应该加一。 7）、循环队列中，在capacity容量中，浪费一个空间。如果只剩下一个空间的时候，循环队列就已经满了，就可以进行扩容了。
4.1、循环队列的入队操作。
a、b、c、d、e元素入队，维护tail的位置，tail进行自增操作就行了。
4.2、循环队列的出队操作，此时，如果要进行循环队列出队操作，那么如何进行的呢。如果元素a出队，那么需要对front进行维护即可。
如果此时，b元素进行出队操作，如下所示：
4.3、循环队列的循环操作。
循环队列是如何进行循环操作的。准确的说是(tail + 1) % c == front表示循环队列满了。由于到了数组的末端，还可以返回到数组的前端，跑到数组前端的过程就是靠的求余操作。front == tail表示循环队列为空了。
1 package com.queue;
2
3 /**
4 * 循环队列
5 *
6 * @param <E>
7 */
8 public class LoopQueue<E> implements Queue<E> {
9
10 private E[] data;//创建一个E类型的数组。
11 private int front;//定义一个变量，表示队首指向的索引位置，指向队首所在的索引。
12 private int tail;//定义一个变量，队列最后一个元素下一个位置，新元素入队存放的位置对应的索引。
13 private int size;//队列里面有多少个元素。
14
15 /**
16 * 创建一个含参构造函数
17 *
18 * @param capacity 数据的容量大小，用户期望的循环队列的容量大小
19 */
20 public LoopQueue(int capacity) {
21 // 创建一个E类型的数组data
22 // 由于循环队列，需要浪费一个空间，所以容量大小是用户期望的容量大小加一。
23 data = (E[]) new Object[capacity + 1];
24 // 成员变量初始化大小
25 front = 0;//指向队首所在的索引为0
26 tail = 0;//队列最后一个元素下一个位置的索引为0
27 size = 0;//循环队列的大小为0
28 }
29
30 /**
31 * 创建一个无参的构造函数，初始化循环队列的容量为10
32 */
33 public LoopQueue() {
34 // 初始化容量为10的循环队列
35 this(10);
36 }
37
38 /**
39 * 入队操作
40 *
41 * @param e
42 */
43 @Override
44 public void enqueue(E e) {
45 // 首先判断队列是否是满的。
46 // 判断的标准就是队尾tail加一取余循环队列的长度即下一个tail的值等于队首front，就表示队列满了。
47 // 取余操作，是让循环队列的整个索引循环起来，类比钟表循环。
48 // 假如front是一点钟，tail是十二点钟，那么十二加一，取余十二就等于一，那么就表示该循环队列满了。
49 // 因为循环队列要空出一个位置。
50 if ((tail + 1) % data.length == front) {
51 // 如果循环队列满了，进行循环队列扩容。扩容的大小是，此时循环队列的最多可以存放元素的个数乘以2
52 // 此处，不使用data.length乘以二，因为data.length和循环队列最多可以盛放的元素个数之间有一个一的差距。
53 resize(this.getCapacity() * 2);
54 }
55
56 // 此时，将要存放的元素存放到tail的位置上面。
57 data[tail] = e;
58 // 此时，因为是在循环队列里面，维护一下tail的位置。
59 tail = (tail + 1) % data.length;
60 // 维护size的大小
61 size++;
62 }
63
64 /**
65 * 循环队列进行扩容操作
66 *
67 * @param newCapacity
68 * @return
69 */
70 private void resize(int newCapacity) {
71 // 创建一个新的数组，将之前的元素放入到新的数组里面
72 // 由于循环队列，需要浪费一个空间，所以容量大小是用户期望的容量大小加一。
73 E[] newData = (E[]) new Object[newCapacity + 1];
74
75 // 将之前的数组的所有元素，放入到新的数组里面
76 for (int i = 0; i < size; i++) {
77 // 将之前的数组的所有元素放入到新的数组的从零到size减一索引的位置上面。
78 // 在之前的data数组里面，front队首元素有可能不是在零索引位置上面的，比如出队操作。
79 // 此时，将data数组里面front队首元素放到新的数组里面的零索引的位置上面。
80 // 此时newData[i]的位置不是对应data[i]的位置。
81 // 因为newData[0]对应的就是data[front]，那么newData[1]对应的就是data[front + 1]，以此类推。
82 // 所以说，newData[i]对应的是data[(i + front) % data.length]
83 // data中的所有元素相对于newData中的所有元素索引值有一个(i + front)偏移的。
84 // 由于整个队列是循环队列，所以队列要循环起来，(i + front)的值有可能会超过data的length长度，产生越界。
85 // 所以可以进行取余数据长度操作。
86 newData[i] = data[(i + front) % data.length];
87 }
88
89 // 将原来的数组data指向扩容以后的新数组newData
90 data = newData;
91 // 此时队首front变成了0
92 front = 0;
93 // 队尾tail变成了size，循环队列里面的元素个数不需要改变
94 tail = size;
95 }
96
97 /**
98 * 出队操作
99 *
100 * @return
101 */
102 @Override
103 public E dequeue() {
104 // 首先，判断队列是否为空，如果为空，直接抛出异常
105 if (this.isEmpty()) {
106 throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
107 }
108
109 // 否则，如果此时队列不为空，就进行出队操作
110 // 首先，对要出队的元素进行保存
111 E result = data[front];
112 // 将出队的元素的位置指向null。
113 data[front] = null;
114
115 // 维护front，因为是循环队列
116 front = (front + 1) % data.length;
117
118 // 维护size的大小，由于是出队，所以size的大小减一
119 size--;
120
121 // 出队，可以进行扩容操作，节约资源。如果size大小等于容量的四分之一的时候，就缩容到之前的二分之一
122 // 并且缩容的值不等于0
123 if (size == this.getCapacity() / 4 && this.getCapacity() / 2 != 0) {
124 this.resize(this.getCapacity() / 2);
125 }
126
127 // 返回出队的元素内容
128 return result;
129 }
130
131 /**
132 * 查看循环队列的队首元素
133 *
134 * @return
135 */
136 @Override
137 public E getFront() {
138 // 首先，判断队列是否为空，如果为空，直接抛出异常
139 if (this.isEmpty()) {
140 throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
141 }
142 return data[front];
143 }
144
145 /**
146 * 获取到循环队列的大小
147 *
148 * @return
149 */
150 @Override
151 public int getSize() {
152 // 由于size就是维护的循环队列的大小
153 return size;
154 }
155
156 /**
157 * 判断循环队列是否为空
158 *
159 * @return
160 */
161 @Override
162 public boolean isEmpty() {
163 // 循环队列的队首front等于循环队列的队尾指向的下一个位置的tail相等的时候，即循环队列为空
164 return front == tail;
165 }
166
167 /**
168 * 返回循环队列的容量大小，初始化的时候容量加一，此时获取到循环队列容量的时候，记得减一。
169 *
170 * @return
171 */
172 public int getCapacity() {
173 // 扩容的时候，data发生变化，那么扩容以后的data.length的长度就发生了变化
174 return data.length - 1;
175 }
176
177 @Override
178 public String toString() {
179 // 封装数组遍历的内容
180 StringBuilder sb = new StringBuilder();
181 sb.append(String.format("LoopQueue : size = %d,capacity = %d\n", size, this.getCapacity()));
182 sb.append("front [");
183 // 切记，i的初始化值是front。
184 // i的最大值是不可以取到tail的值的。
185 // i递增是(i + 1) % data.length。因为是循环队列。
186 for (int i = front; i != tail; i = (i + 1) % data.length) {
187 sb.append(data[i]);
188 // 如果当前的索引不是最后一个元素的时候
189 if ((i + 1) % data.length != tail) {
190 sb.append(", ");
191 }
192 }
193 sb.append(" ] tail ");
194 return sb.toString();
195 }
196
197 public static void main(String[] args) {
198 LoopQueue<Integer> loopQueue = new LoopQueue<>();
199 // 入队操作
200 for (int i = 0; i < 20; i++) {
201 loopQueue.enqueue(i);
202 System.out.println(loopQueue.toString());
203 }
204
205 System.out.println();
206 // 出队操作
207 loopQueue.dequeue();
208 System.out.println("循环队列出队操作: " + loopQueue);
209
210 // 获取到队列的大小
211 int size = loopQueue.getSize();
212 System.out.println("获取到循环队列的大小: " + size);
213
214 // 获取到队首的元素
215 Integer front = loopQueue.getFront();
216 System.out.println("获取到循环队列队首的元素: " + front);
217
218 // 判断队列是否为空
219 System.out.println("判断循环队列是否为空: " + loopQueue.isEmpty());
220 }
221
222 }执行效果，如下所示：
5、数组队列和循环队列的比较，性能测试。
1 package com.queue;
2
3 import java.util.Random;
4
5 /**
6 *
7 */
8 public class Main {
9
10 /**
11 * 测试使用queue运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
12 *
13 * @param queue
14 * @param opCount
15 * @return
16 */
17 public static double queuePerforms(Queue<Integer> queue, int opCount) {
18 // 开始时间
19 long startTime = System.nanoTime();
20
21 Random random = new Random();
22 // 入队操作
23 for (int i = 0; i < opCount; i++) {
24 queue.enqueue(random.nextInt(Integer.MAX_VALUE));
25 }
26
27 // 出队操作
28 for (int i = 0; i < opCount; i++) {
29 queue.dequeue();
30 }
31
32 // 结束时间
33 long endTime = System.nanoTime();
34
35 // 秒与纳秒之前差九位数
36 return (endTime - startTime) / 1000000000.0;
37 }
38
39 public static void main(String[] args) {
40 int opCount = 1000000;// 一百万次
41
42 // 数组队列的性能
43 // 影响数组队列性能的是出队操作，因为每一个元素都要进行前移操作
44 ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
45 double time1 = queuePerforms(arrayQueue, opCount);
46 System.out.println("ArrayQueue, time: " + time1 + " s");
47
48
49 // 循环队列的性能
50 LoopQueue<Integer> loopQueue = new LoopQueue<>();
51 double time2 = queuePerforms(loopQueue, opCount);
52 System.out.println("LoopQueue, time: " + time2 + " s");
53 }
54
55 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读