1.队列Queue
定义
队列又叫做FIFO（先进先出）表，即first-in，first-out
现实中的队列
——排队
队列的接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public
interface
QueueInterface<T> {
/**
* 将新元素插入队列后端
* @param newEntry 待插入的对象 */
public
void
enqueue(T newEntry);
/**
* 删除并返回队列前端对象
* @return 位于队列前端的对象，如果队列为空则返回null */
public
T dequeue();
/**
* 检索队列前端对象
* @return 位于队列前端的对象，如果队列为空则返回null */
public
T getFront();
/**
* 检查队列是否为空
* @return 如果队列为空则返回true */
public
boolean
isEmpty();
/**
* 从队列中删除所有元素 */
public
void
clear();
}
|
Java类库：Queue接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public
interface
Queue<T> {
// 在对象的末端插入一个新元素，如果插入成功则返回true，否则抛出一个异常
public
boolean
add(T newEntry);
// 在对象的末端插入一个新元素，根据此操作成功与否返回true或false
public
boolean
offer(T newEntry);
// 在队列的前端检索并删除元素，如果在此操作之前队列已为空，则抛出异常NoSuchElementException
public
T remove();
// 在队列的前对检索并删除元素，如果在此操作之前队列已为空，则返回null
public
T poll();
// 检索队列前端的元素，如果队列为空，则抛出异常NoSuchelementException
public
T element();
// 检索队列前端的元素，如果队列为空，则返回null
public
T peek();
// 检索队列是否为空
public
boolean
isEmpty();
// 删除队列的所有元素
public
void
clear();
// 获得当前队列中的元素数据
public
int
size();
// 返回作用于队列的元素的迭代期器
public
Iterator<T> iterator();
}
|
双端队列接口描述
|
1
2
3
4
5
6
7
8
9
10
11
|
public
interface
DequeInterface<T> {
public
void
addToFront(T newEntry);
public
void
addToBack(T newEntry);
public
T removeFront();
public
T removeBack();
public
T getFront();
public
T getBack();
public
boolean
isEmpty();
public
void
clear();
}
|
优先队列的接口描述
|
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
|
public
interface
PriorityQueueInterface<T
extends
Comparable<?
super
T>> {
/**
* 将新元素插入优先队列
* @param newEntry newEntry一个对象 */
public
void
add(T newEntry);
/**
* 删除并返回优先队列最高的元素
* @return 优先级最高的对象，如果优先队列为空则返回null */
public
T remove();
/**
* 检索优先级最高的元素
* @return 优先级最高的对象，如果优先队列为空则返回null */
public
T peek();
/**
* 检索优先队列是否为空
* @return 如果优先队列为空则返回true */
public
boolean
isEmpty();
/**
* 缺德优先队列的长度
* @return 当前优先队列中的元素数据 */
public
int
getSize();
/**
* 从优先队列中删除所有元素 */
public
void
clear();
}
|
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
|
public
class
LinkedQueue<T>
implements
QueueInterface<T>, Serializable {
private
Node firstNode;
// 引用队列前端的结点
private
Node lastNode;
// 引用队列后端的结点
public
LinkedQueue() {
firstNode =
null
;
lastNode =
null
;
}
private
class
Node
implements
Serializable {
private
T data;
// entry in queue
private
Node next;
// link to next queue
}
// 在后端插入
public
void
enqueue(T newEntry) {
Node newNode =
new
Node(newEntry,
null
);
if
(isEmpty())
firstNode = newNode;
else
lastNode.setNext(newNode);
lastNode = newNode;
}
// 删除前端元素
public
T dequeue() {
T front =
null
;
if
(!isEmpty()) {
front = firstNode.getData();
firstNode = firstNode.getNext();
if
(firstNode ==
null
)
lastNode =
null
;
}
return
front;
}
// 检索前端元素
public
T getFront() {
T front =
null
;
if
(!isEmpty())
front = firstNode.getData();
return
front;
}
public
boolean
isEmpty() {
return
firstNode ==
null
;
}
public
void
clear() {
firstNode =
null
;
lastNode =
null
;
}
}
|
3.基于(循环)数组的队列实现
|
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
|
public
class
ArrayQueue<T>
implements
QueueInterface<T>, Serializable {
private
T[] queue;
// 存放队列元素的循环数组
private
int
frontIndex;
private
int
backIndex;
private
static
final
int
DEFAULT_INITIAL_CAPACITY =
50
;
public
ArrayQueue() {
this
(DEFAULT_INITIAL_CAPACITY);
}
public
ArrayQueue(
int
initialCapacity) {
queue = (T[])
new
Object[DEFAULT_INITIAL_CAPACITY +
1
];
frontIndex =
0
;
backIndex = initialCapacity;
}
// 在后端插入
public
void
enqueue(T newEntry) {
if
(isArrayFull()) {
// 扩建数组
}
backIndex = (backIndex +
1
) % queue.length;
// 由于数组是循环的，需要使用取余（%）操作符，以使backIndex达到其最大值之后变回0
queue[backIndex] = newEntry;
}
// 删除前端元素
public
T dequeue() {
T front =
null
;
if
(!isEmpty()) {
front = queue[frontIndex];
queue[frontIndex] =
null
;
frontIndex = (frontIndex +
1
) % queue.length;
}
return
front;
}
// 检索前端元素
public
T getFront() {
T front =
null
;
if
(!isEmpty())
front = queue[frontIndex];
return
front;
}
public
boolean
isEmpty() {
return
frontIndex == ((backIndex +
1
) % queue.length);
}
private
boolean
isArrayFull() {
return
frontIndex == ((backIndex +
2
) % queue.length);
}
}
|
4.基于双端链表的双端队列实现
|
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
|
public
class
LinkedDeque<T>
implements
DequeInterface<T>, Serializable {
private
DLNode firstNode;
// 引用双端队列的前端结点
private
DLNode lastNode;
// 引用双端队列的后端结点
public
LinkedDeque() {
firstNode =
null
;
lastNode =
null
;
}
private
class
DLNode
implements
Serializable {
private
T data;
private
DLNode next;
private
DLNode previous;
}
// 插入元素
public
void
addToBack(T newEntry) {
DLNode newNode =
new
DLNode(newEntry, lastNode,
null
);
if
(isEmpty())
firstNode = newNode;
else
lastNode.setNext(newNode);
lastNode = newNode;
}
public
void
addToFront(T newEntry) {
DLNode newNode =
new
DLNode(newEntry,
null
, firstNode);
if
(isEmpty())
lastNode = newNode;
else
firstNode.setPrevious(newNode);
firstNode = newNode;
}
// 删除元素
public
T removeFront() {
T front =
null
;
if
(!isEmpty()) {
front = firstNode.getData();
firstNode = firstNode.getNext();
if
(firstNode ==
null
)
lastNode =
null
;
else
firstNode.setPrevious(
null
);
}
return
front;
}
public
T removeBack() {
T back =
null
;
if
(!isEmpty()) {
back = lastNode.getData();
lastNode = lastNode.getPrevious();
if
(lastNode ==
null
)
firstNode =
null
;
else
lastNode.setNext(
null
);
}
return
back;
}
}
|
5.实现优先队列的方法
可以使用数组或链表实现优先队列。
但使用堆实现优先队列是一种更高效的方法。
本文转自 LinkedKeeper 51CTO博客，原文链接：http://blog.51cto.com/sauron/1226594，如需转载请自行联系原作者
