和栈类似，队列 (Queue) 也是一种线性表，只不过它的操作方式与栈不同。队列在尾部插入元素，在头部删除元素。
队列的基本操作称为入队 (Enqueue) 和出队 (Dequeue)。 它在表的末端 (称为队尾 rear) 进行插入操作，而在表的前端 (称为队头 front) 进行删除操作。
队列是先进先出的，与栈不同，由于这个特性，队列又被称作先进先出表 (First In First Out, FIFO)。
和栈类似，队列使用链表和数组实现都是合法的，链表实现队列是很显然的，只要各维护好队头和队尾指针即可。无论是入队还是出队，时间复杂度都是 O(1)。
队列的数组实现稍微麻烦，但也不复杂，以下内容讨论的都是数组实现的队列。
队列的数组实现
队列的数组实现严格来说需要维护两个指针，分别指向队头和队尾。队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。这样，队列的大小就是队尾指针减去队头指针。
但是由于 Go Slice 的特性，我们可以不用维护队头指针，只需要维护队尾指针即可。
这是最简单的队列实现，很容易写出代码:
1type Queue struct {
2 data []interface{}
3 tail int
4}
5
6func NewQueue() *Queue {
7 return &Queue{
8 data: make([]interface{}, 0),
9 tail: 0,
10 }
11}
12
13func (q *Queue) Enqueue(v interface{}) {
14 q.data = append(q.data, v)
15 q.tail++
16 return
17}
18
19func (q *Queue) Dequeue() (interface{}, error) {
20 if q.tail == 0 {
21 return errors.New("queue is empty")
22 }
23 v := q.data[0]
24 q.data = q.data[1:]
25 return v, nil
26}
但是对于像 C 那种没那么灵活的语言显然这样是不行的，Go Slice 简化了很多东西，这样实现队列就没有任何难点了，所以还是给出 C 的实现。
队列的数组实现（C）
C 语言中，数组是固定大小的，没有办法像 Go Slice 那样灵活，因此需要更原教旨一点的实现方式。
1typedef struct {
2 int *data;
3 int head;
4 int tail;
5 int size;
6} Queue;
7
8Queue* queueCreate(int maxSize) {
9 Queue *q = (Queue *)malloc(sizeof(Queue));
10 q->data = (int *)malloc(sizeof(int) * maxSize);
11 q->head = 0;
12 q->tail = 0;
13 q->size = maxSize;
14 return q;
15}
16
17bool queueEnQueue(Queue* obj, int value) {
18 if (queueIsFull(obj)) {
19 return false;
20 }
21 obj->data[obj->tail] = value;
22 obj->tail = obj->tail + 1;
23 return true;
24}
25
26bool queueDeQueue(Queue* obj) {
27 if (queueIsEmpty(obj)) {
28 return false;
29 }
30 obj->head = obj->head + 1;
31 return true;
32}
但这样一来有一个潜在的问题，当几次入队出队操作之后，队列看似是满了，但实际上队列的头部还有许多空闲空间，这样就造成了空间的浪费。
一个解决方法是，只要头指针和尾指针到达数组末尾，就重新绕回开头。这种实现称为循环队列。
循环队列使得队列判空和判满操作变得复杂，需要额外的判断。
一种常用的方法是，以一个单位空间为代价，即少用一个元素的空间，这样就可以区分队列满和队列空的情况。
当头尾指针相同时，认为队空，而当尾指针的下一个位置是头指针时，认为队满。
这样一来就有了下面的完整实现：
1typedef struct {
2 int *data;
3 int head;
4 int tail;
5 int size;
6} Queue;
7
8Queue* queueCreate(int maxSize) {
9 Queue *q = (Queue *)malloc(sizeof(Queue));
10 q->data = (int *)malloc(sizeof(int) * maxSize);
11 q->head = 0;
12 q->tail = 0;
13 q->size = maxSize;
14 return q;
15}
16
17bool queueIsEmpty(Queue* obj) {
18 return obj->head == obj->tail;
19}
20
21bool queueIsFull(Queue* obj) {
22 return (obj->tail + 1) % obj->size == obj->head;
23}
24
25bool queueEnQueue(Queue* obj, int value) {
26 if (queueIsFull(obj)) {
27 return false;
28 }
29 obj->data[obj->tail] = value;
30 obj->tail = (obj->tail + 1) % obj->size;
31 return true;
32}
33
34bool queueDeQueue(Queue* obj) {
35 if (queueIsEmpty(obj)) {
36 return false;
37 }
38 obj->head = (obj->head + 1) % obj->size;
39 return true;
40}
41
42int queueFront(Queue* obj) {
43 if (queueIsEmpty(obj)) {
44 return -1;
45 }
46 return obj->data[obj->head];
47}
48
49void queueFree(Queue* obj) {
50 free(obj->data);
51 free(obj);
52}
一些练习
意外的，队列在算法题中的考察并不多。至少 LeetCode 上很少有纯粹使用队列的题目。
但是，队列的应用场景很广，比如 BFS、LRU Cache 等等，都是使用队列来实现的。
操作系统，计算机网络中有许多排队问题，都是需要队列来模拟的。
LeetCode 622. 设计循环队列
这道题目是 LeetCode 上唯一一道纯粹使用队列的题目。
1type MyCircularQueue struct {
2 data []int
3 tail int
4 head int
5 size int
6}
7
8
9func Constructor(k int) MyCircularQueue {
10 return MyCircularQueue{
11 data: make([]int, k + 1),
12 tail: 0,
13 head: 0,
14 size: k + 1,
15 }
16}
17
18
19func (this *MyCircularQueue) EnQueue(value int) bool {
20 if this.IsFull() {
21 return false
22 }
23 this.data[this.tail] = value
24 this.tail = (this.tail + 1) % this.size
25 return true
26}
27
28
29func (this *MyCircularQueue) DeQueue() bool {
30 if this.IsEmpty() {
31 return false
32 }
33 this.head = (this.head + 1) % this.size
34 return true
35}
36
37
38func (this *MyCircularQueue) Front() int {
39 if this.IsEmpty() {
40 return -1
41 }
42 return this.data[this.head]
43}
44
45
46func (this *MyCircularQueue) Rear() int {
47 if this.IsEmpty() {
48 return -1
49 }
50 return this.data[(this.tail - 1 + this.size) % this.size]
51}
52
53
54func (this *MyCircularQueue) IsEmpty() bool {
55 return this.head == this.tail
56}
57
58
59func (this *MyCircularQueue) IsFull() bool {
60 return (this.tail + 1) % this.size == this.head
61}
62
63
64/**
65 * Your MyCircularQueue object will be instantiated and called as such:
66 * obj := Constructor(k);
67 * param_1 := obj.EnQueue(value);
68 * param_2 := obj.DeQueue();
69 * param_3 := obj.Front();
70 * param_4 := obj.Rear();
71 * param_5 := obj.IsEmpty();
72 * param_6 := obj.IsFull();
73 */
结果我还是把正经循环队列用 Go 又写了一遍。
评论