【Java -- 数据结构】什么是队列(Queue)？

前言

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。先进先出，简单暴力的理解就是吃进去拉出来

优点:

• 提供了先进先出的存取方式

缺点:

• 存取其他项很慢

队列有两个最基本的操作，入队enqueue(),放一个数据到队列的尾部；出队dequeue()，从队列头部取出一个元素。

顺序队列和链式队列

队列可以使用数组来实现也可以使用链表来实现，用数组实队列的栈叫做顺序队列，用链表实现的队列叫做链式队列。

使用数组来实现一个队列：

public class ArrayQueue {
    private String[] items;
    private int n = 0;//总大小
    private int head = 0;
    private int tail = 0;

    //申请一个大小为n的数组
    public ArrayQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //如果队列满了返回false
        if(tail == n) return false;
        items[tail] = item;
        ++tail;
        return true;
    }

    //出队
    public String dequeue(){
        //head == tail 表示队列为空
        if(head == tail) return  null;
        String res = items[head];
        ++head;
        return res;
    }

}

队列需要两个指针，一个指向队头，一个指向队尾。

当a、b、c、d一次进入队列之后，队列中的head指针指向下标为0的位置，tail下标为4的位置 当我们调用两次出队操作的之后，队列中的head指针指向下标为2的位置，tail指针位置不变。

随着不停的入队和出队操作，head和tail指针会不断的往后移动移动到最右边，即使数组中还有空闲的空间也不能往队列中添加数据了，那怎么办呢？

我们可以使用数据搬移，当然出队的时候不会出现空间不够的情况也就不用搬移，我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想，上面的出队操作不用变，入队操作可以改成下面的：

    public boolean enqueue(String item){
        //tail==n 说明队列满了
        if(tail == n){
            //tail==n&&head==0说明整个队列都是满的
            if(head == 0) return  false;
            //搬移数据
            for (int i = head; i