在网站上做封面,龙岗网站制作资讯,购物国外网站的建立,商家免费网站模板生活如果真能像队列一样#xff0c;那该多好啊。 ——————————————————————————————————————————
背包#xff0c;队列
可以先看他们的API#xff1a;都含有一个无参构造函数#xff0c;添加单个元素的方法#xff0c;测试集合…生活如果真能像队列一样那该多好啊。 ——————————————————————————————————————————
背包队列
可以先看他们的API都含有一个无参构造函数添加单个元素的方法测试集合是否为空的方法和返回集合大小的方法。而Stack和Queue有能删除集合的特定元素的方法。
它们具有泛型和迭代的特性。
泛型的使用可以用它们存储任意类型的数据。 如Stack 用Item替换任意数据类型
StackString stack new StackString();而类型参数必须被实例化为引用类型。而java具有自动装箱和自动拆箱的机制可以在引用类型和对应的原始数据类型之间转换。
StackInteger stack new StackInteger();
stack.push(17); //自动装箱 int 转换为 Integer
int i stack.pop(); //自动拆箱 Integer 转换为 int如果集合可迭代可以使用如foreach循环来逐个访问集合中的元素无需手动管理索引或遍历位置这样可以简化代码实现。
QueueString queue new LinkedList();
// 使用 foreach 循环来遍历 Queue
for (String element : queue) {System.out.println(element);
}背包
特点
不支持删除元素和遍历操作收集元素并迭代遍历所有收集到的元素迭代的顺序不确定无序且与用例无关主要用于统计计算去重求平均值或者样本标准差之类的场景
就理解成一个背包即可里面各种球一次放进去一个球或者一次从里面找自己想要的具有某种特点的球。
BagDouble numbers new BagDouble();
while (!StdIn.isEpty()) numbers.add(StdIn.readDouble());
int N number.size(); // 背包的元素数量double sum 0.0
for (double x : number)sum x;
double mean sum/N;sum 0.0;
for(double x : number)sum (x - mean)*(x- mean);
double std Math.sqrt(sum/(N-1));队列queue
先进先出队列是一种基于先进先出FIFO) 策略的集合类型。
使用场景很常见尤其是排队打印机等待打印或者是计算机某些软件等待处理的任务。
因为是服务性的策略所以主打一个公平先到先得等的越久越先服务。
QueueInteger queue new QueueInteger();
// Enqueue 操作 可以通过add()或offer()方法实现
queue.add(A);
queue.add(B);
queue.offer(C);// dequeue从队列的头部移除并返回一个元素可以使用remove()或poll()方法来实现
String dequeuedElement queue.remove();
System.out.println(Dequeued element: dequeuedElement);队列是一个有序列表可以用数组或是链表来实现。
数组模拟队列思路
队列本身是有序列表若使用数组的结构来存储队列的数据则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。因为队列的输出、输入是分别从前后端来处理因此需要两个变量 front 及 rear 分别记录队列前后端的下标 front 会随着数据输出而改变而 rear 则是随着数据输入而改变如图所示: 准备工作思路 将front和rear初始化为-1 , 为了表示队列为空的状态 (当队列中添加第一个元素时front和rear都会更新为0表示队列中有一个元素) 当 front rear 则代表队列为空 当 rear maxSize - 1 则代表队列为满
class ArrayQueue {
private int maxSize; // 表示数组的最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列// 创建队列的构造器
public ArrayQueue(int arrMaxSize) {maxSize arrMaxSize;arr new int[maxSize];front -1; // 指向队列头部分析出 front 是指向队列头的前一个位置.rear -1; // 指向队列尾指向队列尾的数据(即就是队列最后一个数据)
}// 判断队列是否满 队列尾指向数组的最大索引
public boolean isFull() {return rear maxSize - 1;
}// 判断队列是否为空 初始时两指针都为-1指向同一个位置
public boolean isEmpty() {return rear front;
}
存入数据思路分析
1.添加元素时判断队列是不是满的。若不是则头指针不动用于元素出队列将尾指针后移rear1
2.再将数据存入 rear 所指的数组元素中
// 添加数据到队列
public void addQueue(int n) {
// 判断队列是否满if (isFull()) {System.out.println(队列满不能加入数据~);return;}rear; // 让 rear 后移arr[rear] n;
}出队列获取队列的数据代码
public int getQueue() {
// 判断队列是否空if (isEmpty()) {// 通过抛出异常throw new RuntimeException(队列空不能取数据);}front; // front 后移 满足先进先出原则。return arr[front];
}显示队列中的所有数据 代码
public void showQueue() {// 遍历if (isEmpty()) {System.out.println(队列空的没有数据~~);return;}for (int i 0; i arr.length; i) {System.out.printf(arr[%d]%d\n, i, arr[i]);}
}显示队列的头数据 代码
public int headQueue() {if (isEmpty()) {throw new RuntimeException(队列空的没有数据~~);}return arr[front 1];}
}
对于这个代码所模拟的队列进行问题分析及方案优化
问题目前数组使用一次就不能用没有出队列的功能则没有达到复用的效果。且如果队列尾部的空间已满而队列头部仍有空间此时无法再添加元素优化方案将这个数组使用算法改进成一个环形的队列 通过取模%变成循环的
数组模拟环形队列
对前面的数组模拟队列进行优化实现可以复用。成为是一个环形的循环队列。(通过取模的方式来实现即可)
分析说明 因为是环形结构满了会回头。所以当尾索引的下一个为头索引时表示队列满了。因此将队列容量空出一个作为约定。通过这个约定可以得出 (rear 1) % maxSize front代表队列满了。 rear front 则代表队列为空 当你定义了1个长度为5的队列已经有了4个元素。这个时候头指针指着第一个数字尾指针值向 具体思路如下: 将front指向队列的第一个元素即front0 将rear指向队列最后一个元素的后一个位置即rear0。这里需要注意rear指向的位置实际上是不存储数据的只是为了区分队列空和满的情况因此需要浪费一个位置 这里比如当你定义了1个长度为5的队列已经有了4个元素。这个时候头指针指着第一个元素尾指针值向第4个元素后面的位置。这时候你再加一个元素的话那尾指针就指回了第一个位置这样子就出现了rear front。那你就没办法确定到底是队列满了还是队列空了。因此采用(rear 1) % maxSize front就表示队列满了此时rear指向的位置实际上是不存储数据的。在网上找到的其他思路新增一个容量 capacity 字段并进行维护当 capacitysize 表示队列已满。维护一个标记或者当 头指针尾指针 时同步判断当前位置是否有元素来判断当前是队空还是队满。现在使用的方法会浪费一个空间而新增容量字段需要维护而标记的方法队列空和队列满的时候需要判断是那种情况影响性能。一般使用浪费一个空间的方法用空间换时间。在判断队列是否满时尾指针的下一个位置会等于头指针的位置。所以使用**(rear 1) % maxSize front**条件当rear和front相邻且都指向有数据的位置时队列为满。 public boolean isFull() {return (rear 1) % maxSize front;
} 在判断队列是否为空时使用rear front的条件当队列中没有元素时front和rear都指向同一个位置。 public boolean isEmpty() {return rear front;
}计算队列中有效数据元素的个数时使用**(rear maxSize - front) % maxSize**的公式由于队列是循环的所以队列的尾部可能在数组的起始位置之前。 计算出队列尾指针rear到队列头指针front的距离并进行模运算得到实际的元素个数。
添加数据到队列
public void addQueue(int n) {// 判断队列是否满if (isFull()) {System.out.println(队列满不能加入数据~);return;}//直接将数据加入arr[rear] n;//将 rear 后移, 这里必须考虑取模rear (rear 1) % maxSize;
}获取队列的数据, 出队列
public int getQueue() {// 判断队列是否空if (isEmpty()) {// 通过抛出异常throw new RuntimeException(队列空不能取数据);}// 这里需要分析出 front 是指向队列的第一个元素// 1. 先把 front 对应的值保留到一个临时变量// 2. 然后将 front 后移, 考虑取模// 3. 将临时保存的变量返回int value arr[front];front (front 1) % maxSize; return value;
}显示队列的所有数据
public void showQueue() {// 遍历if (isEmpty()) {System.out.println(队列空的没有数据~~);return;}for (int i front; i front size() ; i) {// 使用 i % maxSize 的目的是确保索引值在循环队列的有效范围内
//假设队列的最大大小为 5且队列起始位置front是2不取模的话那就超出了队列范围应该回到队列的开头则需要取模。System.out.printf(arr[%d]%d\n, i % maxSize, arr[i % maxSize])}
}// 求出当前队列有效数据的个数
public int size() {// rear 2// front 1// maxSize 3return (rear maxSize - front) % maxSize;
}显示队列的头数据
public int headQueue() {// 判断if (isEmpty()) {throw new RuntimeException(队列空的没有数据~~);}return arr[front];}
}
———————————————————————————————————— 那这样子是不是就有机会了
