第三章栈和队列 - mc lab.ppt

a3 a2 a1 0 1 2 3 N-1 rear front 循环队列（臆造） 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案有三： ①使用一个计数器记录队列中元素个数（即队列长度）； ②加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况 ③ 人为浪费一个单元，则队满特征可改为front=(rear+1)%N； 顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 * 3.2 队列 队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度（即数据元素个数）：L=（N＋rear－front）% N J2 J3 J1 J4 J5 front rear 实际中常选用方案3（人为浪费一个单元）： 即front和rear二者之一指向实元素，另一个指向空闲元素。 问3： 在具有n个单元的循环队列中，队满时共有多少个元素？ N-1个 6 问1：左图中队列maxsize N=？ 问2：左图中队列长度L=？ 5 * 3.2 队列 队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队空： Q.front =Q. rear 队满： Q.front =(Q.rear + 1) % maxSize 入队: Q.rear = (Q.rear + 1) % maxSize 出队: Q.front = (front + 1) % maxSize; 求队长: (Q.rear-Q.front+maxSize)%maxSize 循环队列： Status EnQueue (SqQueue Q, QElemType e) {// 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE = Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } 循环队列入队的实现 （教材p65）： Status DeQueue (SqQueue Q, QElemType e) {// 若队列不空，则删除Q的队头元素， // 用e返回其值，并返回TRUE; 否则返回FALSE if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } 循环队列出队的实现 （教材p65）： （Ａ） r－f （Ｂ）（n＋f－r）% n （Ｃ）n＋r－f （Ｄ） （n＋r－f）% n 要分析4种公式哪种最合理？ 当 r ≥f 时（A）合理； 当 r f 时（C）合理； 答： 综合2种情况，以（D）的表达最为合理 例2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先 移动队首指针 取出元素 ，后 。 例1：数组Ｑ[n]用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为: * 3.2 队列 例3： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置? J2 J3 J1 J4 J5 front=2 rear=1 解：由图可知，队头和队尾指针的初态分别为front=2和rear=1。 删除4个元素后， f= (2+4) %6=0 再插入4个元素后，r=(1+4)%6=5 front=0 J6 J5 J7 J8 J9 rear=5 rear=1 front=0 * 3.2 队列 对这4个数据元素进行的队操作是进队2次，出队1次，再进队2次，出队1次；这时，第1次出队得到的元素是 ？ ，第2次出队得到的元素是 ？ 。经操作后，最后在队中的元素还有 ？