1. 思路分析

1）尾索引的下一个为头索引时表示队满，即：将队列容量空出一个作为约定，这个在做判断队列满的时候要注意 (rear + 1) % maxSize == front 【满】

2）rear == front 【空】

3）(rear + maxSize -front) % maxSize 【环形队列有效数据个数】

图示：

思路如下：

  1. front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素

front 的初始值 = 0

  1. rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.

rear 的初始值 = 0

  1. 当队列满时，条件是 (rear + 1) % maxSize == front 【满】

  2. 对队列为空的条件， rear == front 空

  3. 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0

  4. 我们就可以在原来的队列上修改得到，一个环形队列

2. 代码实现

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
142
143
144
145
146
147
package com.self.queue;

import java.util.Scanner;

public class ArraySimulateCircleQueue {

    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("程序退出~~");
    }
}

//使用数组模拟环形队列 -- 编写一个CircleQueue类
class CircleQueue{

    private int[] arr; //该数组用于存储数据，模拟队列
    private int maxSize; //表示数组的最大容量
    //front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素; front 的初始值 = 0
    private int front; //队列头
    //rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.; rear 的初始值 = 0
    private int rear; //队列尾

    //1.创建队列的构造器
    public CircleQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //front 和rear默认就是0，可以不写
        //front = 0;
        //rear = 0;
    }

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

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

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

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

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

    //7.求出当前队列有效数据的个数
    public int size(){
        //比如： rear = 1,front = 0,maxSize = 3
        return (rear + maxSize -front) % maxSize;
    }

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

3.代码的简单解析

  1. 创建队列的构造器：初始化队列，front 和 rear 指针初始值为 0；
1
public CircleQueue(int arrMaxSize){}
  1. 判断队列是否满:
1
public boolean isFull(){}
  1. 判断队列是否为空
1
public boolean isEmpty(){}
  1. 添加数据到队列,入队
1
public void addQueue(int n){}
  1. 获取队列的数据，出队列
1
public int getQueue(){}
  1. 显示队列的所有数据
1
public void showQueue(){}
  1. 求出当前队列有效数据的个数
1
public int size(){}
  1. 显示队列的头数据，注意并不是取出数据
1
public int headQueue(){}

数组实现环形队列解决了队列不能复用的问题。

运行过程这里不再叙述，请大家自己测试。