队列
什么是队列就不多bb了，反正就是先进先出的一种东东。它可以用链表或者数组实现，这一节讲的是用数组实现。
反正核心就是用数组去模拟队列，这个类中有四个成员属性：最大容量、数组、头部（我们约定不含有它）、尾部（我们约定含有它）。
为什么不含有头部，含有尾部？TMD，这只是个约定，你也可以反过来，不过这其实都是小问题，我们没必要去计较它们，主要你要有自己的约定，然后后续慢慢的去实现它。
下面我们先玩普通的数组去模拟队列，等我们把它实现之后，我们就发现它有个缺点，然后我们对它进行一点改进，改成用循环的数组去模拟队列就可以解决它的这一缺点了。OK，继续探索队列吧。
数组模拟队列
数组模拟队列的思想是什么？且看下图：
初始化一个大小为maxSize的数组，令其 rear 和 front 都为-1，然后添加元素，我们也叫入队。入队怎么办？生活中我们排队都是从后面入队，所以肯定是rear向后加1呗；如果前面有人出队，如之奈何？那肯定要动front了，它加一即可。
能把这层理解透彻了之后，后面的问题就是1+1，老老实实耐心写一写就可以了。
OK，先写这个数组模拟的队列类的基本结构和构造方法吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class ArrayQueue{
private int maxSize;
private int[] arr;
private int front;
private int rear;
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
}
|
怎么样？这个很容易理解的吧。后续我们写这个队列类的入队、出队方法，但是我们要思考一下，有两个方法是我们现在必须得去实现的，因为后续的一些方法都会用到它们。没错，就是判断队列是否为空、是否满的方法，且看下面如何实现：
1
2
3
4
5
6
7
8
|
public boolean isEmpty(){
return rear==front;
}
public boolean isFull(){
return rear==maxSize-1;
}
|
这俩方法应该蛮好理解的吧，当然可能你会对 isFull 方法感到不太对，确实，这正是普通数组的局限性，因为它不是循环的，这样只要rear到最后移位的时候就没办法了，只能说它满了。我们先搁置这个问题，这个需要到下一节去解决。我们先玩简单的，不着急。接着写入队出队的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public void in(int val){
if(isFull()){
throw new RuntimeException("队列已满，入队失败");
}else {
arr[++rear] = val;
}
}
public int out(){
if(isEmpty()){
throw new RuntimeException("队列为空，出队失败");
}else {
return arr[++front];
}
}
|
这个也不难理解的，接着我们再写两个方法，显示队列元素和查看头元素，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public void show(){
if(isEmpty()){
System.out.println();
}else {
for (int i = (front+1); i <= rear; i++) {
System.out.printf("%d\t",arr[i]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("队列为空，查看失败");
}else {
return arr[front+1];
}
}
|
这样这个类就完成了，基本的思想应该就是这样，应该不难理解。接着我们再main方法中进行测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(6);
queue.in(1);
queue.in(2);
queue.in(3);
queue.in(4);
queue.in(5);
queue.show();
queue.out();
queue.out();
queue.show();
System.out.println(queue.head());
}
|
先把后续添加的两行注释掉，看看运行情况，如下：
现在我们把那两行恢复再测试，看看怎样，如下：
循环数组模拟队列
上面的问题到现在是到解决的时候了，关键就是rear还能不能继续前进，如果是循环的话，那么只要没空，rear即使到最后一位，它又循环回来，然后入队成功。对，核心思想就是这样，有的同学就可能会问那些方法怎么改呀？rear都比front小了，这咋整？好的，其实核心就是一个运算符，% ，就是这货，把它用灵活就行了。
但是，别忘了一个问题，假设你的front在0位置，rear在最后一位，这时按我们上面的推理，这时候队列还有一个位置，就是0位置。这确实，但是如果就在这时再往入队一个元素，那么你的rear就会往后循环到0位置。
这按道理没错，这样队列满了呗。我靠，你发没发现，这不就是我们队列为空的条件吗？这样到底队列为空还是满，分不清。得，我们又要提前约定个东西了，怎么约定才能解决这个问题？
将队列容量空出一个作为约定条件，这样就解决了这个问题了。上面那个情况就不会出现了，因为它已经满了，这样队列满的条件就是 (rear+1) % maxSize == front ，队列为空的条件还是老样子 rear == front 。
关键就是这一点，把这一点理解清楚了之后，后续的代码就很简单了。还是老样子，我直接上这个类的全部代码了，说多了也没啥意思了，我们自己最好先去实现一下，对，我们得增加一个方法，就是队列中有多少个元素 size() 方法，可能有的方法会使用到这个size。
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
| class CircleQueue{
private int maxSize;
private int[] arr;
private int front;
private int rear;
public CircleQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
front = -1;
rear = -1;
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
return (rear+1)%maxSize == front;
}
public int size(){
return (rear+maxSize-front)%maxSize;
}
public void in(int val){
if(isFull()){
throw new RuntimeException("队列已满，入队失败");
}else {
rear = (rear+1) % maxSize;
arr[rear] = val;
}
}
public int out(){
if(isEmpty()){
throw new RuntimeException("队列为空，出队失败");
}else {
front = (front+1)%maxSize;
return arr[front];
}
}
public void show(){
if(isEmpty()){
System.out.println();
}else {
for (int i = (front+1); i < (front+1+size()); i++) {
System.out.printf("%d\t",arr[i%maxSize]);
}
System.out.println();
}
}
public int head(){
if(isEmpty()){
throw new RuntimeException("队列为空，查看失败");
}else {
return arr[(front+1)%maxSize];
}
}
}
|
我们在main方法中进行测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void main(String[] args) {
CircleQueue queue = new CircleQueue(6);
queue.in(1);
queue.in(2);
queue.in(3);
queue.in(4);
queue.in(5);
queue.show();
queue.out();
queue.out();
queue.show();
queue.in(6);
queue.in(7);
queue.show();
}
|
输出结果如下：
