简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：

（1） “下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

（2）”真上溢”现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

（3）”假上溢”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

数组模拟顺序队列

初始化

创建ArrayQueue类,包含队列最大容量maxSize，队列头front，队列尾rear，int型数组arr存放数据。通过构造器给定创建队列的最大容量。

image-20200824192609256

1
2
3
4
5
6
7
8
9
10
11
12
private int maxSize;//数组最大容量，即队列最大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//存放数据，模拟队列

//根据构造器创建指定大小的队列
public ArrayQueue(int maxSize) {
    this.maxSize = maxSize;
    arr = new int[maxSize];
    front = -1;//指向队列头的前一个位置
    rear = -1;//指向队列尾
}

注意这里的代码队列头front指向对是队列头的前一个位置，队列尾rear是始终指向队列尾位置！

image-20200824103246542

判断队列是否满

只要判断队列尾指针rear是否和队列的最大容量maxSize-1相等即可(数组长度-1) rear==maxSize-1实现方法isFull()

image-20200824104135933

1
2
3
4
//判断队列是否满
public boolean isFull() {
    return rear == maxSize - 1;
}

image-20200824104928992

判断队列是否为空

只要判断front指针和rear指针是否在同一个位置即可。front==rear实现方法isEmpty()

image-20200824104817653

1
2
3
4
//判断队列是否为空
public boolean isEmpty() {
    return front == rear;
}

image-20200824103246542

数据入队

首先通isFull()方法判断队列是否满了，当没满时向队列尾部添加数据。rear指针后移一位，在新的rear位置添加数据。rear++; arr[rear] = n实现addQueue()方法

image-20200824111656597

1
2
3
4
5
6
7
8
9
10
//添加数据到队列，入队列
public void addQueue(int n) {
    //判断队列是否满
    if (isFull()) {
        System.out.println("队列满，不能加入数据");
        return;
    }
    rear++;//rear+1，后移指针
    arr[rear] = n;
}

image-20200824112716083

数据出队

首先判断队列是否为空，如果为空则不能进行此操作。不为空，front++，返回当前front指针所指位置的数组值。front++;return arr[front];实现getQueue()方法

image-20200824114118595

1
2
3
4
5
6
7
8
9
//获取队列数据，出队列
public int getQueue() {
    //判断队列是否为空
    if (isEmpty()) {
        throw new RuntimeException("队列空，不能取数据!");
    }
    front++;//初始化定义时，front永远指向队列头的前一个位置，所以出队列获取值时，要后移++
    return arr[front];
}

image-20200824114035452

遍历显示队列

首先判断队列是否为空，如果为空则不能进行此操作。不为空，则从第一个队列头开始遍历front+1到队列尾部rear，打印数组值。实现showQueue()方法

![image-20200824114400131](/Users/kylin/Library/Application Support/typora-user-images/image-20200824114400131.png)

1
2
3
4
5
6
7
8
9
10
//显示队列的所有数据
public void showQueue() {
    if (isEmpty()) {
        System.out.println("当前队列为空！没有数据");
        return;
    }
    for (int i = front + 1; i <= rear; i++) {
        System.out.print(arr[i] + " ");
    }
}

image-20200824115202994

显示队列头

显示当前队列头数据，并不是取数据，单纯的显示。当队列不为空时才有队列头，return arr[front+1];实现headQueue()方法

image-20200824152709015

1
2
3
4
5
6
7
//显示队列的头数据,不是取数据
public int headQueue() {
    if (isEmpty()) {
        throw new RuntimeException("当前队列为空！没有数据");
    }
    return arr[front + 1];
}

image-20200824153442096

测试

初始化一个容量为3的队列，使用while循环，switch

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
public class ArrayQueueDemo {

    public static void main(String[] args) {
        //测试一把
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            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 = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~");
    }

}

依次添加1，2，3入队

image-20200824153917211

添加成功，遍历显示成功。依次出队

image-20200824154549286

出队顺序为1，2，3 出队正常。此时显示头数据，告诉没有数据。此时队列为空，再次入队数据，却告知队列已满！

image-20200824154615942

这里展示的就是顺序队列的缺点：当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

image-20200824155840175

通过上图演示为们可以看到当我们的一个满队列依次按照先进先出的顺序出队列后，我们的front指针位置已经移动到了和rear在同一个位置即队尾。而我们的队列为顺序队列front，rear指针只能向后移动，所以即便前面的已经不在队列中了，我们还是没有办法移动到此。这就是顺序队列的缺点。从而才有循环队列。

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己则从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=(rear+1)%MaxSize。

