环形数组队列
队列的特性是先入先出，也就是在尾部插入数据，在头部删除数据，本文介绍用环形数组实现的队列，如下图所示：
队列的方法主要是增删查，如下接口定义
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
|
package com.eh.ftd.dsa.ds;
/**
* 自定义队列
*
* @author David Li
* @create 2020/06/16 09:50
*/
public interface Queue<T> {
/**
* 入队
*
* @param t
* @return
*/
boolean offer(T t);
/**
* 出队
*
* @return
*/
T poll();
/**
* 返回队首元素
*
* @return
*/
T peek();
/**
* 元素个数
*
* @return
*/
int size();
/**
* 是否为空
*
* @return
*/
boolean isEmpty();
/**
* 是否为满
*
* @return
*/
boolean isFull();
/**
* 展示所有元素
*/
void display();
}
|
处理思路
- 当队列为空时，head=0;rear==0;
- 数组的最后一个元素不存储数据，这样当head==rear表示队列为空，(rear+1)%n==head 表示队列为满
why?：队列中元素的个数是0，1，2，… ，n 共n+1种可能性，但是使用|rear-head|表示是0，1，2，…，n-1 共n种结果，所以必然有两种可能性|rear-head|的结果是一样。我们也可以找出来：
如上图2所示这个队列已满，当一直取元素直至head指向第2个元素，此时rear==head, 按照|rear-head|==0那么表示这个队列为空，但此时队列不为空。所以我们使用一个空的数据位来实现循环队列，也就是数组的最后一个元素不保存数据。
代码实现
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
|
package com.eh.ftd.dsa.ds.impl;
import com.eh.ftd.dsa.ds.Queue;
import java.util.Scanner;
/**
* 环形队列
*
* @author David Li
* @create 2020/06/11 18:26
*/
public class CircleQueue<T> implements Queue<T> {
/**
* 容量
*/
private int capacity;
/**
* 队首
*/
private int head;
/**
* 队尾
*/
private int rear;
private Object[] arr;
public CircleQueue(int capacity) {
// 这里因为要空出一个元素，所以需在用户输入元素个数基础上+1
this.capacity = capacity + 1;
arr = new Object[capacity + 1];
}
@Override
public boolean offer(T t) {
if (isFull()) {
System.out.println("队列已满");
return false;
}
// 直接将数据加入
arr[rear] = t;
// 尾指针后移一位,注意取模
rear = (rear + 1) % capacity;
return true;
}
@Override
public T poll() {
if (isEmpty()) {
return null;
}
// 取出元素
T t = (T) arr[head];
// front指针后移,注意取模
head = (head + 1) % capacity;
return t;
}
@Override
public T peek() {
return (T) arr[head];
}
@Override
public int size() {
return (rear - head + capacity) % capacity;
}
@Override
public boolean isEmpty() {
return head == rear;
}
@Override
public boolean isFull() {
return (rear + 1) % capacity == head;
}
@Override
public void display() {
System.out.print("队列: ");
for (int i = head; i < head + size(); i++) {
i = i % capacity; // i有可能超出，所以要取模
System.out.printf("arr[" + i + "]=" + arr[i] + ";\t");
}
System.out.println();
}
public static void main(String[] args) {
// 创建一个队列
Queue<Integer> queue = new CircleQueue<>(5);
Scanner scanner = new Scanner(System.in);
// 定义一个字符用来接收控制台输入
char c;
// 是否退出程序
boolean loop = true;
while (loop) {
System.out.printf("s:展示队列\ta:入队\td:出队\tp:查看队首元素\te:退出程序\n");
c = scanner.next().charAt(0);
switch (c) {
case 's':
queue.display();
break;
case 'a':
System.out.print("输入一个数:");
int num = scanner.nextInt();
queue.offer(num);
System.out.println();
break;
case 'd':
System.out.println("已出队: " + queue.poll());
break;
case 'p':
System.out.println("队首元素: " + queue.peek());
break;
case 'e':
loop = false;
break;
}
}
}
}
|
运行结果:
如上图2所示这个队列已满，当一直取元素直至head指向第2个元素，此时rear==head, 按照|rear-head|==0那么表示这个队列为空，但此时队列不为空。所以我们使用一个空的数据位来实现循环队列，也就是数组的最后一个元素不保存数据。