java数据结构-队列(Queue)

队列(Queue)?

队列是一个先进先出(FIFO)的数据结构。只允许在表的两端进行删除和新增操作并把删除称为出队新增称为入队,没有元素称为空队,出队的一端称为队头,入队的一段称为队尾。而俩端分别由frontrear俩个指针指向。

队列结构图


队列的实现

接口定义

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 top.weishilei.structure.queue;

/**
* 队列接口定义
* @author weishilei
*/
public interface IMyQueue<T> {
/**
* 返回队列长度
* @return
*/
int size();

/**
* 队列是否为空
* @return
*/
boolean isEmpty();

/**
* 入队新增元素,队列已满抛出异常
* @return
*/
boolean add(T data);

/**
* 入队新增元素,超出队列界限返回false
* @return
*/
boolean offer(T data);

/**
* 返回队头元素,队列为空则抛出异常
* @return
*/
T element();

/**
* 返回队头元素,队列为空则返回null
* @return
*/
T peek();

/**
* 出队删除元素,队列如为空抛出异常
* @return
*/
T remove();

/**
* 出队删除元素,队列为空则返回null
* @return
*/
T poll();

/**
* 清空队列
*/
void clear();
}

队列对于入队,出队,返回队头元素都提供俩种方式,一种是失败返回特殊值,另一种抛出异常。

返回null或false 抛出异常
入队 offer() add()
出队 poll() remove()
返回队头元素 peek() element()

顺序队列的问题

顺序队列假溢出

入图所示,数组末尾元素已被占用,再入队新增元素会造成越界的情况,但实际还有俩个空闲空间未被使用!这种现象称之为“假溢出”。解决这种问题的办法就是后面元素满了,再从头再新增元素,头尾相接的循环,称之为“顺序循环队列”这样我们就可以重复利用空闲空间了。

顺序循环队列

顺序循环队列计算front和rear俩个指针的值都有一套对应的公式获得:

1
2
3
//size为队列的长度
front = (front + 1) % size;
rear = (rear + 1) % size;

顺序循环队列

  1. front指向队头下标,rear指向下次入队下标。
  2. 当front与rear相等则为空队。
  3. 当条件为front = (rear + 1) % size则队列已满,但此时还有一个空闲空间,是为了避免front等于rear为空队的条件,size为队列长度。

顺序循环队列实现代码

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
package top.weishilei.structure.queue;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
* 实现顺序循环队列
* @author weishilei
* @param <T>
*/
public class LoopQueue<T> implements IMyQueue {
private Object[] data;
private int size;
private int front;
private int rear;
private static final int DEFAULT_SIZE = 10;

public LoopQueue() {
data = new Object[DEFAULT_SIZE];
front = 0;
rear = 0;
}

public LoopQueue(int capacity) {
data = new Object[capacity];
front = 0;
rear = 0;
}

/**
* 返回队列长度
*
* @return
*/
@Override
public int size() {
return size;
}

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

/**
* 入队新增元素,队列已满抛出异常
*
* @param data
* @return
*/
@Override
public boolean add(Object data) {
if (data == null) {
throw new NullPointerException();
} else if (front == (rear + 1) % this.data.length) {
throw new NoSuchElementException();
}

this.data[rear] = data;
rear = (rear + 1) % this.data.length;
size++;

return true;
}

/**
* 入队新增元素,超出队列界限返回false
*
* @param data
* @return
*/
@Override
public boolean offer(Object data) {
if (data == null) {
throw new NullPointerException();
} else if (front == (rear + 1) % this.data.length) {
this.ensureCapacity((this.data.length << 1) + 1);
}

this.data[rear] = data;
rear = (rear + 1) % this.data.length;
size++;

return true;
}

/**
* 返回队头元素,队列为空则抛出异常
*
* @return
*/
@Override
public Object element() {
if (isEmpty()) {
throw new NoSuchElementException();
}

return peek();
}

/**
* 返回队头元素,队列为空则返回null
*
* @return
*/
@Override
public Object peek() {
return data[front];
}

/**
* 出队删除元素,队列如为空抛出异常
*
* @return
*/
@Override
public Object remove() {
if (isEmpty()) {
throw new NoSuchElementException();
}

return poll();
}

/**
* 出队删除元素,队列为空则返回null
*
* @return
*/
@Override
public Object poll() {
if (isEmpty()) {
return null;
}

Object deleteData = data[front];
data[front] = null;
front = (front + 1) % size;
size--;

return deleteData;
}

/**
* 清空队列
*/
@Override
public void clear() {
front = rear = size = 0;
Arrays.fill(data, null);
}

/**
* 扩容
* @param capacity
*/
private void ensureCapacity(int capacity) {
if (capacity < size) {
return;
}

Object[] newData = new Object[capacity];
int j = 0;
for (int i = front; i != rear; i = (i + 1) % data.length) {
newData[j++] = data[i];
}

data = newData;
front = 0;
rear = j;
}

@Override
public String toString() {
return Arrays.toString(data);
}

}

总结

坚持分享,您的支持将鼓励我继续努力!