数据结构与算法（八）--使用链表实现队列

一、前言

我们上一章通过链表实现了栈这样一个数据结构，此次我们实现另一个数据结构–队列。我们知道链表的增删查操作只对链表头进行操作才有O(1)的时间复杂度，如果我们对链表的尾部进行操作，它的复杂度都是O(n)级别了。但是对于队列这种数据结构来说，我们需要在一端插入数据，在另一端删除元素，所以我们势必会在这个线性结构的两端同时操作，此时对于链表来说有一端的时间复杂度就会达到O(n)级别。
其实这个问题我们当时在用数组的时候也遇到了，当时我们改进了数据实现队列的方式，从而产生了循环队列的这种实现方式。那么其实对于我们的链表也存在同样的问题，我们不能直接像栈一样使用之前我们实现的链表结构给我们的队列实现出来，所以我们需要改进我们的链表。

二、实现原理

其实改进并不困难，我们为什么说链表的头节点相关操作都是容易的呢，这是因为对于我们链表来说我们有一个head这个变量帮助我们标记链表的头节点在哪。那么现在我们希望对我们链表的尾部进行操作也很简便的话，我们其实也可以这样做，我们设立一个tail变量来标记我们链表的尾部在哪。
如下图，假设我现在添加了一个tail节点，那么我们现在在链表的尾部添加元素的话，其实就相当于在索引为size，换句话说这个tail位置的节点就是最后一个位置之前的一个节点。那么在tail节点添加元素就会变得非常简单，时间复杂度也是O(1).

那么如果我现在想删除tail节点上的元素，怎么做呢？
我们知道我们现在的链表是不对称的，所以当我们思考删除元素的时候会有些不同
我们之前写链表删除元素，我们说需要找到待删除元素的前一个位置的节点。那么如果我现在要删除tail这个节点的元素，我就需要找到tail节点之前的一个节点，可是我们如何去找呢，我们现在知道对于我们现在的链表每一个节点来说，它都有一个next，它指向该节点的后一个节点，所以我们目前是无法通过O(1)复杂度去找到tail的前一个节点的，我们仍然需要从head从头开始去遍历。也就是说即使我们在结尾标记了tail这个节点在哪里，我们还是无法使用O(1)复杂度去删除tail节点上的元素。但是相对来说我去删除haed节点上的元素是非常简单的。那么我们实现队列可以在tail端添加元素，在head端删除元素，即tail端作为队尾，head端作为队首这样其实也可以达到队列的两个操作均为O(1)的要求：
那么我们的改进其实就只有一个，就是添加一个tail变量标记我链表的尾节点在哪即可。

三、代码设计

我们暂时先不使用我们之前实现的链表，因为之前的链表并没有头结点，取而代之的是dummyHead,但是由于我们链表实现的队列只有两端的操作，dummyHead的作用几乎没有，所以暂不考虑，不过后文作者也会给出对应的实现方案，感兴趣的小伙伴也可以自行尝试
首先我们的新的类LinkedListQueue同样去实现之前的Queue队列类
然后我们的节点类和之前的是一致的：

private class Node {
		public T data;
		public Node next;

		public Node(T data, Node next) {
			this.data = data;
			this.next = next;
		}

