导语：数据结构：队列—线程池等有限资源池是如何实现的

一、定义

队列（queue）是一种线性数据结构，

队列中的元素只能先入先出（First In First Out，简称 FIFO）。

队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

二、存储原理

队列这种数据结构既可以用数组来实现，也可以用链表来实现。

1、数组实现

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置

用数组实现的队列叫作顺序队列

2、链表实现

用链表实现的队列叫作链式队列，链表头节点是队头，链表尾节点是队尾。

三、操作

1、入队（enqueue）

把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位 置将会成为新的队尾。

//1、数组队列实现int[] nums;// head表示队头下标，tail表示队尾下标int head = 0;int tail = 0;public ArrayQueue(int size){    nums = new int[size];}public boolean enqueue(int n){    if(tail == nums.length) return false;    nums[tail] = n;    ++tail;    return true;}//2、链表队列实现    Node head;    Node tail;//链表节点数量    int size;    public void enqueue(Node node){        if(tail == null){            head = node;            tail = node;        }else {            //当前尾部节点下一个指针指向新增节点            tail.next = node;            //尾部节点标记为新增节点            tail = node;        }        size++;    }

2、出队（dequeue）

就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元 素将会成为新的队头。

//1、数组队列实现public int dequeue(){    // 如果head == tail 表示队列为空    if(head == tail) return 0;    int ret = nums[head];    ++head;    return ret;}//2、链表队列实现    public Node dequeue(){        if(head == null)return null;        Node h = head;        //链表头变成表头的下一个节点        head = head.next;        //把旧的表头的下一个节点指向设置为null，让gc回收        h.next = null;        if(head == null) tail = null;        size--;        return h;    }

四、时间复杂度

入队和出队都是O(1)，因为通过变量属性记录队头和队尾，入队和出队不需要遍历，只需要操作队头和队尾即可。

五、应用

资源池、消息队列、命令队列等等

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请与我联系，一经查实立刻删除内容。本文内容由快快网络小开创作整理编辑！