队列_再听一遍就睡的博客-程序员秘密

队列

定义：队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列（Queue）是一种先进先出（First In First Out）的线性表，简称FIFO。
允许插入的一端叫做队尾，删除的一端叫做队头。

在这里插入图片描述
同样是线性表，队列也有类似的操作。不同的是队列是在队尾插入数据，在队头删除数据。

顺序队列

队列的基本操作

 1. getSize（）	获取队列中有效元素的个数
 2. isEmpty（）	判断是否为空
 3. clear（）	清空队列
 4. enqueue（）	入队
 5. dequeue（）	出队
 6. getFront（）	获取队首元素
 7. getRear（）	获取队尾元素

空队列：
在这里插入图片描述
这是一个长度为6空队列，此时队尾指针在头部。当我们向队列中插入元素时，效果如下图。

插入数据时，队尾指针向后移动
插入一个数据，队尾指针移动到下标加1的位置

在这里插入图片描述
当我们插入两个数据时，我们要删除一个数据，那么数据要从队头的位置开始删除，即现在下标为0的位置的数据要出队，下标为1的数据就要移动到下标为0的位置，同时队尾指针也要移动到下标为0的位置，即向左移动。

顺序存储的队列是是由ArrayList实现的。
即在数据元素入队的时候，相当于在 ArrayList表尾添加元素，时间复杂度为O（1）。
即在数据元素出队的时候，相当于在 ArrayList表头添加元素，时间复杂度为O（n）。
出队的时间复杂度为O（n）是因为当前只有队尾指针在移动，而队头始终不动，而且还要保证数据的连续性，所以出队的时间复杂度为O（n）。

为了解决出队的时间复杂度为O（n）的问题，我们有了循环队列这个概念。

在这里插入图片描述
这里我们添加了队头指针，队头指针指向队列中第一个元素，队尾指针指向队列中最后一个元素。

在这里插入图片描述
当我们引入队头指针时，出队数据元素时，队头指针向后移动1个下标的位置即可。

这样出队的时间复杂度就成了O（1）。

在这里插入图片描述
但是这样优化的问题就是入队出队的时候数据元素是往后移动的，前面的部分位置就空下来了。且尾指针（Rear）不能继续后移了。

在这里插入图片描述
为了解决上面的问题，我们让头指针和尾指针走到表尾的时候需要后移就重新指向头部。

在这里插入图片描述
但是这个时候如何判断队列是满的还是空的？
但是这个时候我们不难发现，当队列已满和队列为空时，判定的条件都可以是（R+1）%n==F
因为这个条件同时满足两种情况，属于不严谨的情况，所以我们要再次优化。

在这里插入图片描述
我们让尾指针始终指向数组中元素的后一个下标的位置，但这个位置里什么都不存，为null。
这样就可以解决判定队列已满和为空的条件重复了。

在这里插入图片描述
我们不难看出这个时候队列为空，判断的条件是R==F。

在这里插入图片描述

队列已满时，判断的条件是（R+1）%n==F。

本文链接：https://blog.csdn.net/jxc47/article/details/100782186

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

同花顺python_【本地直连】同花顺 Python量化交易接口上线_weixin_39938724的博客-程序员秘密

来源：雪球App，作者：私募之家THS，（https://xueqiu.com/5808549553/129022113）导读：同花顺智能交易终端MindGo版已上线2年多，凭借着同花顺深厚的技术底蕴，不断地对终端进行优化。至今，已服务近1000位个人客户，超过200家私募机构，市场份额不断扩大。目前终端已实现：支持股票、指数、基金、期货、外汇、黄金T+D等6个品种日/分钟级策略回测投研策略无缝...

MySQL -- 数据类型_zhubao124的博客-程序员秘密

数据类型一、数值类型（1）、整型1、int大整型(4个字节) 存储范围：0 ~ 2*32 - 1 2、tinyint 微小整型(1个字节) 1、有符号 signed(默认) -128~127 2、无符号 unsigned 0~255 ...

join()方法的使用_join方法使用_EclipseO2的博客-程序员秘密

一、join()方法的使用主线程创建并启动子线程，如果自线程中要进行大量的耗时运算，主线程往往将早于子线程结束之前结束。如果主线程想等待子线程执行完成之后再结束，比如子线程处理一个数据，主线程要取得这个数据中的值，就要用到 join() 方法先来看一个不用 join() 方法的例子public class MyThread extends Thread { @Override ...

Deprecated: mysql_connect(): The mysql extension is deprecated的解决方法_jasonkent27的博客-程序员秘密

PDO:$dbh = new PDO('mysql:host=localhost;dbname=test', $user, $pass);MYSQLI:$link = mysqli_connect( 'localhost', /* The host to connect to 连接MySQL地址 */ 'user

vue中使用import引入的（方法）function_vue引用function_菜菜子。的博客-程序员秘密

vue3种使用import引入的方法vue3废弃了过滤器的写法，但是很多时候我们对数据进行处理的时候是需要一些转化的，比如我最近遇到的时间转化的问题。刚开始我的做法是然后在用的地方引入一开始的时候我在用的地方直接用了然而。。控制台报错是这样的研究一番之后发现是html里面的内容引用的function必要要export default之后才能使用，所以vue3的话就是把import的方法return 出去就可以vue2的话就是在methods里面声明一下也可以这样就可以在html中使用imp

Unity的UGUI获取InputField输入框文字当前的行数——效果展示（图文详情+源码）_unity ugui获取uitext行数_水光涵月的博客-程序员秘密

Unity的UGUI获取InputField输入框文字当前的行数——（图文详情+源码）????需求????效果????设置????源码总结????????版权声明????需求UGUI，要获取输入框（InputField）的光标在第几行????效果废话不多说，先来看下效果????设置需要把原来的InputField组件删除掉，换成InputTest挂载上去，这几个位置需要重新指定下????源码using System;using System.Collections;usi