网站编辑器介绍,平面设计师赚钱吗,网站设置在设备之间共享怎么开启,妇科医院网站建设怎么做一、基本概念
队列是一种线性数据结构
二、特点 队列是先进先出(FIFO---First In First Out)(买饭排队:先排队的先买饭,买完饭就退出队列,准备买饭从队尾进入队列排队) 规定只能从一端(队尾)添加元素,从另一端(队首)取出元素
三、基本操作 定义一个接口,里面实…一、基本概念
队列是一种线性数据结构
二、特点 队列是先进先出(FIFO---First In First Out)(买饭排队:先排队的先买饭,买完饭就退出队列,准备买饭从队尾进入队列排队) 规定只能从一端(队尾)添加元素,从另一端(队首)取出元素
三、基本操作 定义一个接口,里面实现队列的相关操作 public interface Queue_1T {// 入队void offer(T ele);// 出队T pool();// 查看队首元素T peek();// 队列中元素的个数int getSize();// 队列是否为空boolean isEmpty();
} 以数组作为队列的底层数据结构 public class ArrQueueT implements Queue_1T {}创建全局变量 // 队列的容器
private MyArrayT data; 重载构造方法 public ArrQueue() {this.data new MyArray(50);
} 入队操作 Override
public void offer(T ele) {this.data.add(ele);// 将元素添加到队尾
} 出队操作 Override
public T pool() {if (isEmpty()) {return null;}return this.data.removeByIndex(0);// 将第一个元素返回
} 获取队首的元素 Override
public T peek() {if (isEmpty()) {return null;}return this.data.getValueByIndex(0);// 获取队首的元素
} 获取队列中实际存放元素的个数 Override
public int getSize() {return this.data.getSize();// 获取队列中实际存放元素的个数
} 判断队列是否为空 Override
public boolean isEmpty() {return this.data.isEmpty();
}
四、循环队列
1.创建一个以数组为底层的循环队列类
public class LoopArrT {}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.tailthis.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 LoopQueueT implements Queue_1T {private LoopArrT 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.创建队列
// 普通队列
QueueInteger queue new LinkedList();// 双端队列 linkedList
LinkedListInteger 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();
}
