|
顺序队列 顺序队列 （）顺序队列的定义 队列的顺序存储结构称为顺序队列顺序队列实际上是运算受限的顺序表 （） 顺序队列的表示 ①和顺序表一样顺序队列用一个向量空间来存放当前队列中的元素 ②由于队列的队头和队尾的位置是变化的设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置它们的初值在队列初始化时均应置为 （） 顺序队列的基本操作 ①入队时将新元素插入rear所指的位置然后将rear加 ②出队时删去front所指的元素然后将front加并返回被删元素 注意 ①当头尾指针相等时队列为空 ②在非空队列里队头指针始终指向队头元素尾指针始终指向队尾元素的下一位置 顺序队列基本操作【参见动画演示】 （）顺序队列中的溢出现象 ① 下溢现象 当队列为空时做出队运算产生的溢出现象下溢是正常现象常用作程序控制转移的条件 ② 真上溢现象 当队列满时做进栈运算产生空间溢出的现象真上溢是一种出错状态应设法避免 ③ 假上溢现象 由于入队和出队操作中头尾指针只增加不减小致使被删元素的空间永远无法重新利用当队列中实际的元素个数远远小于向量空间的规模时也可能由于尾指针已超越向量空间的上界而不能做入队操作该现象称为假上溢现象 【例】假设下述操作序列作用在初始为空的顺序队列上 EnQueueDeQueueEnQueueDeQueue… 尽管在任何时刻队列元素的个数均不超过但是只要该序列足够长事先定义的向量空间无论多大均会产生指针越界错误 循环队列为充分利用向量空间克服假上溢现象的方法是将向量空间想象为一个首尾相接的圆环并称这种向量为循环向量存储在其中的队列称为循环队列（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=; //计数器置 } ② 判队空 int QueueEmpty(CirQueue *Q) { return Q>count==; //队列无元素为空 } ③ 判队满 int QueueFull(CirQueue *Q) { return Q>count==QueueSize; //队中元素个数等于QueueSize时队满 } ④ 入队 void EnQueue(CirQueuq *QDataType x) { if(QueueFull((Q)) Error(Queue overflow); //队满上溢 Q>count ++; //队列元素个数加 Q>data[Q>rear]=x; //新元素插入队尾 Q>rear=(Q>rear+)%QueueSize; //循环意义下将尾指针加 ⑤ 出队 DataType DeQueue(CirQueue *Q) { DataType temp; if(QueueEmpty((Q)) Error(Queue underflow); //队空下溢 temp=Q>data[Q>front]; Q>count; //队列元素个数减 Q>front=(Q>front+)&QueueSize; //循环意义下的头指针加 return temp; } ⑥取队头元素 DataType QueueFront(CirQueue *Q) { if(QueueEmpty(Q)) Error(Queue if empty); return Q>data[Q>front]; &nbs |
