顺序存储队列的假溢出的避免方法及循环队列满和空的条件判断

《顺序存储队列的假溢出的避免方法及循环队列满和空的条件判断》由会员分享，可在线阅读，更多相关《顺序存储队列的假溢出的避免方法及循环队列满和空的条件判断（2页珍藏版）》请在装配图网上搜索。

1、顺序存储队列的假溢出的避免方法及循环队列满和空的条件判断设顺序存储队列用一维数组 qm 表示，其中 m 为队列中元素个数， 队列中元素在向量中的下标从 0到 m-1。设队头指针为front,队尾指针是rear，约定front指向队头元素的前 一位置， rear 指向队尾元素。当 front 等于 -1 时队空， rear 等于 m-1 时为队满。由于队列的性质（“删除”在队头而“插入”在队尾） ，所 以当队尾指针rear等于m-1时，若front不等于-1,则队列中仍有空 闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢其解决办法有二：一是将队列元素向前“平移”（占用0至rear-

2、front-1）；二是将队列看成首尾相连,即循环队列（ 0.m-1）。在循环队列下,仍定义 front=rear 时为队空,而判断队满则用两种办 法，一是用“牺牲一个单元”， 即 rear+1=front （准确记是 （ rear+1）%m=front，m 是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag, tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。判断循环队列的状态有两种方法：1 少用一个元素空间约定以 “队列头指针在队列尾指针的下一个位 置上”作为队列呈“满”状态的标志2 另设一个标志以区别队列是“满”还是“空” 。标志，记录对队列最后的操作是删除还是插入。当头尾指针相等时，如果标志记录的是删除，则队列空。如果记录的是插入，则队列满。