概述

队列是一种用于存储数据的数据结构（与链表和栈类似）。队列是一种只能在一端插入（队尾），在另一端删除（队头），有一定操作约束的线性表。队列中第一个插入也是第一个被删除的元素。所以，队列是一种先进先出（FIFO）的线性表。

举一个生活中的例子来理解队列的概念，例如排队。新来的人只能入队尾，排队头的人也是最早被服务，然后出队的人。

所以队列对数据操作集有：

• void addQ( item )：新元素 item 从队尾入队
• int deleteQ()：队头数据元素出队
• boolean isFull()：判断队列 Q 是否已满
• boolean isEmptyQ()：判断队列 Q 是否为空

实现

队列抽象数据类型（与栈类似）有多种实现方式。下面是常用的方法。

• 基于循环数组的实现方法。
• 基于链表的实现方法。

1）基于循环数组实现

队列通常由一个一维数组和一个记录队列头元素位置的变量 front 以及一个记录队列尾元素位置的变量 rear 组成。front 与 rear 初始设为 -1 ，进行 AddQ 入队操作时 rear 加1，进行 deleteQ 出队操作时 front 加1。

通过上图我们发现两个问题，其一是 front 总会在队头位置再前一个位置，如上队头位置是下标 2，而 front 在下标 1。其二是数组并未插满，而是有空位，除去 front 占位 1，0 这个位置其实属于空位，所以我们希望是再 AddQ 入队的时候，数组能循环回来插入 0 这个位置，才算将数组插满，不浪费空间。

这就是为什么我们要用循环数组，再来看一张循环数组的图。

上图所示就是循环数组的队列的应用，与之前方式不同点在于：rear 与 front 初始值为 0，不是 -1，例如插入 AddJob1，rear 递增为 1，所以插入数组下标 1 位置...，以此类推；仅使用 n-1 个数组空间可以认为已经插满，为何要留出 1 个空间呢，因为队列为空时 rear 与 front 相等，当队列插满时，若再让 rear 与 front 相等，则会无法区别队列是空还是满了。所以队列空时是 rear 与 front 相等，队列满时则是如上图状态。

那么循环数组是怎么现实的，如上图下标 5 下一个怎么到下标 0 呢，用求余方式 %，(5+1) % 6 = 0 ，6 指数组长度。

public class ArrayQueue {
    private int front;
    private int rear;
    private int[] array;
    private int maxsize;  /*数组长度*/

    private ArrayQueue(int size) {
        front = 0;
        rear = 0;
        maxsize = size;
        array = new int[size];
    }

    // 队尾入队 rear
    public void AddQ(int item) {
        if( isFull() ) {  
            System.out.println("队列满");
            return;
        }

        rear = (rear+1)%maxsize;
        array[rear] = item;
    }

    // 队头出队 front
    public int deleteQ() {
        if( isEmpty() ) {  
            System.out.println("队列空");
            throw new EmptyStackException();
        }else {
            front = (front+1)%maxsize;
            return array[front];
        }
    }

    public boolean isFull() {
        return (rear+1)%maxsize == front;
    }

    public boolean isEmpty(){
        return front == rear;
    }

    public static void main(String[] args) {

        ArrayQueue queque = new ArrayQueue(5);

        queque.AddQ(10);
        queque.AddQ(20);
        queque.AddQ(50);
        queque.AddQ(1);

        // 长度5，入队  4  个元素则满了    
        queque.AddQ(7);    /*输出：队列满*/

    }
}

2）基于链表实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行：定义 front 指向链表头部，进行出队删除操作；定义 rear 指向链表尾部，进行入队插入操作。

代码：

public class ListQueue {
    private MyListNode front;
    private MyListNode rear;
    private ListQueue(){
        this.front = null;
        this.rear = null;
    }
    public void addQ(int data){
        MyListNode newNode = new MyListNode(data);
        if(rear != null){
            rear.setNext(newNode);
        }    
        rear = newNode;
        if(front == null){    // front 为空时，初始化
            front = rear;   
        }
    }

    public int deleteQ(){
        int data;
        if(isEmpty()){
            throw new EmptyStackException();
        }
        if(front == rear){    /*若队列只有一个元素*/
            front = rear = null;     /*删除后队列置为空*/
        }else{
            front = front.getNext();
        }
        data = front.getData();
        return data;
    }

    public boolean isEmpty(){
        return (front == null);
    }

    public static void main(String[] args) {
        ListQueue queue = new ListQueue();
        queue.addQ(1);
        queue.addQ(3);
        queue.addQ(5);
        queue.addQ(6);
        System.out.println(queue.deleteQ());  // 输出：1
    }
}