		public Node(T data) {
			this(data, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {
			return data.toString();
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

然后我们的成员变量，非常的简单，就是之前说的head头结点，和tail尾结点，以及size

private Node head, tail;
	private int size;

public LinkedListQueue() {
	head = null;
	tail = null;
	size = 0;
}
1
2
3
4
5
6
7
8

然后是一些简单的方法的实现：

@Override
	public T getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("queue is empty");
		}
		return head.data;
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("Queue: front:");
		Node cur = head;
		while (cur != null){
			stringBuilder.append(cur + "->");
			cur = cur.next;
		}
		stringBuilder.append("NULL tail");
		return stringBuilder.toString();
	}
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

最后我们重点讲一下两个方法，分别是入队enqueue和出队dequeue

enqueue

①我们首先要考虑一开始当队列是空的时候，此时头结点head和尾结点都为NULL
此时要插入一个新元素，由于我们现在是以链表尾为队尾，所以我们能很简单的想到让tail = 新增加的节点即可，但这样还不够，我们的head此时还是null,如果添加一个元素后，是不是现在head和tail都是这个节点呢？所以我们还得维护下head,让head也等于这个节点，或者等于tail也是没问题的。

②当队列不为空的时候
此时很简单了，我们维护下tail的关系即可
首先让tail.next=新增加的节点
然后让tail = tail.next即可

最后维护下我们的size，入队方法就完成了，代码如下：

	@Override
	public void enqueue(T t) {
		if(tail == null){
			//说明是往空队列添加元素
			tail = new Node(t);
			head = tail;
		}else {
			tail.next = new Node(t);
			tail = tail.next;
		}
		size ++;
	}
1
2
3
4
5
6
7
8
9
10
11
12

dequeue

①首先和前面实现的队列一样，如果队列为空，我们应该报错不允许出队的操作
②我们之前说过，出队操作是在链表头模拟队首出队进行操作
那么我们先找到我们要删除的元素，其实就是head节点:Node prev = head
然后维护下我们的head节点：head = head.next，最后让prev.next变成NULL，从而让prev可以顺利被垃圾回收掉。
但是这样的操作还是不够的，试想一种情况，我们之前说过当队列只有一个元素的时候，此时head和tail都是这个节点。
那么你出队后，队列为空，head = head.next = null.但是tail并没有维护，仍然是prev那个节点，这样就是不对的。
所以我们要对这种情况做一个特殊处理，即处理完head后，对head是否为NULL进行判断，如果为空，说明出队前队列只有一个元素，那么需要对tail进行维护，让tail也为空！代码如下：

@Override
	public T dequeue() {
		if(isEmpty()){
			throw new IllegalArgumentException("can't dequeue from a empty queue");
		}
		Node prev = head;
		head = head.next;
		prev.next = null;
		if(head == null){
			//说明原队列只有一个元素，出队后队列为空，但是tail此时还指着
			tail = null;
		}
		size --;
		return prev.data;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

至此我们可以测试一下我们用链表实现的队列：

	public static void main(String[] args) {
		LinkedListQueue<Integer> integerLinkedListQueue = new LinkedListQueue<>();
		for (int i = 0; i < 10; i++) {
			integerLinkedListQueue.enqueue(i);
			System.out.println("第" + i + "次操作入队:" + integerLinkedListQueue);
			if (i % 3 == 2) {
				integerLinkedListQueue.dequeue();
				System.out.println("第" + i + "次操作出队:" + integerLinkedListQueue);
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11

测试结果如下：

那么如果我们使用的是虚拟头节点实现，其实也很简单，基本就是将之前的head替换为dummyHead.next,整体代码如下：

public class LinkedListQueue<T> implements Queue<T> {

	private class Node {
		public T data;
		public Node next;

		public Node(T data, Node next) {
			this.data = data;
			this.next = next;
		}

		public Node(T data) {
			this(data, null);
		}

		public Node() {
			this(null, null);
		}

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

	private Node dummyHead, tail;
	private int size;

	public LinkedListQueue() {
		dummyHead = new Node();
		tail = null;
		size = 0;
	}

	@Override
	public void enqueue(T t) {
		if(tail == null){
			//说明是往空队列添加元素
			tail = new Node(t);
			dummyHead.next = tail;
		}else {
			tail.next = new Node(t);
			tail = tail.next;
		}
		size ++;
	}

	@Override
	public T dequeue() {
		if(isEmpty()){
			throw new IllegalArgumentException("can't dequeue from a empty queue");
		}
		Node ret = dummyHead.next;
		dummyHead.next = ret.next;
		ret.next = null;
		if(dummyHead.next == null){
			//说明原队列只有一个元素，出队后队列为空，但是tail此时还指着
			tail = null;
		}
		size --;
		return ret.data;
	}

	@Override
	public T getFront() {
		if (isEmpty()) {
			throw new IllegalArgumentException("queue is empty");
		}
		return dummyHead.next.data;
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("Queue: front:");
		Node cur = dummyHead.next;
		while (cur != null){
			stringBuilder.append(cur + "->");
			cur = cur.next;
		}
		stringBuilder.append("NULL tail");
		return stringBuilder.toString();
	}

	public static void main(String[] args) {
		LinkedListQueue<Integer> integerLinkedListQueue = new LinkedListQueue<>();
		for (int i = 0; i < 10; i++) {
			integerLinkedListQueue.enqueue(i);
			System.out.println("第" + i + "次操作入队:" + integerLinkedListQueue);
			if (i % 3 == 2) {
				integerLinkedListQueue.dequeue();
				System.out.println("第" + i + "次操作出队:" + integerLinkedListQueue);
			}
		}
	}
}
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

四、和数组队列，循环队列的性能比较

我们继续使用之前学习循环队列的性能比较类，即以下方法：

private static double testQueue(Queue<Integer> q,int opCount){
		long startTime = System.currentTimeMillis();
		Random random = new Random();
		for (int i = 0; i < opCount; i++) {
			q.enqueue(random.nextInt(Integer.MAX_VALUE));
		}
		for (int i = 0; i < opCount; i++) {
			q.dequeue();
		}
		long endTime = System.currentTimeMillis();
		return (endTime - startTime)/1000.0;
	}
1
2
3
4
5
6
7
8
9
10
11
12

然后每种队列操作10w次对比三种队列的性能：

public static void main(String[] args) {
		ArrayQueue<Integer> integerArrayQueue = new ArrayQueue<>();
		LoopQueue<Integer> integerLoopQueue = new LoopQueue<>();
		LinkedListQueue<Integer> integerLinkedListQueue = new LinkedListQueue<>();
		System.out.println("arrayQueue,time:"+testQueue(integerArrayQueue,100000)+"s");
		System.out.println("loopQueue,time:"+testQueue(integerLoopQueue,100000)+"s");
		System.out.println("integerLinkedListQueue,time:"+testQueue(integerLinkedListQueue,100000)+"s");
	}
1
2
3
4
5
6
7
8

结果如下：

可以看到由于arrayQueue的出队操作是O(n)，而loopQueue和linkedListQueue的入队出队操作均为O(1),所以循环队列和链表队列性能差距不大，但是他们与数组队列差距非常大。