我们去银行办理业务时,经常会用到排号机,每去一个人取一个号码,银行柜台办理一个业务叫一个号,其中我们排队的过程就是用到了队列。(今天先使用数组来模拟队列,后面再使用链表来实现)
队列具有以下特点
- 队列是一个有序列表,可以用数组或是链表来实现。
- 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出
我们可以先把队列看成排队的行为,所谓的入队其实跟现实中排队是一样的操作,就是在队尾追加一个元素,可参考下图(tail代表队尾)
入队的操作很简单,但是出队呢?由于队列是遵循先进先出原则的,所以是从队头出队,也就是下标为0的位置,这也就意味着队列中多有的元素都要向前移动,以保证队列的队头,也就是下标为0的位置不为空。在现实中确实是这样排队的,可是在程序中,这样属实有点耗费性能。如下图所示
我们可以这样想,为什么出列时一定要全部移动呢,如果不去限制队列的元素必须存储在数组的前个单元这一条件,拿做做核酸举例。我们如果让核酸医生一步步向队伍移动,而不是队伍整体向核酸医生移动,在现实中这样做一定会被贴上脑子缺根筋的标签,但在程序中,出队的性能会大大增加,也就是说,队头不需要一定在下标为0的位置。如下图所示
为了避免当只有一个元素时,队头和队尾重合,因此引入两个变量,分别是head和tail,head代表队列头的前一个位置,tail代表队尾的位置(位置指的是下标),这样当head等于tail时,队列中不是还剩下一个元素而是空队列。 假设是长度为5的数组,初始状态,空队列如图所示。
head和tail均为-1, 然后入队 al a2 a3 a4, head依然为-1(因为是入队操作,只要队尾动就ok),而 tail 则变为3 ,出队a1 a2,head变为0, tail不变。如下图所示
出队a3 a4,head变为3,tail不变,head=tail时为空(每出队一次head向前移动一次),如下图所示
经过上面的分析,我们知道,想要构成一个队列需要以下几个变量:
- 队列的最大长度:MaxSize
- 队列头:head
- 队列尾:tail
- 用来存放数据的数组
其中,maxsize的值是固定,head会随着出队而变化,tail会随着入队而变化。
入队操作其实就是tail+1,出队操作就算head+1;当head=tail时,该队列为空队列,当tail=maxsize-1时,该队列为满队列,无法继续添加。
代码如下:
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试队列
//创建一个队列
ArrayQueue arrayQueue = new ArrayQueue(5);
char key = ' ';//接受用户输入
Scanner sc = new Scanner(System.in);
boolean flag = true;
while (flag) {
System.out.println("s(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
key = sc.next().charAt(0);
switch (key) {
case 's'://显示队列
arrayQueue.showQueue();
break;
case 'e'://退出程序
sc.close();
flag = false;
break;
case 'a'://添加数据到队列
System.out.println("请输入你要添加的一个数");
int num = sc.nextInt();
arrayQueue.addQueue(num);
break;
case 'g'://从队列取出数据
try {
int goQueue = arrayQueue.goQueue();
System.out.println("取出的数据是" + goQueue);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h'://查看队列头的数据
try {
int headData = arrayQueue.headData();
System.out.println("头数据是" + headData);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
class ArrayQueue {
private int maxsize;//队列最大长度
private int head;//队列头
private int tail;//队列尾
private int[] arr;//该数组用来存放数据 模拟队列
public ArrayQueue(int maxsize) {
this.maxsize = maxsize;
arr = new int[maxsize];
head = -1;//指向队列头的前一个位置
tail = -1;//指向队列尾的位置(不是后一位置)
}
//判断队列是否满
public boolean isFull() {
return tail == maxsize - 1;
}
//判断队列是否为空
public boolean isEmpty() {
return tail == head;
}
//添加数据到队列
public void addQueue(int data) {
//队列已满的话无法添加
if (isFull()) {
System.out.println("队列满了,无法继续添加数据");
return;
}
tail++;//让队列尾后移
arr[tail] = data;
}
//获取队列的数据 出队列
public int goQueue() {
//判断队列是否为空 如果为空无数据可以出
if (isEmpty()) {
throw new RuntimeException("队列中无数据,无法出队列");
}
head++;//让队列头后移
System.out.println(head);
return arr[head];
}
//显示队列的所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列为空,无数据");
}
for (int i = 0; i < arr.length; i++) {
System.out.println("arr["+i+"]="+arr[i]);
}
}
//显示队列的头数据 不用取出
public int headData() {
if (isEmpty()) {
throw new RuntimeException("队列为空,没有头数据");
}
return arr[head + 1];
}
}
其实,这样设计还存在很大的问题,假设这个队列的maxsize为5,入队a1 a2 a3 a4 a5后,出队a1 a2,如果继续入队的话,因为数组末尾元素已经被占用,会产生数组越界错误,可实际上,我 们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做假溢出,下一篇就来解决假溢出的问题。



