循环队列.ppt

队列限定插入在队尾进行,删除在队头进行的线性表。所以队列又叫做先进先出线性表。特性:先进先出,(简称为FIFO线性表)。链队列(链式存储结构):^判空条件:=^^^->next=p;=p;^->next=->next->next队列的顺序存储插入元素时,尾指针加1(++);删除元素时,队列头指针加1(++)。=6;约定初始化空队列时:front=rear=00**********,就会出现没有剩余单元的情况。这种现象被称为“假溢出”。循环队列队列的顺序存储0**********、尾指针加1运算的表示:=(+1)%=(+1)%“满”队列“空”=?????队列的顺序存储循环队列解决方法:一是为队列另设一个标志,用来区分队列是“空”还是“满”;二是少用一个元素空间,当队列头指针在队列尾指针的下一个单元时就认为队“满”。此时,队尾指针只差一步追上队头指针。即:(+1)%MAXQSIZE==。一般用第二种方法。判空条件:=:(+1)%MAXQSIZE=#defineMAXQSIZE100//队列的最大数据元素数目typedefstructqueue{//假设只剩下一个单元时认为队满 QElemType*base;//初始化分配的存储空间 intfront;//队头指针 intrear;//队尾指针}SqQueue;(1)初始化队列QintInitQueue(SqQueue&Q){=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!)exit(OVERFLOW);==0;returnOK;}队列的顺序存储循环队列(2)入队i