一.簡介：

1.隊(duì)列也是一種線性結(jié)構(gòu)。

2.相比數(shù)組，隊(duì)列對應(yīng)的操作是數(shù)組的子集。

3.只能從一端（隊(duì)尾）添加元素，只能從另一端（對首）取出元素。

也就是說隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO First In First Out）

二.隊(duì)列的數(shù)組實(shí)現(xiàn)：

package data_structure.arrays;

public class MyArray<T> {

  private T[] data;
  private int size;

  @SuppressWarnings("unchecked")
  public MyArray(int capacity) {
    this.data = (T[]) new Object[capacity];
    this.size = 0;
  }

  /**
   * 無參構(gòu)造函數(shù)初始容量10
   */
  @SuppressWarnings("unchecked")
  public MyArray() {
    this(10);
  }

  /**
   * 獲取元素個(gè)數(shù)
   */
  public int getSize() {
    return size;
  }

  /**
   * 獲取第一個(gè)元素
   */
  public T getFirst() {
    return get(0);
  }

  /**
   * 獲取最后一個(gè)元素
   */
  public T getLast() {
    return get(size - 1);
  }

  /**
   * 獲取數(shù)組容量
   */
  public int getCapacity() {
    return data.length;
  }

  /**
   * 數(shù)組是否是空的
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * 在index 索引位置添加一個(gè)元素t O(n/2)=O(n)時(shí)間復(fù)雜度
   */
  public void add(int index, T t) {

    if (index < 0 || index > size) {
      throw new IllegalArgumentException("Add fail,Require index >=0 and index <=size");
    }
    if (size == data.length) {
      resizeArray(2 * data.length);
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = t;
    size++;

  }

  /**
   * 在數(shù)組開始位置添加一個(gè)元素t O(n)時(shí)間復(fù)雜度
   */
  public void addFirst(T t) {
    add(0, t);
  }

  /**
   * 在當(dāng)前所有元素后添加一個(gè)元素t O(1)均攤復(fù)雜度
   */
  public void addLast(T t) {
    add(size, t);
  }

  /**
   * 獲取index索引位置的元素 0(1)
   */
  public T get(int index) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    return data[index];
  }

  /**
   * 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1 O(n)
   */
  public int find(T t) {
    for (int i = 0; i < size; i++) {
      if (data[i].equals(t)) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 是否包含某個(gè)元素 O(n)
   */
  public boolean contains(T t) {
    return find(t) != -1;
  }

  /**
   * 修改index索引位置的元素 O(1)時(shí)間復(fù)雜度
   */
  public void set(int index, T t) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    data[index] = t;
  }


  /**
   * 刪除index索引的元素，并返回該元素 O(n/2)=O(n)時(shí)間復(fù)雜度
   */
  public T remove(int index) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    T ret = data[index];
    for (int i = index; i < size; i++) {
      data[i] = data[i + 1];
    }
    data[size] = null;
    size--;
    //防止復(fù)雜度震蕩，防止創(chuàng)建0size的數(shù)組
    if (size == data.length / 4 && data.length / 2 != 0) {
      resizeArray(data.length / 2);
    }
    return ret;
  }

  public void removeElement(T t) {
    int i = find(t);
    if (i != -1) {
      remove(i);
    }
  }

  /**
   * 移除所有元素中的第一個(gè)元素 O(n)時(shí)間復(fù)雜度
   */
  public T removeFirst() {
    return remove(0);
  }

  /**
   * 移除所有元素中的最后個(gè)元素 O(1)時(shí)間復(fù)雜度
   */
  public T removeLast() {
    return remove(size - 1);
  }

  @SuppressWarnings("unchecked")
  public T[] resizeArray(int length) {
    T[] newArray = (T[]) new Object[length];
    for (int i = 0; i < size; i++) {
      newArray[i] = data[i];
    }
    data = newArray;
    return newArray;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(String.format("Array : size = %d ,capacity = %d \n", size, data.length));
    builder.append("[");
    for (int i = 0; i < size; i++) {
      builder.append(data[i]);
      if (i != size - 1) {
        builder.append(",");
      }
    }
    builder.append("]");
    return builder.toString();
  }
}

package data_structure.Queue;

import data_structure.arrays.MyArray;

public class ArrayQueue<E> implements Queue<E> {

  MyArray<E> myArray;

  public ArrayQueue(int capacity) {
    this.myArray = new MyArray<>(capacity);
  }

  public ArrayQueue() {
    this.myArray = new MyArray<>();
  }

  /**
   * 添加元素到對尾
   */
  @Override
  public void enqueue(E e) {
    myArray.addLast(e);
  }

  /**
   * 從隊(duì)首取出元素
   */
  @Override
  public E dequeue() {
    return myArray.removeFirst();
  }

  /**
   * 獲取隊(duì)列第一個(gè)元素
   */
  @Override
  public E getFront() {
    return myArray.getFirst();
  }

  /**
   * 獲取隊(duì)列中元素個(gè)數(shù)
   */
  @Override
  public int getSize() {
    return myArray.getSize();
  }

  /**
   * 判斷隊(duì)列是否是空的
   */
  @Override
  public boolean isEmpty() {
    return myArray.isEmpty();
  }

  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Queue: ");
    res.append("front [");
    for (int i = 0; i < myArray.getSize(); i++) {
      res.append(myArray.get(i));
      if (i != myArray.getSize() - 1) {
        res.append(", ");
      }
    }
    res.append("] tail");
    return res.toString();
  }
}