美文网首页程序员Java 杂谈数据结构和算法分析
05-图解数据结构之队列--Queue

05-图解数据结构之队列--Queue

作者: e4e52c116681 | 来源:发表于2018-09-24 10:38 被阅读13次

零、前言

栈是一种线性的数据结构
特性：尾部添加，头部取出 即先进先出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 ArrayGroupQueue<E> implements IQueue<E> {

    /**
     * 成员变量
     */
    private ArrayGroup<E> array;

    public ArrayGroupQueue(int capacity) {
        this.array = new ArrayGroup<>(capacity);
    }

    public ArrayGroupQueue() {
        this.array = new ArrayGroup<>();
    }

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

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

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

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

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("IQueue ：");
        res.append("front [ ");
        for (int i = 0; i < array.size(); i++) {
            res.append(array.get(i));
            if (i != array.size() - 1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

}
数组普通队列测试
 /**
  * 数组队列测试
  */
 private static void arrayQueueTest() {
     ArrayGroupQueue<Integer> queue = new ArrayGroupQueue<>();
     for (int i = 0; i < 5; i++) {
         queue.enqueue(i);
         System.out.println(queue);
     }
     queue.dequeue();
     System.out.println(queue);
     //IQueue ：front [ 0] tail
     //IQueue ：front [ 0, 1] tail
     //IQueue ：front [ 0, 1, 2] tail
     //IQueue ：front [ 0, 1, 2, 3] tail
     //IQueue ：front [ 0, 1, 2, 3, 4] tail
     //IQueue ：front [ 1, 2, 3, 4] tail
 }

三、循环队列

基于数组实现的队列在队首取出是会使得整队移动，而使时间复杂度为O(n)
可以使用循环队，基于队首队尾两个标示来固定队列，从而使得时间复杂度为O(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 front;
    /**
     * 队尾标示
     */
    private int tail;

    /**
     * 元素个数
     */
    private int size;

    /**
     * 无参构造：默认10个容量
     */
    public ArrayLoopQueue() {
        this(11);
    }

    /**
     * 一参构造
     *
     * @param capacity 队列容量
     */
    public ArrayLoopQueue(int capacity) {
        // 因为会有一个浪费，所以+1
        data = (T[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    @Override
    public void enqueue(T el) {
        if (isFull()) {
            grow(getCapacity() * 2);
        }
        data[tail] = el;
        //插入数据时对尾标示进行操作
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        T ret = data[front];
        data[front] = null;
        //插入数据时对首标示进行操作
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            grow(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        return data[front];
    }

    /**
     * 重新确定容量
     * @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 + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 获取容量
     * @return 容量
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 队列元素个数
     * @return 元素个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 是否为空
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 队列是否满了
     * @return 队列是否满了
     */
    public boolean isFull() {
        // tail的下一个位置等于front时
        return (tail + 1) % data.length == front;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("ArrayLoopQueue: size = %d, capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) // 最后一个元素不要加，
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}
测试：
/**
 * 循环队列测试
 */
private static void LoopQueueTest() {
    ArrayLoopQueue<Integer> queue = new ArrayLoopQueue<>(8);
    for (int i = 0; i < 8; i++) {
        queue.enqueue(i);
    }
    System.out.println(queue);
    //ArrayLoopQueue: size = 8, capacity = 8
    //front [0, 1, 2, 3, 4, 5, 6, 7] tail
    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    queue.enqueue(10);
    System.out.println(queue.getFront());//4
    System.out.println(queue);
    //ArrayLoopQueue: size = 5, capacity = 8
    //front [4, 5, 6, 7, 10] tail
}

四、链表式集合实现队列

链表和队列可谓天然配，链表的头删除，头获取都是O(1),但尾添加是O(n),但可以维护首位标识，使尾加也为O(1)

/**
 * 作者：张风捷特烈
 * 时间：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把新Node挂载上来。
            tail.next = new Node(null, el);
            // tail后挪
            tail = tail.next;
        }
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node targetNode = head;
        head = head.next; // head后移
        targetNode.next = null; // 元素置空
        if (head == null) {// 如果头结点为空
            tail = null;
        }

        size--;
        return targetNode.el;
    }

    @Override
    public T getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("IQueue is empty.");
        return head.el;
    }

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("IQueue: front ");

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }


    private class Node {
        public T el;//改节点上的元素
        public Node next; //下一节点


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

        @Override
        public String toString() {
            return el.toString();
        }
    }
}

四、时间测试

数组普通队列：ArrayGroupQueue测试
方法\数量 复杂度 1000 次10000次 10W次 100W次 1000次
enqueue O(1) 0.0006秒 0.0022秒 0.01571秒 0.06668秒 1.1375秒
dequeue O(n) 0.0111秒 0.2707秒 18.7684秒 ---- --
getFront O(1) -- -- -- -- --
数组环形队列：ArrayLoopQueue测试
方法\数量 复杂度 1000 次10000次 10W次 100W次 1000次
enqueue O(1) 0.0004秒 0.0019秒 0.01775秒 0.05414秒 0.6896秒
dequeue O(1) 0.0005秒 0.0021秒 0.0091秒 0.0360秒 0.3327秒
getFront O(1) -- -- -- -- --
链表队列：SingleLinkedStack测试
方法\数量 复杂度 1000 次10000次 10W次 100W次 1000次
enqueue O(1) 0.0011秒 0.0031秒 0.0099秒 0.4881秒 3.1186秒
dequeue O(1) 0.0002秒 0.0013秒 0.0046秒 0.0221秒 0.1388秒
getFront O(1) -- -- -- -- --

后记、

1.声明：

[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明
[2]欢迎广大编程爱好者共同交流
[3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
[4]你的喜欢与支持将是我最大的动力

2.连接传送门：

更多数据结构知识欢迎访问:图解数据结构
项目源码均在我的https://github.com/toly1994328/DS：欢迎star
张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com

3.联系我

QQ:1981462002
邮箱：1981462002@qq.com
微信：zdl1994328

4.欢迎关注我的微信公众号，最新精彩文章，及时送达：
公众号.jpg

相关文章

网友评论

    本文标题：05-图解数据结构之队列--Queue

    本文链接：https://www.haomeiwen.com/subject/xwpcoftx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    程序员

    Java 杂谈

    数据结构和算法分析

    数据结构

    关于我们|服务条款|联系我们|05-图解数据结构之队列--Queue|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！