队列
队列是一种先进先出的线性存储的数据结构，常用于缓存，消息队列（废话 ，我名字都叫队列）。
在进行大量数据交互时，队列能很有效的解决并发问题。
但是又由于队列的先进先出的特性，但队列的进的速度 > 队列出的速度时 ，就会出现以下状况：
在这种情况下肯定是不能进行插入了的,因为队尾指针已经走到最后. 但其实队首指针并不在起始索引的位置, 前面还是有空出的位置 , 但是如果把数据插在这里队列的先进先出的特性也就不复存在了 , 这种情况下就只能把队列中剩余的元素进行整体前移.
前移就前移吧 , 数据量小的时候还算好 , 当数据量大的时候就相当于每次插入操作都要将之前的所有元素前移一位再插入(这个性能耗费程度可想而知).
当然如果会想到用queue去处理缓存这种操作的人肯定也会想到这种情况
要避免每次插入都触发可以设置一个阈值,在插入时做一个判断, 判断剩余空间是否小于阈值 , 小于阈值就将元素移动.
环形队列
上述情况虽然能有效解决普通队列的性能, 但是并不是最优解, 环形队列就可以很有效的解决这种情况 .
首先可以理解一下什么是环形队列
在计算机中并不存在环形结构, 数据保存都是线性下去的. 环形只是我们使用指针来进行取模运算做到的环形效果.
环形队列实现
首先理一下环形队列存取数据的逻辑:
- 内部维护两个指针 , 一个队首指针
head, 一个队尾指针end.
- 普通队列判断队空的条件 :
head == end , 环形队列亦是.
- 普通队列判断队满的条件 :
(end + 1) % max == head , max为队列最大长度 , 加一为预留一个空位用作环形判断, 因为是环形结构 , 存到队列最大长度后,继续往队首继续存放 , 所以需要进行取模运算, 如果取模运算后和队首指针相同则该队列已满.
逻辑理清楚后可以开始环形队列的实现
这里内部数据存放使用数组:
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
| package weison.test;
public class roundQueue {
private Object[] arr;
private int maxLength, head, end;
public roundQueue(){
this.maxLength = 10;
arr = new Object[maxLength];
head = end = 0;
}
public roundQueue(int maxLength){
this.maxLength = maxLength;
arr = new Object[maxLength];
head = end = 0;
}
public Object[] getArr() {
return arr;
}
public void setArr(Object[] arr) {
this.arr = arr;
}
public boolean isEmpty(){
return head == end;
}
public boolean isFull(){
return (end + 1) % maxLength == head;
}
public void push(Object o){
if(isFull()){
System.out.println("队列已满,无法插入");
}
arr[end] = o;
end = (end + 1) % maxLength;
}
public Object pull(){
if (isEmpty()){
System.out.println("队列为空 , 无法取出数据");
}
Object temp = arr[head];
arr[head] = null;
head = (head + 1) % maxLength;
return temp;
}
}
|
环形队列测试
1
2
3
4
5
6
7
8
9
10
| public static void main(String[] args) {
roundQueue queue = new roundQueue(4);
queue.push(1);
queue.push(2);
queue.push(3);
queue.print();
}
|
输出结果 :
当前环形队列的内部情况就如图所示:
目前如果再去插入的话就会提示已经插满(因为需要一个位置去做环形判断) , 现在进行取出操作,取出两个然后继续执行插入:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void main(String[] args) {
roundQueue queue = new roundQueue(4);
queue.push(1);
queue.push(2);
queue.push(3);
queue.print();
System.out.println("=========================================");
queue.pull();
queue.pull();
queue.print();
}
|
输出结果:
现在队列中的情况应该是这个样子的了:
那么既然是环形结构,我再继续往里面push,肯定是继续往后面加的再加两个上去应该是这个样子:
用普通的线性队列来表示的现在应该是这样的:
那我们现在执行下插入操作后再遍历看看效果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void main(String[] args) {
roundQueue queue = new roundQueue(4);
queue.push(1);
queue.push(2);
queue.push(3);
queue.print();
System.out.println("=========================================");
queue.pull();
queue.pull();
queue.print();
System.out.println("=========================================");
queue.push(4);
queue.push(5);
queue.print();
}
|
测试结果:
可以看出 , 实际效果也和我们猜测的相同.