看动画学算法之: 队列 queue

程序那些事

关注

发布于: 刚刚

简介队列 Queue 是一个非常常见的数据结构，所谓队列就是先进先出的序列结构。

想象一下我们日常的排队买票，只能向队尾插入数据，然后从队头取数据。在大型项目中常用的消息中间件就是一个队列的非常好的实现。

队列的实现一个队列需要一个 enQueue 入队列操作和一个 DeQueue 操作，当然还可以有一些辅助操作，比如 isEmpty 判断队列是否为空，isFull 判断队列是否满员等等。

为了实现在队列头和队列尾进行方便的操作，我们需要保存队首和队尾的标记。

先看一下动画，直观的感受一下队列是怎么入队和出队的。

先看入队：

再看出队：

可以看到入队是从队尾入，而出队是从队首出。

队列的数组实现和栈一样，队列也有很多种实现方式，最基本的可以使用数组或者链表来实现。

先考虑一下使用数组来存储数据的情况。

我们用 head 表示队首的 index，使用 rear 表示队尾的 index。

当队尾不断插入，队首不断取数据的情况下，很有可能出现下面的情况：

上面图中，head 的 index 已经是 2 了，rear 已经到了数组的最后面，再往数组里面插数据应该怎么插入呢？

如果再往 rear 后面插入数据，head 前面的两个空间就浪费了。这时候需要我们使用循环数组。

循环数组怎么实现呢？只需要把数组的最后一个节点和数组的最前面的一个节点连接即可。

有同学又要问了。数组怎么变成循环数组呢？数组又不能像链表那样前后连接。

不急，我们先考虑一个余数的概念，假如我们知道了数组的 capacity，当要想数组插入数据的时候，我们还是照常的将 rear+1，但是最后除以数组的 capacity, 队尾变到了队首，也就间接的实现了循环数组。

看下 java 代码是怎么实现的：

public class ArrayQueue {

//存储数据的数组private int[] array;//head索引private int head;//real索引private int rear;//数组容量private int capacity;
public ArrayQueue (int capacity){    this.capacity=capacity;    this.head=-1;    this.rear =-1;    this.array= new int[capacity];}
public boolean isEmpty(){    return head == -1;}
public boolean isFull(){    return (rear +1)%capacity==head;}
public int getQueueSize(){    if(head == -1){        return 0;    }    return (rear +1-head+capacity)%capacity;}
//从尾部入队列public void enQueue(int data){    if(isFull()){        System.out.println("Queue is full");    }else{        //从尾部插入        rear = (rear +1)%capacity;        array[rear]= data;        //如果插入之前队列为空,将head指向real        if(head == -1 ){            head = rear;        }    }}
//从头部取数据public int deQueue(){    int data;    if(isEmpty()){        System.out.println("Queue is empty");        return -1;    }else{        data= array[head];        //如果只有一个元素，则重置head和real        if(head == rear){            head= -1;            rear = -1;        }else{            head = (head+1)%capacity;        }        return data;    }}

复制代码

}大家注意我们的 enQueue 和 deQueue 中使用的方法：

rear = (rear +1)%capacityhead = (head+1)%capacity 这两个就是循环数组的实现。

队列的动态数组实现上面的实现其实有一个问题，数组的大小是写死的，不能够动态扩容。我们再实现一个能够动态扩容的动态数组实现。

//因为是循环数组，这里不能做简单的数组拷贝private void extendQueue(){    int newCapacity= capacity*2;    int[] newArray= new int[newCapacity];    //先全部拷贝    System.arraycopy(array,0,newArray,0,array.length);    //如果real<head,表示已经进行循环了，需要将0-head之间的数据置空，并将数据拷贝到新数组的相应位置    if(rear< head){        for(int i=0; i< head; i++){            //重置0-head的数据            newArray[i]= -1;            //拷贝到新的位置            newArray[i+capacity]=array[i];        }        //重置real的位置        rear= rear+capacity;        //重置capacity和array        capacity=newCapacity;        array=newArray;    }}

复制代码

需要注意的是，在进行数组扩展的时候，我们不能简单的进行拷贝，因为是循环数组，可能出现 rear 在 head 后面的情况。这个时候我们需要对数组进行特殊处理。

其他部分是和普通数组实现基本一样的。

队列的链表实现除了使用数组，我们还可以使用链表来实现队列，只需要在头部删除和尾部添加即可。

看下 java 代码实现：

public class LinkedListQueue {//head 节点 private Node headNode;//rear 节点 private Node rearNode;

class Node {    int data;    Node next;    //Node的构造函数    Node(int d) {        data = d;    }}
public boolean isEmpty(){    return headNode==null;}
public void enQueue(int data){    Node newNode= new Node(data);    //将rearNode的next指向新插入的节点    if(rearNode !=null){        rearNode.next=newNode;    }    rearNode=newNode;    if(headNode == null){        headNode=newNode;    }}
public int deQueue(){    int data;    if(isEmpty()){        System.out.println("Queue is empty");        return -1;    }else{        data=headNode.data;        headNode=headNode.next;    }    return data;}

复制代码

}队列的时间复杂度上面的 3 种实现的 enQueue 和 deQueue 方法，基本上都可以立马定位到要入队列或者出队列的位置，所以他们的时间复杂度是 O(1)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/12-algorithm-queue/

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/2f445dfa959e0a529a22d0b29】。文章转载请联系作者。

程序那些事

关注

关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！

发布

暂无评论

创作场景

看动画学算法之: 队列 queue

程序那些事

评论