数据结构之队列

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 7.6k

队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

队列只允许在后端（称为 rear ）进行插入操作，在前端（称为 front ）进行删除操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。从队头删除元素的操作叫做出队，从队尾追加元素的操作叫做入队。

队列可分为三种：顺序队列、循环队列、双端队列

顺序队列

顺序存储结构存储的队列称为顺序队列。和顺序表一样，用一个一维数组存。队头在数组的低下标端，队尾设在高下表端。队头，队尾指针值是数组元素的下标。队头指针始终指向队头结点的前一个结点位置，初始值为-1（理论上应该为0，但是Java中索引是从0开始的，索引为0代表队列中第一个元素，所以定为-1）。队尾指针是指向队尾结点位置，初始值也为-1。

队列中没有元素时，称为空队列，

  • 初始化条件：front=rear=-1

  • 队列空的条件：front=rear

  • 队列满的条件： rear = MAXSIZE

Java实现

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
public class OrderQueue {
	
	private Object[] data;
	private int front = -1;
	private int rear = -1;
	
	/**
	 * 队列的长度
	 */
	private int length;
	
	private static final int DEFAULT_LENGTH = 10;
	
	/**
	 * 默认长度的队列
	 * 创建一个新的实例OrderQueue.
	 */
	public OrderQueue() {
		if (length == 0) {
			length = DEFAULT_LENGTH;
		}
		data = new Object[length];
	}
	
	/**
	 * 指定队列的长度
	 * 创建一个新的实例OrderQueue.
	 * @param length
	 */
	public OrderQueue(int length) {
		this.length = length;
		data = new Object[length];
	}
	
	/**
	 * 入队
	 * @author qinghuazangshui 2018年7月27日 上午11:02:30
	 * @param obj
	 * @return
	 * @since v1.0
	 */
	public synchronized Object in(Object obj) {
		if (rear == length-1) {
			return null;
		}
		data[++rear] = obj;
		return obj;
	}
	
	/**
	 * 入列
	 * @author qinghuazangshui 2018年7月27日 上午11:11:15
	 * @param obj
	 * @return
	 * @since v1.0
	 */
	public synchronized boolean pull(Object obj) {
		if (rear == length-1) {
			throw new IndexOutOfBoundsException("队列已满");
		}
		data[++rear] = obj;
		return true;
	}
	
	/**
	 * 出队
	 * @author qinghuazangshui 2018年7月27日 上午11:18:57
	 * @return
	 * @since v1.0
	 */
	public synchronized Object out() {
		if(front == rear) {
			return null;
		}
		front++;
		Object obj = data[front];
		data[front] = null;
		return obj;
	}
	
	/**
	 * 出队
	 * @author qinghuazangshui 2018年7月27日 上午11:19:06
	 * @return
	 * @since v1.0
	 */
	public synchronized boolean push() {
		if(front == rear) {
			throw new IndexOutOfBoundsException("队列已空");
		}
		front++;
		data[front] = null;
		return true;
	}
	
	public void print() {
		System.out.println(Arrays.toString(data));
	}
}

测试

1
2
3
4
5
6
7
8
9
10
11
public class TestOrderQueue {
	
	public static void main(String[] args) {
		OrderQueue queue = new OrderQueue();
		for(int i=10; i<23; i++) {
			Object obj = queue.in(i);
			System.out.println(obj);
		}
		queue.print();
	}
}

循环向队列中添加元素，队列的默认长度是10，插入操作结束后打印当前队列的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
10
11
12
13
14
15
16
17
18
19
null
null
null
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

可以看到，当插入10个元素后开始返回null值，表示队列已满，插入失败；最终打印的结果也只有10个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TestOrderQueue {
	
	public static void main(String[] args) {
		OrderQueue queue = new OrderQueue();
		for(int i=10; i<23; i++) {
			Object obj = queue.in(i);
			//System.out.println(obj);
		}
		queue.print();
		
		System.out.println("-----------分割线------------");
		
		while(true) {
			Object obj = queue.out();
			if(obj == null) {
				break;
			}
			System.out.println(obj);
		}
		queue.print();
	}
}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
-----------分割线------------
10
11
12
13
14
15
16
17
18
19
[null, null, null, null, null, null, null, null, null, null]

每次出队都返回此次出队的元素，并将队头指针向后移动一位，同时将原有索引的位置置空

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 class TestOrderQueue {
	
	public static void main(String[] args) {
		OrderQueue queue = new OrderQueue();
		for(int i=10; i<23; i++) {
			Object obj = queue.in(i);
			//System.out.println(obj);
		}
		//queue.print();
		
		//System.out.println("-----------分割线------------");
		
		while(true) {
			Object obj = queue.out();
			if(obj == null) {
				break;
			}
			//System.out.println(obj);
		}
		//queue.print();
		
		Object obj = queue.in(10);
		System.out.println(obj);
	}
}

将所有元素出队后，再向队列中添加元素，返回null值，即添加失败；但是队列中明明10个位置都是空的，可用的。这就是顺序队列中的假溢出问题。

假溢出

队尾指针已经指向队尾，即rear = length-1；但是队列的前面部分仍有可用空间，但是此时已经不能再向队列中插入元素了，此种情况称为“假溢出”

