数组模拟环形队列实现

一、队列（Queue）

1）特点：先进先出，即：先存入队列的数据，要先取出，后存入的要后取出
2）是一个有序列表，可以用数组或是链表来实现
3）示意图（使用数组模拟队列示意图）

添加数据是在队列的尾部加，front值不变
取数据的时候是从队列的头部取，rear值不变，front值依次递减

二、使用数组模拟队列思路

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

2、向队列中添加数据的思路分析：
1）当front == rear，表示队列为空，将尾部指针往后移动一位，即rear+1
2）若尾指针rear小于队列的最大下标 maxSize - 1,则表示队列未满，则可以将数据存放到队列中，否则无法存入数据。rear == maxSize - 1[队列已满]

三、代码实现

/**
 * 使用数组模拟队列
 */
class ArrayQueue {
    /**
     * 数组最大容量
     */
    private int maxSize;
    /**
     * 数组头
     */
    private int front;
    /**
     * 数组尾
     */
    private int rear;
    /**
     * 存放数据的数组
     */
    private int[] arr;

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

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

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

    /**
     * 向队列添加数据
     */
    public void addQueue(int n) {
        // 首先判断队列是否已满
        if (isFull()) {
            System.out.println("队列已满，不能再添加数据~");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    /**
     * 获取队列的数据,出队列
     */
    public int getQueue() {
        // 首先判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空~");
        }
        // 出队列，是从队列的头开始
        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

问题分析并优化
1）缺点：目前这种队列的方式有一个弊端，队列使用一次就不能再使用了。
2）将这个数组使用算法，改进成一个环形队列，取模：%

四、数组模拟环形队列

4.1、思路：

4.2 代码实现

class CircleQueue {
    /**
     * 数组最大容量
     */
    private int maxSize;
    /**
     * 数组头: 指向队列的第一个元素，初始值为0
     */
    private int front;
    /**
     * 数组尾：指向队列的最后一个元素的后一个位置，默认值为0
     */
    private int rear;
    /**
     * 存放数据的数组
     */
    private int[] arr;

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

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

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

    /**
     * 向队列添加数据
     */
    public void addQueue(int n) {
        // 首先判断队列是否已满
        if (isFull()) {
            throw new RuntimeException("队列已满，不能存放数据！");
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 获取队列的数据，出队列
     *
     * @return
     */
    public int getQueue() {
        // 首先判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空，不能取出数据！");
        }
        /**
         * 取元素的逻辑：
         * 1、front是指向队列的第一个元素，先将第一个元素取出放到临时变量中保存
         * 2、front向后移动一位，front = (front + 1) % maxSize
         * 3、最后返回第一步的临时变量
         */
        int tmp = arr[front];
        front = (front + 1) % maxSize;
        return tmp;
    }

    /**
     * 显示队列的所有数据
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列为空，不能取出数据！");
            return;
        }
        /**
         * 遍历队列的思路：
         * 从front位置开始，遍历(rear+maxSize-front)%maxSize个元素
         */
        int length = (rear + maxSize - front) % maxSize;
        for (int i = front; i < length + front; i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }
    
}
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