记录生活中的点点滴滴

0%

队列

队列

什么是队列就不多bb了,反正就是先进先出的一种东东。它可以用链表或者数组实现,这一节讲的是用数组实现。

反正核心就是用数组去模拟队列,这个类中有四个成员属性:最大容量、数组、头部(我们约定不含有它)、尾部(我们约定含有它)。

为什么不含有头部,含有尾部?TMD,这只是个约定,你也可以反过来,不过这其实都是小问题,我们没必要去计较它们,主要你要有自己的约定,然后后续慢慢的去实现它。

下面我们先玩普通的数组去模拟队列,等我们把它实现之后,我们就发现它有个缺点,然后我们对它进行一点改进,改成用循环的数组去模拟队列就可以解决它的这一缺点了。OK,继续探索队列吧。

数组模拟队列

数组模拟队列的思想是什么?且看下图:

初始化一个大小为maxSize的数组,令其 rearfront 都为-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());
// queue.in(6);
// queue.in(7);
}

先把后续添加的两行注释掉,看看运行情况,如下:

现在我们把那两行恢复再测试,看看怎样,如下:

循环数组模拟队列

上面的问题到现在是到解决的时候了,关键就是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);//5个就会满了
// queue.in(8);
queue.show();
}

输出结果如下: