队列

什么是队列

什么是队列？队列就是一个队伍。队列和栈一样，由一段连续的存储空间组成，是一个具有自身特殊规则的数据结构。栈是后进先出的规则，队列刚好相反，是一个先进先出(FIFO，First In First Out)或者说是后进后出(LILO，Last In Last Out)的数据结构。

队列是一种受限的数据结构，插入操作只能从一端操作，这一端叫做队尾；二移除操作也只能从另一端操作，这一段叫作对头。

我们将没有元素的队列称为空队。往队列中插入元素的操作叫作入队，相应的，从队列中移除元素的操作叫作出队。

一般而言，队列的实现有两种方式：数组和链表。用数组实现队列有两种方式，一种是顺序队列，一种是循环队列。

用数组实现队列，若出现队列满了的情况，则这时就算有新的元素需要入队，也没有位置。此时一般的选择是要么丢掉，要么等待，等待时间由程序控制。

队列的存储结构

顺序队列会有两个标记，一个是对头位置(head)，一个是下一个元素可以插入的队尾位置(tail)。一开始两个标记都指向数组下表为0的位置。

在插入元素之后，tail标记就会加1，如入队三个元素，分别是A、B、C，则当前标记即存储情况。head指向0，tail指向3。

当head为0时，tail为3.接下来进行出队操作，出队一个元素，head指向的位置则加1。比如进行一次出队操纵之后，顺序队列存储情况。head指向1，tail指向3。

因此，在顺序队列中，对队列中元素的个数我们可以用tail减去head计算。当head与tail相等时，队列为空队，当tail达到数组的长度，也就是队列存储之外的位置时，说明这个队列已经无法容纳其他元素入队了。空间是否满了？并没有，由于两个标记只增不减，所以两个标记最终都会到数组的最后一个元素之外，这是虽然数组是空的，但也无法再往队列里加入元素了。

当队列中无法再加入元素时，我们称之为“上溢”; 当顺序队列还有空间却无法入队时，我们称之为“假上溢”；如果空间真的满了，则我们称之为“真上溢”；如果队列是空的，则执行出队操作，此时队列里没有元素，能不能出队，我们称之为“下溢”。

怎么解决顺序队列的“假上溢”问题，这时就需要采用循环队列了。

当顺序队里出现假上溢时，其实数组前端还有空间，我们可以不把标记指向数组外的地方，只需要把这个标记重新指向开始处就能够解决。想想一下这个数组首尾相接，成为一个圈。存储结构还是在一个数组上。

一般而言。我们在对head或者tail加1时，为了方便，可直接对结果取余数组长度，得到我们徐亚的数组长度。另外由于顺序队列存在“假上溢”的问题，所有在实际使用过程中都是使用循环队列来实现的。

但是循环队列中会出现这样一种情况：当队列没有元素时，head等于tail，而当队列满了时，head也等于tail。为了区分这两种状态，一般在循环队列中规定队列长度只能为数组总长度减1，即有一个位置不放元素。因此，当head等于tail时，说明队列为空队，而当head等于(tail+1)%length时，说明队满。

代码如下

public class ArrayQueue<T> {

    private final Object[] items;

    private int head = 0;

    private int tail = 0;

    /**
     * 初始化队列
     *
     * @param capacity 队列长度
     */
    public ArrayQueue(int capacity) {
        this.items = new Object[capacity];
    }

    /**
     * 入队
     *
     * @param item 入队元素
     * @return 是否入队
     */
    public boolean put(T item) {
        if (head == (tail + 1) % items.length) {
            //表示队满
            return false;
        }
        items[tail] = item;
        //tail 标记往后移一位
        tail = (tail + 1) % items.length;
        return true;
    }

    /**
     * 获取队列头元素，不出队
     *
     * @return 队列头元素
     */
    @SuppressWarnings("unchecked")
    public T peek() {
        if (head == tail) {
            return null;
        }
        return (T)items[head];
    }

    /**
     * 出队
     *
     * @return 头部元素
     */
    @SuppressWarnings("unchecked")
    public T poll() {
        if (head == tail) {
            return null;
        }
        T item = (T)items[head];
        //把没有用的元素赋空值，当然也可以不设置，标记移动了，之后会被覆盖。尽量还是设置null
        items[head] = null;
        //head标记往后移动一位
        head = (head + 1) % items.length;
        return item;
    }

    public boolean isFull() {
        return head == (tail + 1) % items.length;
    }

    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 队列元素数
     *
     * @return 队列元素数
     */
    public int size() {
        if (tail >= head) {
            return tail - head;
        }else {
            return tail + items.length - head;
        }
    }

}

测试代码如下

public class ArrayQueueTest {

    @Test
    public void main(){

        ArrayQueue<String> queue = new ArrayQueue<>(4);
        Assert.assertTrue("添加A失败",queue.put("A"));
        Assert.assertTrue("添加B失败",queue.put("B"));
        Assert.assertTrue("添加C失败",queue.put("C"));

        Assert.assertTrue("添加D成功",!queue.put("D"));

        //队列已满，并且D元素没有入队成功
        Assert.assertTrue("队列未满",queue.isFull());

        Assert.assertEquals("队列中元素数不为3",3,queue.size());

        //获取头元素但不出队
        Assert.assertEquals("头元素不为A","A",queue.peek());

        Assert.assertEquals("出队A失败","A",queue.poll());
        Assert.assertEquals("出队B失败","B",queue.poll());
        Assert.assertEquals("出队C失败","C",queue.poll());

        //队列为空队
        Assert.assertTrue("队列不为空",queue.isEmpty());
    }

}

以上代码中，声明为4，但是使用的时候只能放入3个元素，采用的是初始化数组时多设置一个位置来解决问题的；也可以通过增加一个变量来记录元素的个数去解决问题，不需要两个标记去确定是队空还是队满，元素也能放满而不用空出一位了。

队列的特点

队列的特点就是先进先出。出队的一头是队头，入队的一头是队尾。当然，队列一般都会规定一个有限的长度，叫做队长。

队列的使用场景

队列在实际开发当中很常用。在一般程序中会将队列作为缓冲器或者解藕使用。

某品牌手机在线秒杀用到的队列

某品牌的手机推出新型号，想要购买就需要上网预约，等到了开抢时间就得赶紧打开网页守着，疯狂刷新页面。疯狂的点击抢购按钮。一般在每次秒杀活动中提供的手机只有几千部。假设有两百万的人抢购，那么从开抢的这一秒，两百万人都开始向服务器发送请求。如果服务器都能直接处理请求，把抢购结果立刻告诉用户，同时为请购成功的用户生成订单，让用户付款购买手机，则这对服务器的要求很高，很难实现。可以采用排队的方式解决。把这些请求按顺序放入队列的队尾中，然后提示用户“正在排队中......”，接下来用户开始排队：而且这个对列的另一端，也就是队头会有一些服务器去处理，根据先后顺序告知用户抢购结果。

这就出现了抢购手机时，抢购界面稍后才会告诉我们抢购结果的情况。

这种方式也叫做异步处理。异步与同步是相对的。同步是在一个调用执行完成之后，等待调用结束返回；而异步不会立刻返回结果，返回结果的时间是不可预料的，在另一端的服务器处理完之后才会有结果，如何通知执行的结果又是另一回事。

生产者和消费者模式

这个模式就像有一个传送带，生产者在传送带这头将生产的货物放上去，消费者在另一头逐个地将货物从传送带上取下来。这种设计设计模式的原理也比较简单，即存在一个队列，若干个生产者同时向队列中添加元素，然后若干个消费者从队列中获取元素。

对于生产者和消费者的设计模式来说，有一点非常重要，那就是生产速度要和消费的速度持平。如果生产太快，而消费得太慢，那么队列就会很长。而对于计算机来说，队列太长所占用的空间也会较大。