20210416

回顾 | 闲聊 | 数据结构-栈与队列（七）

Table of Contents

恋词复习

  • remold v.改铸；改造
  • decent adj.体面的，相当不错的；得体的；正派的
  • incentive n.刺激；激励；鼓励；动机

闲聊

逛b站，心爱的博主终极小腾更新了，这一期的视频真的看的我热血沸腾，祖国真的太美了啊！！

数据结构-配置问题-栈与队列（七）

正常配置

上图分别对应正常配置下的队空、入队、出队、队满操作（状态）、入队过程。

操作（状态） 代码 备注
队空 front == rear为真 无
入队 rear = (rear+1)%maxSize; queue[rear]=x; 先移动指针再入队元素
出空 front = (front+1)%maxSize; x=queue[front]; 先移动指针再出队元素
队空 front == (rear+1)%maxSize为真 无

正常配置下元素个数计算

上图分别对应正常配置下当rear > front和rear < front时的图，那么计算此时队中元素有几个？

状态 个数 备注
rear>front rear-front个 无
rear<front (rear+1)+(maxSize-1-front)=rear-front+maxSize个 个数即为黄色部分+蓝色部分

合并一下：即为(rear - front + maxSize ) % maxSize个，队空状态也适用。

非正常配置（一）

上图分别对应非正常配置（一）下的队空、入队、出队、队满操作（状态）、入队过程。

操作（状态） 代码 备注
队空 front == rear为真 与正常配置相同
入队 queue[rear]=x;rear = (rear+1)%maxSize; 先入队元素再移动指针
队空 x=queue[front];front = (front+1)%maxSize; 先取元素再移动指针
队空 front == (rear+1)%maxSize为真 与正常配置相同

正常配置下元素个数计算

上图分别对应正常配置下当rear > front和rear < front时的图，那么计算此时队中元素有几个？

状态 个数 备注
rear>front rear-front个 无
rear<front (rear-0)+(maxSize-front)=rear-front+maxSize个 个数即为黄色部分+蓝色部分

合并一下：即为(rear - front + maxSize ) % maxSize个，队空状态也适用。这种配置下的元素分布与正常配置情况下只是错开了一个位置，而总的个数是不变的，中间的推导过程可能稍有不同（在计算rear<front时），但最后结果是一样的。

非正常配置（二）

上图分别对应非正常配置（二）下的队空、入队、队满操作（状态）、入队过程。

操作（状态） 代码 备注
队空 front == rear为真 与正常配置队满条件恰好相同
入队 queue[rear]=x;rear = (rear+1)%maxSize; 先移动指针再入队元素
队满 front == (rear+2)%maxSize为真 无

其实入队操作在这种配置下也可以先入队元素再移动指针。只不过在这里采取这种方法。

正常配置下元素个数计算

上图分别对应正常配置下当rear > front和rear < front时的图，那么计算此时队中元素有几个？

状态 个数 备注
rear>front rear-front+1个 无
rear<front (rear+1)+(maxSize-front)=rear-front+1+maxSize个 个数即为黄色部分+蓝色部分

合并一下：即为(rear - front + 1 + maxSize ) % maxSize个。

总结

由以上三种配置，其实可以规定front == rear为真时队空，也可以规定front在rear后面时队空，那么其实也可以规定rear和front差n个位置时队空。

即只要设计满足队列的先进先出的特性，怎么搞都可以。（所以要搞清题目配置！）

408例题

由题目句子“队列非空时front和rear分别指向队头和队尾元素这题为非正常配置的题目且为上述所说非正常配置（二），那么易知题目配置为下图，且入队演示：