看得见的数据结构Android版之队列篇

1,899 阅读8分钟

零、前言

1.现实世界里我们更多讲究的是先来后到,先排队先买票,这样才有秩序,毕竟我们没有计算机那么有耐心
2.使用队列结构能很好的模拟和解决类似生活中的事,比如消息的发送用队列维护就是非常恰当的
3.队列就像去动物园买票,先处理队列的头部,有新的人来了就后面排着去,慢慢等
4.还有一种很有意思的队列是循环队列,它是由于数组对头部操作的困难性,从而转变一种思路,让数组也能很好的实现队列结构,后面会仔细分析一下
5.本例操作演示源码:希望你可以和我在Github一同见证:DS4Android的诞生与成长,欢迎star

1.留图镇楼:队列的最终实现的操作效果:
数组实现普通队列:

蓝色区域是数组看见:初始化四个空间,不够再扩容,空闲太多再缩容

数组实现普通队列.gif

链表实现普通队列:

队列综合操作.gif


2.队列结构的简介:
队列是一种线性的数据结构  
特性:尾部添加,头部取出 即先进先出FIFO  
操作:enqueue入队  dequeue出队  getFront查看队首元素

队列.png


一、队列接口

兵马未动,粮草先行,有接口好办事。

/**
 * 作者:张风捷特烈
 * 时间:2018/8/17 0017:15:57
 * 邮箱:1981462002@qq.com
 * 说明:队列接口
 */
public interface IQueue<T> {
    /**
     * 入队
     * @param el 元素
     */
    void enqueue(T el);

    /**
     * 出队
     * @return 元素
     */
    T dequeue();

    /**
     * 获取队首元素
     * @return 队首元素
     */
    T getFront();

    /**
     * 获取队列元素个数
     * @return 元素个数
     */
    int getSize();

    /**
     * 是否为空
     * @return 是否为空
     */
    boolean isEmpty();
}

二、普通队列的数组实现

普通队列的数组实现----性能非常差,后面用数组实现循环队列来优化
为什么会很差,因为尾添加和头删除,总有一个会让所有的人挪一挪,后面会用数组实现循环队列来优化

/**
 * 作者:张风捷特烈
 * 时间:2018/8/17 0017:15:57
 * 邮箱:1981462002@qq.com
 * 说明:普通队列的数组实现----性能非常差,后面用数组实现循环队列来优化
 */
public class ArrayChartQueue<E> implements IQueue<E> {
    private ArrayChart<E> array;//成员变量

    public ArrayChartQueue(int capacity) {
        this.array = new ArrayChart<>(capacity);
    }

    public ArrayChartQueue() {
        this.array = new ArrayChart<>();
    }

    @Override
    public void enqueue(E el) {
        array.add(el);
    }

    @Override
    public E dequeue() {
        return array.remove(0);
    }

    @Override
    public E front() {
        return array.get(0);
    }

    @Override
    public int size() {
        return array.size();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
}
2.数组普通队列的插入演示:

由于是基于数组来实现,所以一切的操作也是基于数组
初始四个大小的数组,就像招待处预留四把椅子,然后等椅子坐满了,再来加椅子

数组普通队列的插入.gif

3.数组普通队列的查看首元演示:

数组普通队列查看首元.gif

4.数组普通队列的移除演示:

数组表结构移除头部...万恶之源,千万不要用,此处仅演示! 此处仅演示!此处仅演示!!
数组表结构移除头部...万恶之源,千万不要用,此处仅演示! 此处仅演示!此处仅演示!!

数组普通队列移除首元.gif


三、循环队列

基于数组实现的队列在队首取出时会使得整队移动,效率会很低
但是壮哉我大数组,岂会连个小小的队列都搞不定,以后还哪还有脸立足王座...于是循环队列出现了
说起循环大家脑子里都是一个圈来回转,循环小数表示不服... 只要有周期性就是循环,想成一个圈就狭隘了

1.循环队列实现的思路:
不就是想要知道队尾和队首是那个嘛,我标出来,维护一下给你不就行了吗  
注意:这里的优势在于维护了队尾和队首的标示,插入尾和删除头都是定点,而且数组整体不移动,而是标示在动
新加元素时,队尾表识后移,不够就扩容。删除头时队首标示  

循环队列特点:
为空时,`队尾标示==队首标示`,
队列满:`(队尾标示+1)%数组长度==队首标示`   
循环队列会使队首前一个位置不可用。

循环队列.png

循环队列循环机制.png

/**
 * 作者:张风捷特烈
 * 时间:2018/8/17 0017:16:03
 * 邮箱:1981462002@qq.com
 * 说明:数组实现循环队列
 */
public class ArrayLoopQueue<T> implements IQueue<T> {
    private T[] data;// 队列数据
    private int head;//队首标示
    private int tail;//队尾标示
    private int size;//元素个数
    public ArrayLoopQueue() {//无参构造:默认8个容量
        this(8);
    }
    public ArrayLoopQueue(int capacity) {
        // 因为会有一个浪费,所以+1
        data = (T[]) new Object[capacity + 1];
        head = 0;
        tail = 0;
        size = 0;
    }
    @Override
    public void enqueue(T el) {
        if (isFull()) {//加入时满了---扩容
            grow(capacity() * 2);
        }
        data[tail] = el;//在队尾插入
        //插入数据时对尾标示进行维护-----
        tail = (tail + 1) % data.length;
        size++;
    }
    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("MakeSure it's not an empty
        }
        T ret = data[head];
        data[head] = null;//让队首移除
        //队首移除时对首标示进行维护-----
        head = (head + 1) % data.length;
        size--;
        //闲置太多---缩容
        if (size == capacity() / 4 && capacity() / 2 != 0 && size > 4) {
            grow(capacity() / 2);
        }
        return ret;
    }
    @Override
    public T front() {
        if (isEmpty()) {
            throw new IllegalArgumentException("MakeSure it's not an empty
        }
        return data[head];
    }
    /**
     * 扩容/缩容
     *
     * @param newCapacity 新的容量
     */
    private void grow(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // 此时在newData中队首对齐回来,data中就得有一个front的偏移量
            newData[i] = data[(i + head) % data.length];
        }
        data = newData;
        head = 0;
        tail = size;
    }
    /**
     * 获取容量
     *
     * @return 容量
     */
    public int capacity() {
        return data.length - 1;
    }
    /**
     * 队列元素个数
     *
     * @return 元素个数
     */
    @Override
    public int size() {
        return size;
    }
    /**
     * 是否为空
     *
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }
    /**
     * 队列是否满了
     *
     * @return 队列是否满了
     */
    private boolean isFull() {
        // tail的下一个位置等于head时
        return (tail + 1) % data.length == head;
    }
}

