一、基本概念

队列是一种线性数据结构

二、特点

1. 队列是"先进先出(FIFO---First In First Out)"(买饭排队:先排队的先买饭,买完饭就退出队列,准备买饭从队尾进入队列排队)

2. 规定只能从一端(队尾)添加元素,从另一端(队首)取出元素

三、基本操作

1. 定义一个接口,里面实现队列的相关操作

   public interface Queue_1<T> {//  入队void offer(T ele);//  出队T pool();//  查看队首元素T peek();//  队列中元素的个数int getSize();//  队列是否为空boolean isEmpty();
   }

2. 以数组作为队列的底层数据结构

   public class ArrQueue<T> implements Queue_1<T> {}
   

3. 创建全局变量

   //  队列的容器
   private MyArray<T> data;

4. 重载构造方法

   public ArrQueue() {this.data = new MyArray<>(50);
   }

5. 入队操作

   @Override
   public void offer(T ele) {this.data.add(ele);//  将元素添加到队尾
   }

6. 出队操作

   @Override
   public T pool() {if (isEmpty()) {return null;}return this.data.removeByIndex(0);//  将第一个元素返回
   }

7. 获取队首的元素

   @Override
   public T peek() {if (isEmpty()) {return null;}return this.data.getValueByIndex(0);//  获取队首的元素
   }

8. 获取队列中实际存放元素的个数

   @Override
   public int getSize() {return this.data.getSize();//  获取队列中实际存放元素的个数
   }

9. 判断队列是否为空

   @Override
   public boolean isEmpty() {return this.data.isEmpty();
   }

四、循环队列

1.创建一个以数组为底层的循环队列类

public class LoopArr<T> {}

2.定义全局变量

private T[] data;//  创建一个泛型数组 保存数据data
private int size;//  创建一个变量 数组中实际存放元素的个数size
private int front;//  指向队首
private int tail;//  指向队尾
private int capacity;//  创建一个变量 容积capacity

 3.构造函数

public LoopArr(int capacity) {//  判断容量,传入容量小于0if (capacity < 0) {//  将队列容量初始化为11this.capacity = 11;} else {//  将队列容量增加1个,可使队列判断队满及队空更加方便this.capacity = capacity + 1;}this.size = 0;//  初始化队列中实际存放元素个数this.front = this.tail = 0;//  初始化队列,将队头与队尾都置为0this.data = (T[]) (new Object[this.capacity + 1]);//  为泛型数组赋值
}

 4.向数组中添加元素

public void add(T item) {//判断数组是否满if ((this.tail + 1) % capacity == this.front) {// 扩容   resize  容积扩一倍resize((this.capacity - 1) * 2 + 1);}//  向指定位置添加元素this.data[this.tail] = item;this.tail = (this.tail + 1) % this.capacity;//更新this.sizethis.size++;
}

5.扩容

private void resize(int newCapacity) {System.out.println("resize:" + newCapacity);//  打印数组的新容量//  改变容量与容积this.data = Arrays.copyOf(data, newCapacity);this.capacity = newCapacity;//  将this.front置为零,this.tail=this.sizethis.front = 0;this.tail = this.size;
}

 6.移除队首元素

public T remove() {if (isEmpty()) {return null;}T delValue = this.data[this.front];//  获取要删除索引的值//  删除完之后,this.front向后移动this.front = (this.front + 1) % capacity;//  更新数组索引this.size--;//  判断是否缩容if (this.size < this.capacity / 4 && this.capacity / 2 > 0) {resize((this.capacity - 1) / 2 + 1);}return delValue;//  返回删除的值
}

7.创建循环队列

public class LoopQueue<T> implements Queue_1<T> {private LoopArr<T> data;//  容器public LoopQueue() {this.data = new LoopArr<>(100);}//  向循环队列中从队尾添加元素@Overridepublic void offer(T ele) {this.data.add(ele);}//  将队头元素从循环队列中移出@Overridepublic T pool() {return this.data.remove();}//  获取队头元素@Overridepublic T peek() {return this.data.getFirstVal();}//  获得循环队列的长度@Overridepublic int getSize() {return this.data.getSize();}//  判断循环队列是否为空@Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}

五、双端队列

1.创建双端队列类

public class Dique {}

2.创建队列

//  普通队列
Queue<Integer> queue = new LinkedList<>();//  双端队列  linkedList
LinkedList<Integer> help = new LinkedList<>();

3.添加操作

public void offer(int ele) {this.queue.add(ele);//  判断双端队列中(从尾部开始比ele小的元素都要出队)while (!this.help.isEmpty() && this.help.peekFirst() < ele) {this.help.pollLast();//  LinkedList中特有的方法,将最后一个元素检索并删除}this.help.offerLast(ele);//  将元素从尾部添加
}

4.删除操作

public Integer remove() {//  队列为空,返回nullif (this.queue.isEmpty()) {return null;}//  队头与双端队列队头相同,双端环队列队头删除if (this.queue.peek() == this.help.peekFirst()) {this.help.pollFirst();}//  并将普通队列队头删除return this.queue.poll();
}