Java-队列

　　队列(Queue)是一种先进先出(First In First Out,FIFO)的线性表。它只允许在表的一端插入元素，而在表的另一端删除元素。

　　在队列中，允许插入元素的一端称为队尾(rear),允许删除元素的一端称为队头(front)。

　　

 1.顺序队列

　　队列的顺序存储结构称为顺序队列。它是利用一组地址连续的存储单元存放队列中的元素。由于队列中的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队首元素和队尾元素。

　　设顺序队列Q的容量为6，其队头指针为front,队尾指针为rear，

 队首固定，每次出队剩余元素向下移动

package com.example.data;

/**
 * 顺序队列
 */
public class ArrayQueue {
    private Object[] elementData;
    /**
     * 设置队列容量为6
     */
    private int capacity = 6;
    /**
     * 队尾
     */
    private int rear = 0;
    /**
     * 队头
     */
    private int front = 0;

    public ArrayQueue() {
        this.elementData = new Object[capacity];
    }

    /**
     * 入队 ，当front = 0 ，rear = 容量 - 1 时，再有元素入队发生溢出--真溢出
     */
    public void push(Object data) {
        if (rear > (capacity - 1)) {
//            throw new RuntimeException("超过最大容量 " + capacity + ",当前rear = " + rear);
            System.out.println("超出最大容量 " + capacity + ",数据丢失 " + data);
            return;
        }
        elementData[rear++] = data;
    }

    /**
     * 出队  当front != 0 ，rear = 容量 - 1 时，再有元素入队发生溢出--假溢出
     *  解决办法，队首固定，front永远为0,出队时修改剩余元素向下移动
     */
    public Object pop() {
        // 队列为空
        if (rear == 0 && front == 0) {
            return null;
        }
        Object relust = elementData[front];
        Object[] elementDataNew = new Object[capacity];
        System.arraycopy(elementData,1,elementDataNew,0,rear-front-1);
        elementData = elementDataNew;
        rear--;
        return relust;
    }
}

2.循环队列

　　在顺序队列的基础上，将数组的最后一个元素的下一个元素逻辑上人为是数组的第一个元素，这样就形成了逻辑上的环。

　　入队操作： rear = （rear +1）% M ;  sq[rear] = x ;

　　出队操作：front = (front+1) % M ;  x = sq[front] ;

　　循环队列会牺牲一个元素空间，约定以“队列的尾指针所指位置的下一个位置是队头指针”表示队满，而队头、尾指针的值相同时表示队列为空

　　队空条件 ：front == rear

　　队满条件：（rear+1）%M = front

/**
     * 入队   (rear + 1) % capacity == front 满队列
     */
    public void push(Object data) {
        if ((rear + 1) % capacity == front) {
            return;
        }
        rear = (rear+1) % capacity;
        elementData[rear] = data;
    }

    /**
     * 出队  fornt==rear 空队列
     */
    public Object pop() {
        // 队列为空
        if (rear == front) {
            return null;
        }
        front = (front+1)%capacity;
        Object relust = elementData[front];
        return relust;
    }