【尚硅谷】Java数据结构与算法笔记02 - 队列

---

一、使用场景

• 银行排队，先到先得
• 测核酸，先到先测
  

二、队列介绍

1. 队列是一个有序列表, 可以用数组或是链表来实现。
2. 遵循先入先出的原则。即: 先存入队列的数据, 要先取出。后存入的要后取出
3. 示意图: (使用数组模拟队列示意图)
   

三、数组模拟队列

3.1 思路分析

• 队列本身是有序列表, 若使用数组的结构来存储队列的数据, 则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理, 因此需要两个变量 front 及 rear 分别记录队列前后端的下标, front 会随着数据输出而改变, 而 rear则是随着数据输入而改变, 如图所示:

当我们将数据存入队列时称为” addQueue”, addQueue 的处理需要有两个步骤: 思路分析
1）将尾指针往后移: rear $+1$, 当 front $==$ rear 【空】
2）若尾指针 rear 小于队列的最大下标 maxSize-1, 则将数据存入 rear 所指的数组元素中, 否则无法存入数据。 rear $==\max$ Size $-1$ [队列满]

3.2 Java代码实现

public class ArrayQueue {
    public static void main(String[] args) {
        // 1. 声明数组模拟的队列，设置maxSize为4
        ArrayQueue arrayQueue = new ArrayQueue(4);
        // 2. 开始测试
        arrayQueue.add(1);
        arrayQueue.add(3);
        arrayQueue.add(4);
        arrayQueue.add(2);
        arrayQueue.add(5);
        System.out.println(arrayQueue.poll());
        System.out.println(arrayQueue.poll());
        System.out.println(arrayQueue.poll());
        System.out.println(arrayQueue.poll());
        System.out.println(arrayQueue.poll());
    }

    // 数组长度（队列的最大容量）
    int maxSize;
    // 当前队列长度
    int curSize;
    // 数组
    int[] arr;
    // 当前指向的元素
    int curIndex;

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        curIndex = 0;
        curSize = 0;
    }

    // 添加元素到队列
    public void add(int num) {
        if (curSize >= maxSize) {
            System.err.println("队列容量不足，无法添加元素");
        }else{
            arr[curSize++] = num;
        }
    }

    // 从队列取出头元素
    public int poll() {
        if (curIndex >= curSize) {
            throw new RuntimeException("当前队列为空，无法取出元素");
        }else if (curIndex >= maxSize) {
            throw new RuntimeException("超出队列长度");
        }else{
            return arr[curIndex++];
        }
    }

}
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

输出：

队列容量不足，无法添加元素
1
3
4
2
Exception in thread "main" java.lang.RuntimeException: 当前队列为空，无法取出元素
	at com.wskh.DataStructures.Queue.ArrayQueue.poll(ArrayQueue.java:57)
	at com.wskh.DataStructures.Queue.ArrayQueue.main(ArrayQueue.java:26)
1
2
3
4
5
6
7
8

3.3 问题分析与优化

1. 目前数组使用一次就不能用, 没有达到复用的效果
2. 将这个数组使用算法, 改进成一个环形的队列 取模：%

四、数组模拟环形队列

4.1 思路分析

对前面的数组模拟队列的优化, 充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明:

1. 尾索引的下一个为头索引时表示队列满, 即将队列容量空出一个作为约定, 这个在做判断队列满的 时候需要注意 $($ rear $+1)\%$ maxSize $=$ front 满]
2. rear $==$ front $[$ 空 $]$
3. 分析示意图:

4.2 Java代码实现

public class CircleArrayQueue {
    public static void main(String[] args) {
        // 1. 声明数组模拟的队列，设置maxSize为4
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
        // 2. 开始测试
        circleArrayQueue.add(1);
        circleArrayQueue.add(3);
        circleArrayQueue.add(4);
        System.out.println(circleArrayQueue.poll());
        System.out.println(circleArrayQueue.poll());
        circleArrayQueue.add(2);
        circleArrayQueue.add(5);
        System.out.println(circleArrayQueue.poll());
        System.out.println(circleArrayQueue.poll());
        System.out.println(circleArrayQueue.poll());
    }

    // 数组长度（队列的最大容量）
    int maxSize;
    // 当前队列长度
    int curSize;
    // 当前追加的指针
    int addIndex;
    // 数组
    Integer[] arr;
    // 当前指向的元素
    int curIndex;

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new Integer[maxSize];
        curIndex = 0;
        curSize = 0;
        addIndex = 0;
    }

    // 添加元素到队列
    public void add(int num) {
        if (curSize >= maxSize) {
            System.err.println("队列容量不足，无法添加元素");
        } else {
            arr[(addIndex++) % maxSize] = num;
        }
    }

    // 从队列取出头元素
    public int poll() {
        if (arr[curIndex % maxSize] == null) {
            throw new RuntimeException("当前队列为空，无法取出元素");
        } else {
            curSize--;
            Integer integer = arr[curIndex % maxSize];
            arr[curIndex % maxSize] = null;
            curIndex++;
            return integer;
        }
    }

}
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

输出：

1
3
4
2
5
1
2
3
4
5