队列
什么是队列就不多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(); }
|
输出结果如下:
