<顺序队列-知识大全-满米百科
> 知识大全 > 列表
顺序队列
时间:2024-12-23 16:46:40
答案

顺序队列

顺序队列   ( )顺序队列的定义    队列的顺序存储结构称为顺序队列 顺序队列实际上是运算受限的顺序表

( ) 顺序队列的表示   ①和顺序表一样 顺序队列用一个向量空间来存放当前队列中的元素   ②由于队列的队头和队尾的位置是变化的 设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置 它们的初值在队列初始化时均应置为    ( ) 顺序队列的基本操作   ①入队时 将新元素插入rear所指的位置 然后将rear加   ②出队时 删去front所指的元素 然后将front加 并返回被删元素   注意    ①当头尾指针相等时 队列为空    ②在非空队列里 队头指针始终指向队头元素 尾指针始终指向队尾元素的下一位置    顺序队列基本操作【参见动画演示】

( )顺序队列中的溢出现象   ① 下溢 现象     当队列为空时 做出队运算产生的溢出现象 下溢 是正常现象 常用作程序控制转移的条件   ② 真上溢 现象     当队列满时 做进栈运算产生空间溢出的现象 真上溢 是一种出错状态 应设法避免   ③ 假上溢 现象  由于入队和出队操作中 头尾指针只增加不减小 致使被删元素的空间永远无法重新利用 当队列中实际的元素个数远远小于向量空间的规模时 也可能由于尾指针已超越向量空间的上界而不能做入队操作 该现象称为 假上溢 现象  【例】假设下述操作序列作用在初始为空的顺序队列上           EnQueue DeQueue EnQueue DeQueue …  尽管在任何时刻 队列元素的个数均不超过 但是只要该序列足够长 事先定义的向量空间无论多大均会产生指针越界错误

循环队列   为充分利用向量空间 克服 假上溢 现象的方法是 将向量空间想象为一个首尾相接的圆环 并称这种向量为循环向量 存储在其中的队列称为循环队列(Circular Queue)     

( ) 循环队列的基本操作   循环队列中进行出队 入队操作时 头尾指针仍要加 朝前移动 只不过当头尾指针指向向量上界(QueueSize )时 其加 操作的结果是指向向量的下界 这种循环意义下的加 操作可以描述为 ① 方法一     if(i+ ==QueueSize) //i表示front或rear        i= ;    else        i++;② 方法二 利用 模运算     i=(i+ )%QueueSize

( ) 循环队列边界条件处理   循环队列中 由于入队时尾指针向前追赶头指针 出队时头指针向前追赶尾指针 造成队空和队满时头尾指针均相等 因此 无法通过条件front==rear来判别队列是 空 还是 满 【参见动画演示】  解决这个问题的方法至少有三种   ① 另设一布尔变量以区别队列的空和满   ② 少用一个元素的空间 约定入队前 测试尾指针在循环意义下加 后是否等于头指针 若相等则认为队满(注意 rear所指的单元始终为空)   ③使用一个计数器记录队列中元素的总数(即队列长度)

( ) 循环队列的类型定义      #define Queur Size    //应根据具体情况定义该值     typedef char Queue DataType;  //DataType的类型依赖于具体的应用     typedef Sturet{               //头指针 队非空时指向队头元素           int front;              //尾指针 队非空时指向队尾元素的下一位置           int rear;               //计数器 记录队中元素总数           DataType data[QueueSize]     }CirQueue;

( ) 循环队列的基本运算   用第三种方法 循环队列的六种基本运算  ① 置队空      void InitQueue(CirQueue *Q)      {              Q >front=Q >rear= ;              Q >count= ;     //计数器置        }

推荐
© 2024 满米百科