Java数据结构与算法[原创]——队列

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。队列和栈类似，也是一个遵循特殊规则约束的数据结构。将没有元素的队列称之为空队，往队列中插入元素的过程称之为入队，从队列中移除元素的过程称之为出队。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的队列（queue）的概念、存储结构、队列的特点，文末给出java实现循环队列的代码实现供读者参考学习。

队列正如其名，队列就像一支队伍，有队首(head)和队尾(tail)以及队列长度。队列和栈类似，也是一个遵循特殊规则约束的数据结构。在上一篇文章java数据结构与算法——栈中介绍栈是一个后进先出（LIFO）的数据结构，队列正好与之相反，是一个先进先出（FIFO，First In First Out），例如我们去肯德基排队，先排上队的肯定先拿到餐出队，这和我们对列认知是一致的。

上面说到队列是一个遵循特殊规则的数据结构，除了先进先出，队列的插入只能从队列的一端操作，我们称这端为队尾；对应的，移除只能从另一端出来，我们称之为队首。

将没有元素的队列称之为空队，往队列中插入元素的过程称之为入队，从队列中移除元素的过程称之为出队。

一般而言，队列的实现有两种方式：数组实现和链表实现，本篇中采取数组实现，链表实现在后续补充。用数组实现的队列有两种：一种是顺序队列，另一种是循环队列，这两种队列的存储结构和特点下文会逐一介绍。

说明：用数组实现队列，若队列中出现队满的情况（因为在声明队列时，一般会指定一个初始容量），此时如果有新元素入队，但没有位置怎么办？要么丢弃，要么等待。

以下采用数组实现，初始化一个队列长度为6，队列有两个标记，一个队头的位置head，一个队尾的位置tail，初始都指向数组下标为0的位置，如图所示：

在插入元素时，tail标记+1，比如入队三个元素，依次为A，B，C（注意是有顺序的），则当前队列存储情况如图：
当前head为0，tail为3，接下来进行出队操作，此处将A元素出队，则head+1，此时队列的存储情况如图：

根据上面的图例，我们可以通过tail-head获得队列中元素的个数。当tail==head时，此时队列为空，而当tail等于数组长度时，此时将无法出入元素，那么队列是否已经满呢？未必！因为head和tail在入队和出队操作中只增不减，因此head和tail都会最终指向队列之外的存储位置，此时虽然数组为空，但也无法将元素入队。

上溢： 当队列中无法插入元素时，称之为上溢；
假上溢： 在顺序队列中，数组还有空间（不一定全空）但无法入队称之为假上溢；
真上溢： 如果head为0，tail指向数组之外，即数组真满了，称之为真上溢；
下溢： 如果空队中执行出队操作，此时队列中无元素，称之为下溢

如何解决“假上溢”的问题呢？此时引入循环队列。出现假上溢时，此时数组还有空闲的位置，将tail从新指向数组的0索引处即可，如图所示：

如果继续入队E和F，则队列的存储结构如图：
通常而言，在对head和tail加1时，为了方便采用对数组长度取余操作。另外由于顺序队列存在“假上溢”的现象，所以一般用循环队列实现。

在采用循环队列实现的过程中，当队列满队时，tail等于head，而当队列空时，tail也等于head，为了区分两种状态，一般规定循环队列的长度为数组长度-1，即有一个位置不放元素，此时head==tail时为空队，而当head==(tail+1)%数组长度，说明对满。

下面是循环队列的java代码，采用数组方式实现：

public class ArrayQueue {
    private final Object[] queue;  //声明一个数组
    private int head;
    private int tail;
    
    /**
     * 初始化队列
     * @param capacity 队列长度
     */
    public ArrayQueue(int capacity){
        this.queue = new Object[capacity];
    }
    
    /**
     * 入队
     * @param o 入队元素
     * @return 入队成功与否
     */
    public boolean put(Object o){
        if(head == (tail+1)%queue.length){
            //说明队满
            return false;
        }
        queue[tail] = o;
        tail = (tail+1)%queue.length;  //tail标记后移一位
        return true;
    }
    
    /**
     * 返回队首元素，但不出队
     * @return
     */
    public Object peak() {
        if(head==tail){
            //队空
            return null;
        }
        return queue[head];        
    }
    
    /**
     * 出队
     * @return 出队元素
     */
    public Object pull(){
        if(head==tail){
            return null;
        }
        Object item = queue[head];
        queue[head] = null;
        return item;
    }
    
    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){
        return head == tail;
    }
    
    /**
     * 判断是否为满
     * @return
     */
    public boolean isFull(){
        return head == (tail+1)%queue.length;
    }
    
    /**
     * 获取队列中的元素个数
     * @return
     */
    public int getsize(){
        if(tail>=head){
            return tail-head;
        }else{
            return (tail+queue.length)-head;
        }
    }    
}

下面是队列的测试代码

public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue q = new ArrayQueue(4);  //初始化队列长度为3，因为循环队列有一个不放元素
        System.out.println(q.put("张三"));  //入队，true
        System.out.println(q.put("李四"));  //入队，true 
        System.out.println(q.put("赵五"));  //入队，true
        System.out.println(q.put("老王"));  //队满，false
        
        System.out.println(q.isFull());  //队满 true
        System.out.println(q.getsize()); //3，队列中有3个元素
        
        System.out.println(q.peak());  //返回“张三”  不出队
        System.out.println(q.pull());  //返回“张三”  
        System.out.println(q.pull());  //返回“李四”  
        System.out.println(q.pull());  //返回“赵五”  
        
        System.out.println(q.isEmpty());  //true 空队
    }
}

队列先入先出的特点，使得其应用非常广泛，比如队列作为“缓冲区”，可以解决计算机和外设速度不匹配的问题，FIFO的特点保证了数据传输的顺序；除此之外队列在后面树的层序遍历中也有应用，FIFO的特点保证了处理顺序不会出错。