设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,

您所在的位置:网站首页 环形队列元素个数 设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,

设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,

2024-03-29 13:45| 来源: 网络整理| 查看: 265

注意本题的索引下标是从1开始 所以循环队列中最多有n个元素 在循环队列中,头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位

假设循环队列的队尾指针是rear,队头是front,其中QueueSize为循环队列的最大长度。

(1) 入队时队尾指针前进1:(rear+1)%QueueSize

(2) 出队时队头指针前进1:(front+1)%QueueSize

(3) 队列长度:(rear-front+QueueSize)%QueueSize

现有一循环队列,其队头指针为front,队尾指针为rear;循环队列长度为N。其队内有效长度为?(假设队头不存放数据)

答案:(rear-front+N)%N

(4) 队空和队满的条件

为了区分队空还是堆满的情况,有多种处理方式:

方式1: 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,即约定以"队头指针在队尾指针的下一位置作为队满的标志"。

队满条件为:(rear+1)%QueueSize==front

队空条件为:front==rear

队列长度为:(rear-front++QueueSize)%QueueSize

方式2: 增设表示队列元素个数的数据成员size,此时,队空和队满时都有front==rear。

队满条件为:size==QueueSize

队空条件为:size==0

方式3: 增设tag数据成员以区分队满还是队空

tag表示0的情况下,若因删除导致front==rear,则队空;

tag等于1的情况,若因插入导致front==rear则队满



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3