常用的循环队列

阵列变形-圆形队列

不管是哪种开发方式，我们经常每天使用Array Array，向其中添加元素，删除元素...都是非常频繁的操作.

但是今天我们讨论循环队列，它也是一个数组Array，那么它与我们日常使用的数组操作之间有什么区别，它有什么优点？

我们想象一个场景，一群病人拿起电话号码，等着看候诊室的感冒. 假设等候室有5个座位，编号为0、1、2、3、4. 您可以参考下图:

因此，按照先到先得的原则，医生将首先在位置0处看患者，然后当患者0到达诊所时，患者1将移至患者0，而患者2将移至患者0. 移至患者1. 在原始位置，患者3将移至患者2的原始位置，而患者4将移至患者3的原始位置. 如果后方仍有患者，则站立的患者将转到坐4坐下吧？然后，从诊所看到原始患者0之后，然后是新患者0（患者经过时的原始位置1），他将进入咨询室，然后发生另一轮移动到该位置的情况...如下所示:

这是医院的医生遵循先到先得的原则的方式. 如上面的代码中所述，这也是常识.

但是，如果这家医院很大，而且每天都有很去看医生，那么假设等候室有100个位置，数量是0-99，则每天都会满员，然后坐在位置0首先是人去看医生，然后位置1-99的患者将向前移动一个位置，即1-> 0,2-> 1，.... 99-> 98，新患者坐在位置99

在此过程中，每位患者走进诊室看医生时，后面的人将向前移动一个位置并重复一次. 看到这一点，您是否曾想过真正的麻烦感觉，也很累，不是，总是想移动位置... -_-

在这里，如果我们的队列（数组）有100万个元素，我们取出队列的头，即数组[0]，然后将后面的元素一一向前移动，然后全部完成. 转换位置后，花费的时间为O（n）复杂度. 团队越长，时间成本就越大. 因此，一个结论是: 从数组中获取head元素的时间复杂度为O（n）.

然后我们将考虑，可以简化从队列头（数组）的头部获取元素的操作的复杂性，从而使出队操作的成本降低，可以，请问问我们亲爱的通函队列出现，我们表示热烈欢迎.

循环队列它也是一个数组. 但是，为了指示团队的头和尾，我们需要引入两个额外的变量，前部指示团队负责人的位置，尾部指示将进入队列的下一个位置，也就是说在尾元素后面的位置. 为什么不以这种方式设计它，不用担心，让我们看下面的图片:

看上面的图片，当队列（数组）为空时，front == tail，我们要指出的是，当数组已满时，如果front == tail，那么就无法判断它是否为空或满. 如果使用tail指示tail元素的位置，则此处将存在歧义，因此，front指示head元素的位置，而tail指示进入队列的下一个位置. 然后以这种方式，为了指示该数组已满，我们必须牺牲下一个数组的位置，以便指示该数组已满，tail + 1 == front. 当我们想要进入病人时，我们改变尾巴，当我们想要取出病人时，我们改变前轮，所以来回往复，整个感觉是尾巴追逐着前轮，阵列感觉就像是一条路端到端的连接，请参见下图，该模拟涉及3位患者，然后是1位患者.

上图中的操作流程已被总结. 当新患者进入队列时，我们只需要将其放在队列的末尾，然后tail =（tail + 1）％Patient.length，当我们想让前一个患者去诊所时，第一组患者被取出. 然后，front =（front + 1）％Patients.length，通过移动代表队长的前标记和代表队尾的尾标记，我们可以避免移动数组元素的位置，这减少了很多费用-_-.

现在，取出团队第一个元素的时间复杂度变为O（1）. 想象一下，我们的服务器商品库中有数百万个产品正在等待处理. 如果业务场景是从团队的头到团队，如果您想要一个接一个地处理尾部，则使用前数组元素位置偏移方法，然后计算时间，估计是几秒钟，类似于感觉我们打开一个白色屏幕的网站，这将非常糟糕，对吧？

但是如果我们采用后一种方法通过前后方法标记团队的头和尾，那么服务器将迅速完成取出商品头的操作-_-

好的，以上是循环队列的使用场景. 当数组很长时，我们需要以最小的代价提取队列的第一个元素，那么循环队列是一个很好的解决方案，但是您可以从上面看到，循环队列指示队列（数组）已满，并且需要牺牲额外的空间. 但是，与节省时间相比，此小空间的浪费可以忽略不计.

循环队列是我们常用的数据结构之一，它也非常强大. 也许您正在进行前端开发，不会使用大容量数组循环队列，但是您仍然了解在循环队列中获取和存储元素的方法. 很有好处.

例如，滚动移动电话页面顶部的横幅，第一个，然后第二个循环队列，最后一个. 如果您想回到第一个，则不是说正面从正面到背面，然后再回到正面，请参见下图:

循环队列有许多派生应用程序，等待大家探索，大家欢呼...

今天推荐

返回搜狐了解更多

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-190993-1.html