基本数据结构：队列

发表于 更新于 分类于 Waline：

队列是我们编程时必不可少的数据结构，可以用数组实现，也可以用链表实现，但是其实队列也有一些小的地方因为长时间不用而会忘记，这次就来稍微回忆一下。

什么是队列

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

两种实现方式

顺序队列

用数组方式实现的队列就是顺序队列，下面这段例子使用JavaScript语言实现的一个简单版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class myQueue {
    constructor(capacity) {
        this.items = new Array(capacity);
        this.n = capacity;
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        if (this.tail === this.n) {
            return false;
        }
        this.items[this.tail++] = item;
        return true;
    }

    dequeue() {
        if (this.head === this.tail) {
            return null;
        }
        let res = this.items[this.head++];
        return res;
    }
}

这段代码其实有一个很严重问题，那就是随着不断地入队，出队，head和tail都在不断向后移动，直到tail指向了最后，即使此时head前面有空间，也无法把数据插入。

那我们怎么解决这个问题呢？其实有很多方案，但归结一点就是数据搬移，我们这里说其中一种，就是改造以下我们的入队函数，当入队时发现tail已经到了队尾的位置了，把所有的数据搬移到从头部起始，再进行插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enqueue(item) {
    if (this.tail === this.n) {
        if (this.head === 0) {
            return false;
        }
        for (let i = this.head; i < this.tail; i++) {
            this.items[i - this.head] = this.items[i];
        }
        this.tail -= this.head;
        this.head = 0;
    }
    this.items[this.tail++] = item;
    return true;
}

循环队列

上面的代码其实已经能够实现一个队列的基本操作了，但是如果tail指向了队列尾部，就会涉及一次数据搬移，还是比较费时的，那我们能不能想个办法把这一步也给省略呢？

这里就涉及到了我大学时期刚学算法课时印象最深的一个设计了，我们把这个队列给掰弯，让它变成一个首位相接的环，这样当tail指向队尾时，再插入数据，tail指针就可以重新指向队列的头部，只要head指针不在头部就行。

在实现代码之前，我们首先要想一想，为什么这样是可以的，有什么要注意的地方？

第一个问题，我们可以回过头来思考以下，head和tail的作用实际上是什么？这两个值其实标记的是[head, tail)区间内的位置是有数据的，区间之外的位置是没有数据的，我们可以把这个items想象成一段铁轨，[head, tail)就是铁轨上的火车，如果这段铁轨是一段线段，那这列火车只能从头向尾移动，一旦移动到尾部，就只能把火车搬回头部，但是如果这段铁轨是个圆，那就可以省略掉把火车搬回头部这一过程。

第二个问题，上面我们也说过[head. tail)区间内的是有数据，这个区间是一个前闭后开空间，也就是说head指向的节点是有数据的，tail指向的是待插入数据的，如果指向了同一个，也就是初始情况，算是没有数据的。那如果我们将这个队列变成循环的，就会出现一个问题，当head = tail时，到底是初始状态还是tail又回来了？而且tail表明接下来可以在这里插入，但其实这里head已经被插入数据了。所以反过来讲我们不能让tail再绕一圈后回到head指向的地方，于是我们需要引入一个类似哨兵的位置，放在head的前面，当tail指向这里就算满队列了。

明白了这两个问题，就可以知道队空的条件为head = tail，队满的条件就是(tail + 1) % n = head

这个时候的代码就应该是这样的

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
class myQueue {
    constructor(capacity) {
        this.items = new Array(capacity);
        this.n = capacity;
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        if ((this.tail + 1) % this.n === this.head) {
            return false;
        }
        this.items[this.tail] = item;
        this.tail = (this.tail + 1) % this.n;
        return true;
    }

    dequeue() {
        if (this.head === this.tail) {
            return null;
        }
        let res = this.items[this.head];
        this.head = (this.head + 1) % this.n;
        return res;
    }
}

链式队列

上面讲的顺序队列无论如何优化，其实都有一个比较大的限制。

这个限制是数组这种数据结构带来的，那就是必须事先定义好队列的长度，因为数组需要一块连续的内存来保证可以根据下标进行O(1)的随机访问。

有的人可能会问，Javascript 中的数组长度是可变的啊，其实这个要去看一下Javascript内部对于数组是怎么实现的，一种方案是当我们没有给长度的时候，会帮助我们申请一段内存使用，当发现长度不够时，会帮助我们申请一段更大的内存（一般是1.5倍），然后帮我们把数据拷贝过去。

那如果我们使用链表来实现队列，还会有这个问题吗？答案是没有，因为链表的内存是不连续的，所以不需要事先申请好，而且由于队列的特殊性，我们并不需要根据下标去随机访问，所以说看起来用链表来实现一个队列更好，那我们就先来试一下。

在尝试之前我们还是要想明白两个问题：

  • 队空的条件是什么？
  • 队满的条件是什么？

针对这两个问题。第一个问题答案是，head指向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
26
27
28
29
30
31
32
class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class myQueue2 {
    constructor() {
        this.head = this.tail = null;
    }

    enqueue(item) {
        if (this.tail === null) {
            this.head = this.tail = new Node(item);
        } else {
            let newNode = new Node(item);
            this.tail.next = newNode;
            this.tail = this.tail.next;
        }
        return item;
    }

    dequeue() {
        if (this.head === null) {
            return null
        }
        let res = this.head.val;
        this.head = this.head.next;
        return res;
    }
}

这个代码已经可以正常工作了，但是还有几个问题我们要思索一下：

  • 会不会有内存泄漏？比如在dequeue到最后head为null时，tail其实还保存着对最后一个节点的引用
  • 哨兵节点在这里有没有用处？

两种使用场景

阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

所谓的CAS原子操作，就是Compare and Set就是先比较队尾的数据与自己上次获取的是不是相同的，如果相同的说明队列没有被其他线程更新过，就可以set值进去，如果不相同的，说明队列已经被更新过了。

这个设计思想是不是有点像区块链？