解决假溢出的方法，可以在每次元素出队时，所有元素整体向前移动，让空的存储单元留在队尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public synchronized Object out2() {
	if(front == rear) {
		return null;
	}
	front++;
	Object obj = data[front];
	
	Object[] temp = new Object[length];
	for(int i=front+1; i<=rear; i++) {
		temp[i-1] = data[i];
	}
	for(int i=rear+1; i<length; i++) {
		temp[i] = null;
	}
	data = temp;
	front = -1;
	return obj;
}

测试

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
	OrderQueue queue = new OrderQueue();
	for(int i=10; i<23; i++) {
		Object obj = queue.in(i);
	}
	
	System.out.println(queue.out2());
	queue.print();
}

输出结果

1
2
10
[11, 12, 13, 14, 15, 16, 17, 18, 19, null]

可以看出，不再出现假溢出的问题

但是，这种处理方式涉及到大量的对象创建和数据移动，性能很低；还有一种较巧妙的解决方法，那就是循环队列

循环队列

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

循环队列应用范围广泛，比如Linux内核当中的环形缓冲区就是基于循环队列来设计的。

循环队列：采用环状顺序表来存放队列元素，有两个指针，其中 front 指针指向队列的队头元素，rear指针指向队尾元素的下一个位置，往队列中加进或取出元素时分别改变这两个变量的计数。当头尾指针（front / rear）指向队列尾的元素（下标：QueueSize-1）时，其加1操作的结果是指向向量的下界0。

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是”空”还是”满”。

解决这个问题的方法至少有三种：

  • 另设一布尔变量以区别队列的空和满；
  • 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
  • 使用一个计数器记录队列中元素的总数（即队列长度）。

此处我们采用第二种方式，少用一个元素的空间，根据尾指针在循环意义下加1后是否等于头指针判断队列是否满

定义

  • 初始化条件： front == rear == 0
  • 队列满条件： MOD(rear+1,m) == front
  • 队列空条件： front == rear
  • 队头指针推进计算: front = MOD(front+1,m)
  • 队尾指针推进计算: rear = MOD(rear+1,m)

Java实现

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

public class CycleQueue {
	
	private Object[] data;
	private int front = 0;
	private int rear = 0;
	
	private static final int DEFAULT_CAPACITY = 10;
	
	private int length;
	
	public CycleQueue() {
		this.data = new Object[DEFAULT_CAPACITY];
		length = data.length;
	}
	
	public boolean full() {
		if ((rear + 1) % length == front) {
			return true;
		}
		return false;
	}
	
	public boolean empty() {
		if (front == rear) {
			return true;
		}
		return false;
	}
	
	public synchronized Object in(Object obj) {
		if (full()) {
			return null;
		}
		data[rear] = obj;
		rear = (rear + 1) % length;
		return obj;
	}
	
	public synchronized Object out() {
		if (empty()) {
			return null;
		}
		Object obj = data[front];
		data[front] = null;
		front = (front + 1) % length;
		return obj;	
	}
	
	public void print() {
		System.out.println(Arrays.toString(data));
	}
}

测试1

1
2
3
4
5
6
7
8
9

public static void main(String[] args) {
	CycleQueue queue = new CycleQueue();
	for(int i=10; i<23; i++) {
		Object obj = queue.in(i);
		System.out.println(obj);
	}
	queue.print();
}

尝试向循环队列中插入元素，当插入9个元素后，判定队列已满（空闲一个元素位置，用于区分队列满和队列空），所以不再插入元素。

输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
10
11
12
13
14
15
16
17
18
null
null
null
null
[10, 11, 12, 13, 14, 15, 16, 17, 18, null]

测试2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
	CycleQueue queue = new CycleQueue();
	for(int i=10; i<23; i++) {
		Object obj = queue.in(i);
		//System.out.println(obj);
	}
	queue.print();

	
	System.out.println("-----------分割线------------");
	
	while(true) {
		Object obj = queue.out();
		if(obj == null) {
			break;
		}
		System.out.println(obj);
	}
	queue.print();
       System.out.println(queue.empty());
}

从循环队列中取元素，然后再打印查看效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
[10, 11, 12, 13, 14, 15, 16, 17, 18, null]
-----------分割线------------
10
11
12
13
14
15
16
17
18
[null, null, null, null, null, null, null, null, null, null]
true

可以看到，调用出队方法后，队列中元素置为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
public static void main(String[] args) {
	CycleQueue queue = new CycleQueue();
	for(int i=10; i<23; i++) {
		Object obj = queue.in(i);
		//System.out.println(obj);
	}
	queue.print();

	
	System.out.println("-----------分割线------------");
	
	while(true) {
		Object obj = queue.out();
		if(obj == null) {
			break;
		}
		//System.out.println(obj);
	}
	queue.print();
	
	System.out.println(queue.empty());

	queue.in(20);
	queue.in(21);
	queue.in(22);
	queue.in(23);
	queue.in(24);
	queue.in(25);
	queue.in(26);
	queue.in(27);
	queue.in(28);
	queue.in(29);
	queue.print();
	
	System.out.println(queue.full());
}

队列为空后，再向队列中插入元素，输出结果：

1
2
3
4
5
6
[10, 11, 12, 13, 14, 15, 16, 17, 18, null]
-----------分割线------------
[null, null, null, null, null, null, null, null, null, null]
true
[21, 22, 23, 24, 25, 26, 27, 28, null, 20]
true

可以看到空元素的位置发生了变化，元素29因为队列已满，并没有插入成功，调用full()方法返回true，队列已满。

链式队列

TODO

等整理完链表的实现再来完善