四、单链表式实现队列结构

链表和队列可谓天然配,链表的头删除,头获取很快,但尾添加要获取尾部,需要遍历一次,不好
但可以维护首位标识,使队尾也容易获取。(当然你也可以用双链表...直接批件衣服,改都不用改)
注释的很清楚了,看着代码顺一下,或debug走一波,我就不赘述了

/**
 * 作者:张风捷特烈
 * 时间:2018/8/17 0017:22:50
 * 邮箱:1981462002@qq.com
 * 说明:单链表实现队列
 */
public class SingleLinkedQueue<T> implements IQueue<T> {

    private Node head;//头节点
    private Node tail;//尾节点

    private int size;//元素个数

    public SingleLinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T el) {//入队
        // 如果队尾为空,说明队列是空的。因为tail一直指向最后一个非空节点。
        if (tail == null) {
            tail = new Node(null, el);//初始化
            head = tail;
        } else {
            tail.next = new Node(null, el); // 新来的排到后面去
            tail = tail.next; //更新队尾
        }
        size++;
    }

    @Override
    public T dequeue() {//出队
        if (isEmpty())
            throw new IllegalArgumentException("MakeSure it's not an empty queue");
        Node targetNode = head;//我是老大
        head = head.next; // 我是老二,但我要篡位了...以后哥就是老大
        targetNode.next = null; //前任老大走了....
        if (head == null) {// 如果头结点为空
            tail = null;
        }
        size--;
        return targetNode.el;
    }

    @Override
    public T front() {
        if (isEmpty())
            throw new IllegalArgumentException("MakeSure it's not an empty queue");
        return head.el;
    }

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

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

    private class Node {
        private T el;//改节点上的元素
        private Node next; //下一节点
        /**
         * 两参构造
         *
         * @param next //下一节点
         * @param el   生成节点的元素值
         */
        private Node(Node next, T el) {
            this.el = el;
            this.next = next;
        }
    }
}

五、小结

1.数组普通队列:ArrayChartQueue测试
方法\数量1000次10000次10W次100W次1000次
enqueue0.0006秒0.0022秒0.01571秒0.06668秒1.1375秒
dequeue0.0111秒0.2707秒18.7684秒------
2.数组环形队列:ArrayLoopQueue测试

方法\数量|1000|次10000次|10W次|100W次|1000次 --- |---|---|---|---|---|---| enqueue|0.0004秒|0.0019秒|0.01775秒|0.05414秒|0.6896秒 dequeu|0.0005秒|0.0021秒|0.0091秒|0.0360秒|0.3327秒

3.链表队列:SingleLinkedStack测试
方法\数量1000次10000次10W次100W次1000次
enqueue0.0011秒0.0031秒0.0099秒0.4881秒3.1186秒
dequeue0.0002秒0.0013秒0.0046秒0.0221秒0.1388秒

可见循环队列还是蛮好的,壮哉,我大数组!
数组普通队列,就认识一下吧...不要用它。
数组环形队列和链表队列的比较也就相当于数组和链表的比较


本系列后续更新链接合集:(动态更新)

后记:捷文规范

2.本文成长记录及勘误表
项目源码日期备注
V0.1--github2018-11-24看得见的数据结构Android版之队列结构的实现
3.更多关于我
笔名QQ微信爱好
张风捷特烈1981462002zdl1994328语言
我的github我的简书我的掘金个人网站
4.声明

1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3----个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正
4----看到这里,我在此感谢你的喜欢与支持


icon_wx_200.png