【数据结构与算法】环形队列的介绍、用数组实现环形数组

1. 环形队列的基本介绍

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

而环形队列，通过取模的方式，将数组看做是一个环形的

2. 使用数组实现环形队列

环形队列的变量说明：

• 环形队列有一个最大容量maxSize
• 队列的输出由head下标来控制，head会随着数据的输出而改变
• 队列的输入由tail下标来控制，tail会随着数据的输入而改变
• 队列是否满了，或队列是否为空，由变量flag控制
• 用一个数组来储存队列的数据

环形队列的方法说明：

• add2ArrayQueue：将数据添加到队列。如果队列未满，则可以添加数据。如果添加完数据后，队列满了则修改flag变量
• takeFromArrayQueue：从队列获取数据。如果队列不为空，则从队列获取数据。如果获取完数据后，队列为空则修改flag变量
• showArrayQueue：显示队列的所有数据，但不取出
• showHead：显示队列的头数据，但不取出

环形队列的实现：

import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {

        // 创建一个环形队列
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
        // 用于接收用户输入
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;

        // 输出一个菜单
        System.out.println("a(add): 添加数据到队列");
        System.out.println("t(take): 从队列取出数据");
        System.out.println("s(show): 显示队列所有数据");
        System.out.println("h(head): 查看队列头部数据");
        System.out.println("e(exit): 退出程序");
        while (loop) {

            // 接收一个字符
            key = scanner.next().charAt(0);
            switch (key) {
                case 'a':
                    System.out.println("请输出一个数：");
                    int inputData = scanner.nextInt();
                    circleArrayQueue.add2ArrayQueue(inputData);
                    break;
                case 't':
                    try {
                        int resultData = circleArrayQueue.takeFromArrayQueue();
                        System.out.printf("取出的数据是%d\n", resultData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    circleArrayQueue.showArrayQueue();
                    break;
                case 'h':
                    circleArrayQueue.showHead();
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");

    }
}


class CircleArrayQueue {
    // 数组的最大容量
    private int maxSize;
    // head指向队列的头部(获取下一个数据的index)
    private int head;
    // tail指向队列的尾部(添加下一个数据的index)
    private int tail;
    // flag = 0表示空，flag = 1表示满
    private int flag;
    // 用数组来实现环形队列
    private int[] arrayQueue;

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        // 初始化head和tail都指向0
        this.head = 0;
        this.tail = 0;
        this.flag = 0;
        this.arrayQueue = new int[this.maxSize];
    }

    // 判断队列是否空
    public boolean isEmpty() {
        // 如果head等于tail，且falg等于0，则表示空了
        return this.head == this.tail && flag == 0;
    }

    // 判断队列是否满
    public boolean isFull() {
        // 如果head等于tail，且flag等于1，则表示满了
        return this.head == this.tail && flag == 1;
    }


    // 添加数据到数组队列
    public void add2ArrayQueue(int data) {
        if (isFull()) {
            System.out.println("队列满了, 不能添加数据了");
            return;
        }
        this.arrayQueue[this.tail] = data;
        // 取模是为了跳转到数组的头部
        this.tail = (this.tail + 1) % this.maxSize;
        // 如果下一个要添加数据的index，和下一个要获取数据的index(还未获取)相等，则表示队列满了
        if (this.tail == this.head) {
            this.flag = 1;
        }

    }

    // 从队列获取数据
    public int takeFromArrayQueue() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列是空的，不能获取数据");
        }

        int data = this.arrayQueue[this.head];
        // 取模是为了跳转到数组的头部
        this.head = (this.head + 1) % maxSize;
        // 如果下一个要获取数据的index，和下一个要添加数据的index(还未添加)相等，则表示队列为空
        if (this.head == this.tail) {
            this.flag = 0;
        }
        return data;
    }

    // 计算当前队列有效数据的个数
    public int size() {
        if (isEmpty()) {
            return 0;
        } else if (isFull()) {
            return this.maxSize;
            // 如果tail在head后，则有效数据个数等于tail - head
        } else if (this.tail > this.head) {
            return this.tail - this.head;
            // 如果tail在head前，则有效数据等于maxSize - head + tail
        } else {
            return this.maxSize - this.head + this.tail;
        }
    }

    // 显示队列的所有数据(并不是取出)
    public void showArrayQueue() {
        if (isEmpty()) {
            System.out.println("队列空的，不能显示数据");
            return;
        }

        // 从head开始遍历，遍历有效数据的个数
        for (int i = this.head; i < this.head + this.size(); i++) {
            System.out.printf("arrayQueue[%d]=%d\n", i % this.maxSize, this.arrayQueue[i % this.maxSize]);
        }
    }


    // 显示队列的head的数据(并不是取出)
    public void showHead() {
        if (isEmpty()) {
            System.out.println("队列空的，不能显示数据");
            return;
        }
        System.out.println(this.arrayQueue[this.head]);
    }
}
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161

运行程序，结果如下：

a(add): 添加数据到队列
t(take): 从队列取出数据
s(show): 显示队列所有数据
h(head): 查看队列头部数据
e(exit): 退出程序
a
请输出一个数：
10
a
请输出一个数：
11
t
取出的数据是10
s
arrayQueue[1]=11
h
11
e
程序退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19