Java数据结构之队列

什么是队列

  • 队列是一种受限的线性表,其限制是仅允许在队的一端进行插入,而在队的另一端进行删除.
  • 在队列中把插入数据元素的一端称为队尾(rear).
  • 删除数据元素的一端称为队首(front).
  • 向队尾插入元素称为进队或入队.新元素入队后成为新的队尾元素.
  • 从队列中删除元素称为离队或出队.元素出队后,其后续元素成为新的队首元素
  • 因此在队列中,先入队的元素,肯定是先出队.所以称队列为先进先出表(FIFO).

队列结构与日常生活中排队等候服务的模型是一致的,最早进入队列的人,最早得到服务从队首离开;最后到来的人只能排在队列的最后,最后得到服务并最后离开.

队列的常用方法

队列结构一般都满足以下几个方法:

方法 功能描述
getSize() 返回队列的大小,即队列中元素的个数
isEmpty() 判断队列是为空
enqueue(e) 将元素e入队
dequeue 删除队尾元素
peek() 获取队首元素,但不出队

接口代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Created by HuShiwei on 2016/10/18 0018.
* FIFO先进先出
*/
public interface Queue {
public int getSize();//返回队列的大小
public boolean isEmpty();//判断队列是否为空
public void enqueue(Object e);//数据元素e入队
public Object dequeue();//队首元素出队
public Object peek();//取队首元素
}

队列的线性表实现

实现分析

队列的线性表实现:底层是用的数组存储队列元素.

queueArray

  • 如何判断队列是否满队列还是空队列
    • 设计了一个循环数组
    • 设计一个队首指针front,和一个队尾指针rear
    • front指向队列的首元素,rear指向队尾的最后一个元素+1的位置
  • 如何判断队列是空队列还是满队列?
    • 当是空队列的时候,front=rear,两个指针都指向同一个位置
    • 当是满队列的时候,因为是循环数组,所以front=rear.这样我们就没办法区分是空队列还是满队列了.
  • 如何解决这个问题呢?
    • 把数组的最后一个位置空出来,浪费最后的存储空间.
    • 这样,判断是满队列的时候,就可以根据(rear+1)%capacity=front
  • 注意点
    • 队尾指针rear指向队尾元素+1的位置.这样在队尾入队的时候就可以指针赋值了

代码实现

注意: 在实现队列的时候,一定要记住

  • 队列的结构特性,FIFO
  • 如何通过指针来操作
  • 理解了这些,自己就可以很轻松的实现队列了
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
/**
* 队列的顺序存储实现
*/
public class QueueArray implements Queue {
private static final int CAP = 7;//队列默认大小
private Object[] elements;//数据元素数组
private int capacity;//数组的大小
private int front;//队首指针
private int rear;//队尾指针
public QueueArray() {
this(CAP);
}
// 初始化队列
public QueueArray(int cap){
capacity = cap + 1;
elements = new Object[capacity];
front = rear = 0;
}
// 返回队列的大小
@Override
public int getSize() {
return (rear-front+capacity)%capacity;
}
// 判断队列是否为空
@Override
public boolean isEmpty() {
return front==rear;
}
// 数据元素e入队
@Override
public void enqueue(Object e) {
if (getSize()==capacity-1) {
expandSpace();
}
elements[rear] = e;
rear = (rear + 1) % capacity;
}
// 扩充队列大小
private void expandSpace() {
Object[] objects = new Object[elements.length * 2];
int i=front;
int j = 0;
while (i != rear) {
objects[j++] = elements[i];
i = (i + 1) % capacity;
}
elements = objects;
capacity = elements.length;
// 设置新的队首队尾指针
front = 0;
rear = j;
}
// 队首元素出队
@Override
public Object dequeue() {
if (isEmpty()) {
try {
throw new Exception("错误: 队列空了...");
} catch (Exception e) {
e.printStackTrace();
}
}
Object element = elements[front];
elements[front] = null;
front = (front + 1) % capacity;
return element;
}
// 取队首元素
@Override
public Object peek() {
if (isEmpty()) {
try {
throw new Exception("错误: 队列空了...");
} catch (Exception e) {
e.printStackTrace();
}
}
return elements[front];
}
}

队列的链式存储实现

未完待续….

Donate comment here