队列Queue

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

• 队列是一种线性结构
• 相比数组，队列相应的操作是数组的子集
• 只能从队尾添加元素，只能从队首取出元素

下述队列是以动态数组为底层实现
动态数组动态数组及均摊复杂度与防止复杂度震荡

//动态数组
public class Arr<E> {private E[] data;// 创建一个数组private int size;// 数组中元素个数// 自定义构造器初始化数组 capacity数组的长度public Arr(int capacity) {// TODO Auto-generated constructor stubdata = (E[]) new Object[capacity];size = 0;}// 默认构造方法 capacity数组的长度=10public Arr() {// TODO Auto-generated constructor stubthis(10);}// 获取数组个数public int getSize() {return size;}// 获取数组长度public int getCapacity() {return data.length;}// 判断数组是否为空public boolean isEmpty() {return size == 0;}// 数组中添加元素 index是插入元素的位置，e是插入的元素，时间复杂度为O(n)public void add(int index, E e) {if (index < 0 || index > size) {try {throw new Exception("数组排列要求不能有空");} catch (Exception e1) {// TODO Auto-generated catch blocke1.printStackTrace();}}// 数组扩容if (size == data.length) {try {resize(2 * data.length); // 这里是扩容为原数组的2倍，Arraylist是扩容1.5倍} catch (Exception e1) {// TODO Auto-generated catch blocke1.printStackTrace();}}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;}// 数组扩容或者缩容,时间复杂度为O(n)private void resize(int newcapcatity) {// TODO Auto-generated method stubE[] newData = (E[]) new Object[newcapcatity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;}// 在数组末尾添加元素,时间复杂度为O(1)public void addLast(E e) {add(size, e);}// 在数组首部添加元素,时间复杂度为O(n)public void addFirst(E e) {add(0, e);}// 重写toString 使用字符串拼接@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append(String.format("Array:size = %d, capacity = %d\n", size, data.length));res.append('[');for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(',');}}res.append(']');return res.toString();}//获取最后一个元素public E getLast() {return get(size - 1);}//获取第一个元素public E getFirst() {return get(0);}// 获取index位置的数组元素,时间复杂度为O(1)E get(int index) {if (index < 0 || index >= size) {try {throw new Exception("index非法");} catch (Exception e) {// TODO Auto-generated catch blocke.printStackTrace();}}return data[index];}// 修改数组元素,时间复杂度为O(1)void set(int index, E e) {if (index < 0 || index >= size) {try {throw new Exception("index非法");} catch (Exception e3) {// TODO Auto-generated catch blocke3.printStackTrace();}}data[index] = e;}// 查询是否包含数组元素e,时间复杂度为O(n)public boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e))return true;}return false;}// 查找数组元素e,时间复杂度为O(n)public int find(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e))return i;// 返回元素e的位置}return -1;// 找不到元素e，返回-1}// 删除指定位置index的数组元素,时间复杂度为O(n)public E remove(int index) {if (index < 0 || index >= size) {try {throw new Exception("index非法");} catch (Exception e3) {// TODO Auto-generated catch blocke3.printStackTrace();}}// 缩容if (size == data.length / 2) {resize(data.length / 2);}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;data[size] = null;return ret;// 返回删除的元素}// 数组删除首个元素,时间复杂度为O(n)public E removeFirst() {return remove(0);}// 数组删除最后一个元素,时间复杂度为O(1)public E removeLast() {return remove(size - 1);}// 数组删除元素e,时间复杂度为O(n)public void removeElement(E e) {int index = find(e);if (index != -1) {remove(index);} else {System.out.println("数组中没有元素e");}}
}

对列接口Queue

public interface Queue<E> {void enqueue(E e);//入队E dequeue();//出队E getFront();//获取队首元素int getSize();//获取队列中元素个数boolean isEmpty();//判断队列是否为空
}

队列ArrayQueue

public class ArrayQueue<E> implements Queue<E>  {private Arr<E> array;public ArrayQueue(int capacity) {// TODO Auto-generated constructor stubarray = new Arr<>(capacity);}public ArrayQueue() {// TODO Auto-generated constructor stubarray = new Arr<>();}@Overridepublic void enqueue(E e) {// TODO Auto-generated method stubarray.addLast(e);}@Overridepublic E dequeue() {// TODO Auto-generated method stubreturn array.removeFirst();}@Overridepublic E getFront() {// TODO Auto-generated method stubreturn array.getFirst();}@Overridepublic int getSize() {// TODO Auto-generated method stubreturn array.getSize();}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn array.isEmpty();}public int getCapacity() {return array.getCapacity();}public String toString() {StringBuilder res = new StringBuilder();res.append("Queue：");res.append("front [");for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));if(i != array.getSize()-1)res.append(",");}res.append("] tail");return res.toString();}
}

测试

public class Test02 {public static void main(String[] args) {ArrayQueue<Integer> queue = new ArrayQueue<>();for (int i = 0; i < 5; i++) {queue.enqueue(i);System.out.println(queue);}queue.dequeue();System.out.println(queue);System.out.println("队首元素为："+queue.getFront());}
}

测试结果

数组对列复杂度分析

• void enqueue(E) 均摊复杂度O(1)
  -E dequeue() 均摊复杂度O(n)
• E front() 复杂度O(1)
• int getSize() 复杂度O(1)
• boolean isEmpty() 复杂度O(1)