数组模拟循环队列

初始化

此时front指针始终指向队列头，而rear指针指向队列尾的后一个位置,maxSize-1才为队列最大容量。最后一个当队列满时rear指向该位置

image-20200824160913252

1
2
3
4
5
6
7
8
9
10
11
12
13
private int maxSize; // 表示数组的最大容量
//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
//front 的初始值 = 0
private int front;
//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
//rear 的初始值 = 0
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列

public CircleQueue(int arrMaxSize) {
    maxSize = arrMaxSize;
    arr = new int[maxSize];
}

image-20200824161413687

判断队列是否满

队列满的条件变为(rear + 1) % maxSize == front;

image-20200824162834209

1
2
3
4
// 判断队列是否满
public boolean isFull() {
    return (rear + 1) % maxSize == front;
}

image-20200824162720881

判断队列是否为空

队列是否为空的条件依旧为front==rear

image-20200824163149198

1
2
3
4
// 判断队列是否为空
public boolean isEmpty() {
    return rear == front;
}

image-20200824163235302

数据入队

首先判断当前队列是否已满，如果没有才能进行入队操作。rear后移不再是++，而是变成了rear = (rear + 1) % maxSize;

image-20200824164253347

1
2
3
4
5
6
7
8
9
10
11
12
// 添加数据到队列
public void addQueue(int n) {
    // 判断队列是否满
    if (isFull()) {
        System.out.println("队列满，不能加入数据~");
        return;
    }
    //直接将数据加入
    arr[rear] = n;
    //将 rear 后移, 这里必须考虑取模
    rear = (rear + 1) % maxSize;
}

image-20200824164659981

数据出队

首先判断队列是否为空，不为空则把front指针所指的数组值返回，front移动也不是顺序移动而是变成了front = (front+1) % maxSize

![image-20200824165029096](/Users/kylin/Library/Application Support/typora-user-images/image-20200824165029096.png)

image-20200824170154335

队列当前有效个数

此方法查看当前队列中存放了几个数据(rear + maxSize - front) % maxSize;

image-20200824171125480

1
2
3
4
// 求出当前队列有效数据的个数
public int size() {
    return (rear + maxSize - front) % maxSize;
}

image-20200824171507796

显示队列头

显示当前队列头数据，并不是取数据，单纯的显示。当队列不为空时才有队列头，return arr[front];

image-20200824171605770

1
2
3
4
5
6
7
8
// 显示队列的头数据， 注意不是取出数据
public int headQueue() {
    // 判断
    if (isEmpty()) {
        throw new RuntimeException("队列空的，没有数据~~");
    }
    return arr[front];
}

image-20200824171803940

遍历显示队列

变量i初始值为front，条件为i<front+size(),数组索引值为i%maxSize

image-20200824172220694

1
2
3
4
5
6
7
8
9
10
11
12
13
// 显示队列的所有数据
public void showQueue() {
    // 遍历
    if (isEmpty()) {
        System.out.println("队列空的，没有数据~~");
        return;
    }
    // 思路：从front开始遍历，遍历多少个元素
    // 动脑筋
    for (int i = front; i < front + size(); i++) {
        System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
    }
}

image-20200824172831819

测试

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
public static void main(String[] args) {

    //测试一把
    System.out.println("测试数组模拟环形队列的案例~~~");

    // 创建一个环形队列
    CircleQueue queue = new CircleQueue(4); //说明设置4, 其队列的有效数据最大是3
    char key = ' '; // 接收用户输入
    Scanner scanner = new Scanner(System.in);//
    boolean loop = true;
    // 输出一个菜单
    while (loop) {
        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 = scanner.next().charAt(0);// 接收一个字符
        switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'a':
                System.out.println("输出一个数");
                int value = scanner.nextInt();
                queue.addQueue(value);
                break;
            case 'g': // 取出数据
                try {
                    int res = queue.getQueue();
                    System.out.printf("取出的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h': // 查看队列头的数据
                try {
                    int res = queue.headQueue();
                    System.out.printf("队列头的数据是%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'e': // 退出
                scanner.close();
                loop = false;
                break;
            default:
                break;
        }
    }
    System.out.println("程序退出~~");
}

实例话队列 maxSize = 4 ，则队列最大容量为3。依次输入1，2，3入队

image-20200824173158257

入队成功。依次出队

image-20200824173253293

按照1，2，3先进先出的顺序依次出队。接着继续添加3，2，1数据入队

image-20200824173552201

添加成功，成功实现了循环队列！