队列queue

无标签
数据结构与算法
发布日期:   2022-07-06
文章字数:   2k
阅读时长:   9 分

基本介绍

  • 队列是一个有序列表，可以用数组或链表来实现
  • 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

数组模拟队列

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

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

    改变，而rear则是随着数据输入而改变，如图所示:

image-20220706204103966

  • 思路分析

    • 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤:
      1. 将尾指针往后移: rear+1，当 front == rear 时，队列为空
      2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。
      3. 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
    127
    package com.ysy.queue;


    import java.util.Scanner;

    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){
                            //TODO: hadle exception
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h': //查看队列头的数据
                        try{
                            int res = queue.headQueue();
                            System.out.printf("队列头的数据是%d\n", res);
                        }catch (Exception e){
                            //TODO: hadle exception
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e': //退出
                          scanner.close();
                          loop = false;
                          break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    }


    //使用数组模拟队列-编写一个ArrayQueue类
    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;//指向队列头部，分析出front是指向队列头的前一个位置
            rear = -1;//指向队列尾部，指向队列尾的数据(即就是队列的最后一个数据)
        }

        //判读队列是否满
        public boolean inFull(){
            return rear == maxSize - 1;
        }
        //判断队列是否空
        public boolean isEmpty(){
            return rear == front;
        }

        //添加数据到队列
        public void addQueue(int n){
            //判断队列是否满
            if(inFull()){
                System.out.println("队列满，不能加入数据~");
                return;
            }
            rear++;//让rear后移
            arr[rear] = n;
        }

        //获取队列数据，出队列
        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()) {
                System.out.println("队列空，没有数据");
            }
            return arr[front + 1];
        }
    }

  • 问题分析并优化

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

数组模拟环形队列

  • 分析说明
    1. 尾索引的下一个为头索引时表示队列满，即将队列容量空出-一个作为约定，这个在做判断队列满的时候需要注意**(rear + 1) % maxSize== front [满]**
    2. rear == front [空]
    3. 队列的最大有效数据 = maxSize - 1
    4. 分析示意图如下

image-20220706215942904

  • 思路分析

    1. front 变量的含义做一个调整 : front 就指向队列的第一个元素，也就是说ar[front]就是队列的第一个元素。front的初始值= 0
    2. rear 变量的含义做一个调整: rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。rear的初始值=0
    3. 当队列满时，条件是(rear +1) % maxSize = front 【满】
    4. 对队列为空的条件，rear== front【空】
    5. 队列中有效的数据的个数**(rear + maxSize - front) % maxSize** // rear= 1 front=0
    6. 可以在原来的队列上修改得到一个环形队列

  • 代码实现

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
139
140
141
package com.ysy.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //测试
        //创建一个环形队列
        CircleArrayQueue queue = new CircleArrayQueue(4);
        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){
                        //TODO: hadle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try{
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    }catch (Exception e){
                        //TODO: hadle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class CircleArrayQueue{
    private int maxSize;//表示数组的最大容量
    //front 变量的含义做一个调整 : **front 就指向队列的第一个元素**，也就是说ar[front]就是队列的第一个元素。
    // front的初始值= 0
    private int front;//队列头
    //rear 变量的含义做一个调整: **rear 指向队列的最后一个元素的后一个位置**，因为希望空出一个空间做为约定。
    // rear的初始值=0
    private int rear;//队列尾
    private int[] arr;//用于存放数据，模拟队列

    //创建队列的构造器
    public CircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;//指向队列头部，分析出front是指向队列头的前一个位置
        rear = 0;//指向队列尾部，指向队列尾的数据(即就是队列的最后一个数据)
    }

    //判读队列是否满
    public boolean inFull(){
        return (rear + 1) % maxSize == front;
    }
    //判断队列是否空
    public boolean isEmpty(){
        return rear == front;
    }

    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if(inFull()){
            System.out.println("队列满，不能加入数据~");
            return;
        }
        //直接将数据加入
        arr[rear] = n;
        //rear后移，必须考虑取模
        rear = (rear + 1) % maxSize;
    }

    //获取队列数据，出队列
    public int getQueue(){
        //判断队列是否空
        if(isEmpty()){
            throw new RuntimeException("队列空，不能取数据");
        }
        //front是指向队列的第一个元素
        //先把front对应的值保存到一个临时变量
        //将front后移，考虑取模
        //将保存的临时变量返回
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //显示队列的所有数据
    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]);
        }
    }

    //显示队列的头数据，注意不是取数据
    public int headQueue(){
        //判断
        if(isEmpty()) {
            System.out.println("队列空，没有数据");
        }
        return arr[front];
    }

    //求出当前队列的有效数据的个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }
}
文章作者: Yang Shiyu
文章链接: https://yangshiyu52.github.io/2022/07/06/shu-ju-jie-gou-yu-suan-fa-dui-lie/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Yang Shiyu !
无标签
赏
  目录