数据结构-队列结构

2021-08-02  本文已影响0人  acc8226

如何理解“队列”？

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

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

顺序队列和链式队列

我们知道了，队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那究竟该如何实现一个队列呢？

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

我们先来看下基于数组的实现方法。

IQueue 接口定义

package com.s4.queue;

public interface IQueue {

    // 队列的已用长度
    public abstract int getLength();

    // 队列的预设长度
    public abstract int getPresetLength();
    
    // 入队操作
    public abstract boolean enqueue(Object value);

    public abstract boolean isEmpty();

    public abstract boolean isFull();

    // 出队操作，复杂度是 O(1)
    public abstract Object dequeue();

}

ArrayQueue 关键代码

    /*
     * 入队操作: 这个是优化后的方案。入队操作的时间复杂度还是 O(1)
     */
    @Override
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            if (this.head == 0) {
                return false;
            }
            // 进行迁移[head, tail) 左移 head 位
            for (int i = this.head; i < this.tail; i++) {
                this.datas[i - this.head] = this.datas[i];
            }
            // 搬移完之后更新 head 和 tail
            this.tail -= this.head;
            this.head = 0;
        }
        this.datas[this.tail] = value;
        this.tail++;
        return true;
    }

    // 入队操作: 这是一个错误示例，一个较差的方法
    public boolean enqueueBad(Object value) {
        if (this.isFull()) {
            return false;
        }
        this.datas[this.tail] = value;
        this.tail++;
        return true;
    }

    /*
     * 出队操作，复杂度是 O(1)
     */
    @Override
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Object ret = this.datas[this.head];
        this.head++;
        return ret;
    }

    // 每次出队都会迁移，会增加时间复杂度为O(n)，因此不推荐这么做
    @Deprecated
    public Object dequeue2() {
        if (this.isEmpty()) {
            return null;
        }
        // 每次进行出队操作都相当于删除数组下标为 0 的数据
        Object ret = this.datas[0];
        // [1, tail -1] 整体左移一位 [1, tail) | [0, tail - 1)
        for (int i = 0; i < tail - 1; i++) {
            this.datas[i] = this.datas[i + 1];
        }
        this.tail--;
        this.datas[this.tail] = null;
        return ret;
    }

}

为了解决随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了的问题？

除了 dequeue2 这种思路外，可以在依旧保留出队代码不变的基础上，在入队的时候使用 enqueue 进行数据迁移。

接下来，我们再来看下基于链表的队列实现方法。

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。我将具体的代码放到 GitHub 上，你可以自己试着实现一下，然后再去 GitHub 上跟我实现的代码对比下，看写得对不对。

LinkedQueue 关键代码

    // 入队操作
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            return false;
        }
        Node node = new Node();
        node.data = value;
        node.next = null;
        if (this.isEmpty()) {
            this.head = node;
        } else {
            this.tail.next = node;
        }
        this.tail = node;
        this.length++;
        return true;
    }
    
    // 出队操作，复杂度是 O(1)
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Node nextNode = this.head.next;
        Object ret = this.head.data;
        this.head.data = null;
        this.head.next = null;
        this.head = nextNode;
        if (nextNode == null) {
            this.tail = null;
        }
        this.length--;
        return ret;
    }

循环队列

我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队列的解决思路。

循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。我画了一张图，你可以直观地感受一下。

我们可以发现，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。

CircleQueue 关键代码

    /*
     * 入队
     */
    @Override
    public boolean enqueue(Object value) {
        if (this.isFull()) {
            return false;
        }
        this.datas[this.tail] = value;
        this.tail = indexPlus(this.tail);
        return true;
    }

    /*
     * 出队，复杂度是 O(1)
     */
    @Override
    public Object dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        Object ret = this.datas[this.head];
        this.head = this.indexPlus(this.head);
        return ret;
    }

阻塞队列和并发队列

前面讲的内容理论比较多，看起来很难跟实际的项目开发扯上关系。确实，队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。

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

你应该已经发现了，上述的定义就是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。

前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？

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

内容小结

我的代码实现
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s4

今天我们讲了一种跟栈很相似的数据结构，队列。关于队列，你能掌握下面的内容，这节就没问题了。

队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。特别是长得像一个环的循环队列。

在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。循环队列是我们这节的重点。要想写出没有 bug 的循环队列实现代码，关键要确定好队空和队满的判定条件，具体的代码你要能写出来。

除此之外，我们还讲了几种高级的队列结构，阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。

参考

09 | 队列：队列在线程池等有限资源池中的应用
https://time.geekbang.org/column/article/41330

java/09_queue · 编程语言算法集/algo - 码云 - 开源中国 https://gitee.com/TheAlgorithms/algo/tree/master/java/09_queue

上一篇下一篇

猜你喜欢

热点阅读