摘要：實現隊列介紹隊列為特殊的線性表，隊列的特點先進先出，隊列插入為入隊，隊列刪除為出對。實現這次使用順序隊列實現。

Java 實現隊列

隊列為特殊的線性表，隊列的特點先進先出（FIFO），隊列插入為入隊，隊列刪除為出對。

這次使用順序隊列實現。（使用數組），
why？為什么不直接使用順序表作為底層容器，因為入隊操作執行順序表尾插入，時間復雜度為O(1)

O(1) 普通語句，相互操作，時間復雜度為O(1)

出對操作執行表頭刪除操作，時間復雜度為O(n)，因為涉及到一個循環遍歷，移動，由于時間復雜度高，此時直接想方法將時間復雜度降低為O(1) ，即，用雙指針解決。即front和rear兩個解決

時間復雜度 O(n) 涉及一層循環，此時時間復雜度為O(n)

又因為直接更改下標，會導致空間的浪費，（出隊操作）此時，為了減少空間的浪費，將隊列設計為循環隊列，目的，避免假滿現象的出現。

空隊列的時候 front = rear = 0
入隊 front = 0 rear = 1
此時繼續入隊 front = 0 rear = 2
出隊 front = rear = 2 兩者相等
繼續入隊，front=2 rear = 3
不斷的循環，總有一個為空，即rear
到隊滿 即 front = 2 rear = 1；
隊滿的判斷 front = （rear + 1）% size
real永遠為空

package demo.mingm.struct.queue;

/**
 * 接口 隊列
* @author ming
* @date 2018/11/17
*/
public interface Queue {
    // 定義數組長度
    public static final int DEFAULT_SIZE = 10;
    // 返回隊列長度
    int size();
    // 判斷隊列是否為空
    boolean isEmpty();
    // 判斷隊列是否已滿
    boolean isFull();
    // 入隊， 成功true 錯誤false
    boolean add(T data);
    // offer 入隊，和add方法不同的是，如果隊滿，或傳入的為空，將會拋出錯誤，不會自動擴充
    boolean offer(T data);
    // 返回隊頭元素，不執行刪除操作，為空 返回null
    T peek();
    // 返回隊頭元素，如果為空，將會拋出異常
    T element();
    // 出隊，執行刪除操作，若為空，返回null
    T poll();
    // 出隊，執行刪除操作，若為空，拋出異常
    T remove();
    // 清空隊列
    void cleameQueue();
    
}

package demo.mingm.struct.queue;
import java.util.Arrays;
import java.util.Vector;
public class SeqQueue implements Queue {
    private T[] elementData;    // 儲存數據的數組
    private int size;    // 儲存大小
    private int front, rear;    // 指針指向數組的元素，一個前，一個后
    private int real;
    
    public SeqQueue() {
        elementData= (T[]) new Object[DEFAULT_SIZE];
        // 指針的初始化
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    public SeqQueue(int length) {
        elementData = (T[]) new Object[length];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    public int getSize() {
        return this.size;
    }
    
    public int getFront() {
        return this.front;
    }
    
    public int getRear() {
        return this.rear;
    }
    
    public void setSize(int size) {
        this.size = size;
    }
    
    public void setFront(int front) {
        this.front = front;
    }
    
    public void setRear(int rear) {
        this.rear = rear;
    }
    
    // 獲取隊列長度
    @Override
    public int size() {
        return this.getSize();
    }

    // 判斷隊列是否為空
    @Override
    public boolean isEmpty() {
        return this.getRear() == this.getFront();
    }
    
    // 判斷隊列是否已滿
    @Override
    public boolean isFull() {
        return this.getFront() == (this.getRear() + 1) % this.elementData.length;
    }
    
    // 入隊操作，如果不滿，自動擴充數組
    @Override
    public boolean add(T data) {
        if(this.isFull()) {
            Arrays.copyOf(elementData, elementData.length*2);
        }
        // 是否插入空
        if(data == null)
            return false;
        // 添加data
        elementData[this.getRear()] = data;
        // 移動指針
        this.rear++;    // 創造單向隊列
        this.size++;
        return true;
    }

    @Override
    public boolean offer(T data) {
        if(this.isFull() || data == null) {
            throw new NullPointerException("error 1");
        }
        // 添加data
        this.elementData[this.getRear()] = data;
        // 移動指針
        this.real = (this.real + 1)%elementData.length;    // 創造循環隊列
        this.size++;
        return true;
    }

    // 返回隊頭元素，不刪除
    @Override
    public T peek() {
        if(this.isEmpty())
            return null;
        return this.elementData[this.getFront()];
    }

    // 返回隊頭元素
    @Override
    public T element() {
        if(this.isEmpty())
            throw  new NullPointerException("error 2");
        return this.elementData[this.getFront()];
    }

    // 出隊
    @Override
    public T poll() {
        if (this.isEmpty())
            return null;
        T tmp = this.peek();
        // 循環隊列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

    // 出隊
    @Override
    public T remove() {
        if (this.isEmpty())
            throw  new NullPointerException("error 3");
        T tmp = this.peek();
        // 循環隊列
        this.front = (this.getFront() + 1 ) % this.elementData.length;
        return tmp;
    }

    // 清空
    @Override
    public void cleameQueue() {
        this.real = 0;
        this.front = 0;
    }
}