队列的应用场景

应用场景

银行排队，饭店点餐等等

队列介绍

  • 队列是一个有序列表，可以用数组或链表来实现；
  • 遵循先入先出的原则；(先进先出)

数组模拟队列的思路分析

数据模拟队列

  • 队列本身是有序列表，若使用数组的结构来存储队列数据，则队列数组的声明如下如，其中maxSize是该队列的最大容量；

    image-20220908112148564

  • 因为队列的输入、输出是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变；

思路分析

当我们将数据存入队列时称为addQueue，addQueue的处理需要两个步骤：

  1. 将尾指针往后移：rear+1,当front==rear (队列空)
  2. 托尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear==maxSize-1 (队列满)

数组模拟队列的代码实现

数组模拟队列代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package com.jokerdig.queue;

import java.util.Scanner;

/**
 * @author Joker大雄
 * @data 2022/9/8 - 12:27
 **/
// 数组模拟队列
public class Demo01 {
    public static void main(String[] args) {
        // 测试队列
        // 创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        // 输出菜单
        while(flag){
            System.out.println("=============队列验证==============");
            System.out.println("==========a: 添加队列============");
            System.out.println("==========g: 获取队列============");
            System.out.println("==========s: 查看队列============");
            System.out.println("==========h: 查看队列头的数据============");
            System.out.println("==========e: 退出程序============");
            System.out.print("请输入对应的字符：");
            key=scanner.next().charAt(0);
            switch (key){
                case 'a':
                    System.out.print("请输入一个数字：");
                    int val = scanner.nextInt();
                    arrayQueue.addQueue(val);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的数据：%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.printf("取出的头数据：%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序已退出");

    }
}
// 使用数组模拟队列，编写一个类
class ArrayQueue{
    private int maxSize; // 数组最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int arr[]; // 数组来模拟队列

    // 创建队列构造器,初始化数据
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头，实际上指向队列头的前一个位置
        rear = -1; // 指向队列尾部,实际指向队列尾部数据(包含尾部)
    }
    // 判断队列是否满
    public boolean isFull(){
        return rear == maxSize-1;
    }
    // 判断队列为空
    public boolean isEmpty(){
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int num){
        // 判断队列是否满
        if(isFull()){
            System.out.println("队列已满，无法添加");
            return;
        }
        rear++; // rear向后移
        arr[rear] =num;
    }
    // 获取(取出)队列数据
    public int getQueue(){
        if(isEmpty()){
            // 抛出异常,进程停止
            throw new RuntimeException("队列为空");
        }
        front++;// front 向后移
        return arr[front];
    }
    // 显示队列所有数据
    public void showQueue(){
        // 判断是否空
        if(isEmpty()){
            System.out.println("队列为空");
            return;
        }
        // 遍历
        for (int i=0;i<arr.length;i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }
    // 显示队列的头数据，不是取出数据
    public int headQueue(){
        // 判断是否空
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return arr[front+1];
    }
}

运行结果

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：g
队列为空
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：1
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
arr[1]=0
arr[2]=0
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：2
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
arr[1]=2
arr[2]=0
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：3
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
arr[1]=2
arr[2]=3
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：4
队列已满，无法添加
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：h
取出的头数据：1
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：g
取出的数据：1
=============队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：e
程序已退出

Process finished with exit code 0

存在的问题

队列使用使用一次后，就无法为队列添加值！

数组模拟环形队列的思路分析

对数组模拟队列的优化，充分利用数组因此将数组看作是一个环形。(通过取模的方式来实现)

  1. 尾部索引的下一个为头索引时表示队列满，将队列容量作为约定，在做判断队列是否满的时候要注意(rear+1)%maxSize == front (满)；
  2. rear == front (空)；
  3. 这中情况下front和rear初始值默认为0；(而不是-1)
  4. 队列中有效的的数据个数(rear+maxSize-front)%maxSize
  5. 环形队列分析图；

image-20220908140439707

数组模拟环形队列的实现

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package com.jokerdig.queue;

import java.util.Scanner;

/**
 * @author Joker大雄
 * @data 2022/9/8 - 14:06
 **/
// 数组模拟环形队列
public class Demo02 {
    public static void main(String[] args) {
        // 测试队列
        // 创建一个环形队列
        // 当前环形队列最大有效数据为(3-1=2),因为我们保留了一个空间
        ArrayQueue1 arrayQueue = new ArrayQueue1(3);
        char key; //接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        // 输出菜单
        while(flag){
            System.out.println("=============环形队列验证==============");
            System.out.println("==========a: 添加队列============");
            System.out.println("==========g: 获取队列============");
            System.out.println("==========s: 查看队列============");
            System.out.println("==========h: 查看队列头的数据============");
            System.out.println("==========e: 退出程序============");
            System.out.print("请输入对应的字符：");
            key=scanner.next().charAt(0);
            switch (key){
                case 'a':
                    System.out.print("请输入一个数字：");
                    int val = scanner.nextInt();
                    arrayQueue.addQueue(val);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的数据：%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.printf("取出的头数据：%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序已退出");

    }
}
// 使用数组模拟环形队列，编写一个类
class ArrayQueue1{
    private int maxSize; // 数组最大容量
    private int front; // 队列头 默认为0
    private int rear; // 队列尾 默认为0
    private int arr[]; // 数组来模拟队列

    // 创建队列构造器,初始化数据
    public ArrayQueue1(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    // 判断队列是否满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }
    // 判断队列为空
    public boolean isEmpty(){
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int num){
        // 判断队列是否满
        if(isFull()){
            System.out.println("队列已满，无法添加");
            return;
        }
        arr[rear] =num;
        rear = (rear+1) % maxSize; // 将rear后移
    }
    // 获取(取出)队列数据
    public int getQueue(){
        if(isEmpty()){
            // 抛出异常,进程停止
            throw new RuntimeException("队列为空");
        }
        // front是指向队列的第一个元素
        /*  1. 先把front保存到临时变量
            2. 把front后移
            3. 把临时保存的变量返回
         */
        int val = arr[front];
        front = (front+1)%maxSize;
        return val;
    }
    // 显示队列所有数据
    public void showQueue(){
        // 判断是否空
        if(isEmpty()){
            System.out.println("队列为空");
            return;
        }
        // 从front开始遍历，到(front+当前队列有效值)结束
        for (int i=front; i<front+size();i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

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


    // 显示队列的头数据，不是取出数据
    public int headQueue(){
        // 判断是否空
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }
}

运行结果

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：1
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：2
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
arr[1]=2
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：3
队列已满，无法添加
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[0]=1
arr[1]=2
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：g
取出的数据：1
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[1]=2
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：a
请输入一个数字：6
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：s
arr[1]=2
arr[2]=6
=============环形队列验证==============
==========a: 添加队列============
==========g: 获取队列============
==========s: 查看队列============
==========h: 查看队列头的数据============
==========e: 退出程序============
请输入对应的字符：e
程序已退出

Process finished with exit code 0