队列
队列的一个使用场景
银行排队的案例:
队列介绍
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
示意图：(使用数组模拟队列示意图)
数组模拟队列
数组模拟队列思路：思路图
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示
新增思路
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
将尾指针往后移：rear+1 , 当 front == rear 【空】
若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
根据队列思路实现数组模拟队列
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.Queue * @className: ArrayQueueDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/16 14:24 * @version: 1.0 */ public class ArrayQueueDemo { public static void main(String[] args) { //创建一个队列 ArrayQueue queue = new ArrayQueue(3); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } /* 根据 数组来实现的队列*/ class ArrayQueue { //队列最大上限 private int MaxSize; //队列尾部 private int rear; //队列头部 private int front; //存放队列数据的数组 private int[] ArrayQueue; /** * @author 冷环渊 Doomwatcher * @context: 初始化构造队列，初始化队列和头尾值向 * @date: 2021/12/16 14:30 * @param maxSize * @return: */ public ArrayQueue(int maxSize) { // 获取最大值 this.MaxSize = maxSize; //初始化 队列 ArrayQueue = new int[MaxSize]; //设置最大最小值 rear = -1; front = -1; } /** * @author 冷环渊 Doomwatcher * @context: 判断是否队列是否达到存储上限 * @date: 2021/12/16 14:30 * @param * @return: boolean */ public boolean isfull() { return rear == MaxSize - 1; } /** * @author 冷环渊 Doomwatcher * @context: 判断队列是否是空的 * @date: 2021/12/16 14:32 * @param * @return: boolean */ public boolean isemity() { return rear == front; } /** * @author 冷环渊 Doomwatcher * @context: 向队列插入一条数据 * @date: 2021/12/16 14:34 * @param value * @return: void */ public void addQueue(int value) { if (isfull()) { System.out.println("队列已满 不能加入更多的数据"); return; } //++ 是后赋值，意思是执行完当前赋值，rear向后移动一位 rear++; ArrayQueue[rear] = value; } /** * @author 冷环渊 Doomwatcher * @context:获取队列的值 * @date: 2021/12/16 14:37 * @param * @return: void */ public int getQueue() { if (isemity()) { throw new RuntimeException("该队列是空的 无法获取到内容"); } front++; return ArrayQueue[front]; } /** * @author 冷环渊 Doomwatcher * @context:遍历队列输出 注意是遍历 不会更改队列的指向 * @date: 2021/12/16 14:42 * @param * @return: void */ public void showQueue() { if (isemity()) { System.out.println("队列没有可以遍历的数值"); } for (int i = 0; i < ArrayQueue.length; i++) { System.out.printf("arrQueue[%d]: %d\n", i, ArrayQueue[i]); } } /** * @author 冷环渊 Doomwatcher * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据 * @date: 2021/12/16 14:45 * @param * @return: void */ public int headQueue() { if (isemity()) { throw new RuntimeException("没有头数据"); } return ArrayQueue[front + 1]; } }
问题分析并优化
目前数组使用一次就不能用， 没有达到复用的效果
将这个数组使用算法，改进成一个环形的队列 取模：%
数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明：
尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满]
rear == front [空]
根据思路实现数组模拟环形队列
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.Queue * @className: CircleArrayQueueDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/16 16:28 * @version: 1.0 */ public class CircleArrayQueueDemo { public static void main(String[] args) { System.out.println("测试环形队列"); //创建一个队列 这里空间为4 最大有效空间为3 留出一个空间作为约定 CircleArrayQueue queue = new CircleArrayQueue(4); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } /** 环形队列 * 思路变化： * 之前的队列有问什么问题所在 * 问题分析并优化 *1) 目前数组使用一次就不能用， 没有达到复用的效果 *2) 将这个数组使用算法，改进成一个环形的队列 取模：% * 思路如下 ： * 1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr(front]就是队列的第一个元素 * front的初始值 * 2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定. * rear的初始值=0 * 3.当队列满时，条件是（rear+1)%maxSize=front【满】 * 4.对队列为空的条件，rear==front空 * 5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front)%maxSize//rear=1front=0 * 6.我们就可以在原来的队列上修改得到，一个环形队列 * * */ class CircleArrayQueue { //队列最大上限 private int MaxSize; //队列尾部 思路发生变化这次我们的队尾值变化为0指向队列最后一位的前一位 private int rear; //队列头部 思路变化 指向队头的第一位 也就是下标 为 0 private int front; //存放队列数据的数组 private int[] ArrayQueue; /** * @author 冷环渊 Doomwatcher * @context: 初始化构造队列，初始化队列和头尾值向 * 这里为什么没有初始化队头队尾，因为默认 = 0 * @date: 2021/12/16 14:30 * @param maxSize * @return: */ public CircleArrayQueue(int maxSize) { // 获取最大值 this.MaxSize = maxSize; //初始化 队列 ArrayQueue = new int[MaxSize]; } /** * @author 冷环渊 Doomwatcher * @context: * 这里思路变化，因为我们要做环形队列这里我们有一个位置是动态变化的所以我们需要更新计算是否队列已满的方法 * @date: 2021/12/16 14:30 * @param * @return: boolean */ public boolean isfull() { return (rear + 1) % MaxSize == front; } /** * @author 冷环渊 Doomwatcher * @context: 判断队列是否是空的 * @date: 2021/12/16 14:32 * @param * @return: boolean */ public boolean isemity() { return rear == front; } /** * @author 冷环渊 Doomwatcher * @context: * 加入数据我们也要发生变化 这里我们用的是环形了 * rear 的后移不再是最后一位，可能会出现越界的问题 * （rear+1）%maxSize * @date: 2021/12/16 14:34 * @param value * @return: void */ public void addQueue(int value) { if (isfull()) { System.out.println("队列已满 不能加入更多的数据"); return; } //赋值 ArrayQueue[rear] = value; //考虑用取模来后移 rear rear = (rear + 1) % MaxSize; } /** * @author 冷环渊 Doomwatcher * @context: * 为什么不用 ++了呢 因为我们是环形 一定会出现越界，这里考虑取模动态的算出后移的位置 * @date: 2021/12/16 14:37 * @param * @return: void */ public int getQueue() { if (isemity()) { throw new RuntimeException("该队列是空的 无法获取到内容"); } /* * 1，我们这次的思路是front代表的是队列的第一个下标 * 2. 用临时变量来拿出 当前的值 * 3.后移front 返回值 * */ int value = ArrayQueue[front]; front = (front + 1) % MaxSize; return value; } /** * @author 冷环渊 Doomwatcher * @context: * 遍历环形队列 输出 这里我们不再是遍历数组长度了 * 我们需要求出有效的数量 * @date: 2021/12/16 14:42 * @param * @return: void */ public void showQueue() { if (isemity()) { System.out.println("队列没有可以遍历的数值"); } //这里我们因该是从 front 开始遍历 for (int i = front; i < front + Size(); i++) { //这里下标我们选择取模 应为是环形的会出现越界的情况，所以我们使用取模运算 System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]); } } /*编写一个求出队列有效数据数量的放啊*/ public int Size() { /* 取模思路套用 * 1. rear = 1 * 2. front = 0 * 3. maxSize = 3 * （1+3-0）%3 = 1 应为算出来是下标 所以我们这里有两个有效数据 0，1 * */ return (rear + MaxSize - front) % MaxSize; } /** * @author 冷环渊 Doomwatcher * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据 * 这里不再是 front-1 应为 front此时默认就是0 * @date: 2021/12/16 14:45 * @param * @return: void */ public int headQueue() { if (isemity()) { throw new RuntimeException("没有头数据"); } return ArrayQueue[front]; } }
代码执行效果
