概述
队列，又称为伫列（queue），计算机科学中的一种抽象资料型别，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
从上述的概念中我们可得知，队列两个主要的操作为入队(enqueue)与出队(dequeue)，入队为从队尾插入元素，出队为从队首去删除元素。
数组实现队列
数组实现的队列即元素容器为数组，为了完成入队与出队列的操作，同时还需要两个指针来标记队首和队尾。
代码实现
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
| public class ArrayQueueTest {
private final int[] items;
/**
* front 队首指针
* rear 对尾指针
* capital 队列容量
*/
private int front, rear, capital;
public ArrayQueueTest(Integer capital) {
this.items = new int[capital];
this.capital = capital;
this.front = rear = 0;
}
/**
* 从队尾插入元素
*
* @param item 元素
*/
public void add(int item) {
// 当前容量已满
if (rear == capital) {
if (front == 0) {
throw new RuntimeException("队列已满");
} else {
// 所有元素向前移动一位
for (int i = 0; i < items.length - 1; i++) {
items[i] = items[i + 1];
}
// 队尾指针向前移动一位，同时队首指针向前移动一位
rear--;
front--;
}
}
items[rear] = item;
rear++;
}
/**
* 从队首取出元素
*
* @return 队首取出的元素
*/
public int remove() {
if (front == capital) {
throw new RuntimeException("队列为空");
}
int item = items[front];
front++;
return item;
}
/**
* 获取队列所有元素
*
* @return 队列所有元素数组
*/
public int[] getItems() {
int[] outItems = new int[rear - front];
for (int i = 0; i < outItems.length; i++) {
outItems[i] = items[front + i];
}
return outItems;
}
public static void main(String[] args) {
ArrayQueueTest arrayQueue = new ArrayQueueTest(5);
arrayQueue.add(1);
arrayQueue.add(2);
arrayQueue.add(3);
arrayQueue.add(4);
arrayQueue.add(5);
System.out.println(Arrays.toString(arrayQueue.getItems()));
for (int i = 0; i < 5; i++) {
int removeItem = arrayQueue.remove();
System.out.println(removeItem);
System.out.println(Arrays.toString(arrayQueue.getItems()));
}
arrayQueue.add(8);
System.out.println(Arrays.toString(arrayQueue.getItems()));
arrayQueue.add(9);
System.out.println(Arrays.toString(arrayQueue.getItems()));
// for (int i = 10; i < 20; i++) {
// arrayQueue.add(i);
// System.out.println(Arrays.toString(arrayQueue.getItems()));
// }
// for (int i = 0; i < 10; i++) {
// System.out.println(arrayQueue.remove());
// System.out.println(Arrays.toString(arrayQueue.getItems()));
// }
}
}
|