队列是先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。

队列的操作在两端进行，即在后端（rear）进行插入操作也就是入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue
在队列中，删除的数据还保留着内存中，但头指针已不再指向它
队列和栈一样，存在上溢和下溢。此外，还存在”假溢出“现象

队列的分类

为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：
front=rear
当队满时：front=rear 亦成立

单队列

单队列又分为顺序队列(数组实现)和链式队列(链表实现)。单队列从前面删除元素，从后面插入元素，类似于现实中的排队（只是不允许插队?）。

顺序队列

队列的顺序存储结构，又称为顺序队列，顺序队列实际上是运算受限的顺序表。

在顺序队列，由于数组分配的存储空间存在边界，头尾指针不断增加而不减小（或只减小而不增加），被删除元素的存储空间不能重新利用，会发生”假溢出“，即明明有位置却不能添加元素。

解决假溢出的方法有许多种，如：设定队首指针不动，只要插入元素，在队列的末尾直接插入；只要删除元素，从队首的位置直接删除就行了，但这样会造成大量的数据元素移动。一种更好的办法是，将队列循环起来，也就是循环队列。

链式队列

链式队列，使用带头指针front和尾指针rear的单链表实现。一般用单向链表来实现，不采用循环双链表或者双链表主要是双链表的空间开销（空间复杂度，多前继指针）相对单链表来说大了不少，而单链表只要新增头指针和尾指针就可以轻松实现常数时间内（时间复杂度为O(1)）访问头尾结点。

Java实现链式队列的其中一种方法：

class linkqueue{
    private link front;
    private link rear;
    public linkqueue(){
        setup();
    }
    public linkqueue(int sz){
        setup();
    }
    //初始化
    private void setup(){
        rear=null;
        front=rear;
    }
    //清空队列
    public void clear(){
        rear=null;
        front=rear
    }
    //插入元素
    public void enqueue(object it){
        if(rear!=null){
            rear.setNext(new link(it,null));
            rear=rear.next();
        }
        else front=rear=new link(it,null);
    }
    //删除元素
    public object dequeue(){
        assert.notfalse(!isempty());
        object it = front.element();
        front = front.next();
        if(front==null)
            tear=null;
        return it;
    }
}

循环队列

循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，令rear指向front，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。但是，在顺序队列中，frontrear即表示队列为空，在循环队列则不然，由于头尾相接，队列为满时，也会体现为frontrear。这里有两种解决方法：

可以一个标志变量 flag,当 front==rear 并且 flag=0 的时候队列为空，当front==rear 并flag=1 的时候队列为满。
队列为空的时候就是 front==rear ，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，那么现在判断队列是否为满的条件就是： (rear+1) % QueueSize= front 。

循环队列入队时：rear=(rear+1)%maxsize，出队时: front=(front+1)%maxsize

双端队列

双端队列是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫做insertLeft()和insertRight()，以及removeLeft()和removeRight()。

如果禁止调用insertLeft()和removeLeft()方法（或禁用右端操作），双端队列的功能就和栈一样。

如果禁止调用insertLeft()和removeRight()方法（或相反的一对方法），它的功能就和单队列一样了。

在容器类库中有时会用双端队列来提供栈和队列两种功能。由于不太常用，这里偷个懒，不深入研究了。

优先级队列

优先级队列是比栈和队列更专用的数据结构，但它在很多情况下都很有用。像普通队列一样，优先级队列有一个队头和一个队尾，并且也是从队头移除数据项。不过在优先级队列中，数据项按关键字的值有序，这样一来，关键字最小（或最大）的数据项就总是在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

常见应用场景

阻塞队列： 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。
消息队列
操作系统的进程调度

原文链接：https://blog.csdn.net/fkidi/article/details/123851425