《数据结构》栈和队列.ppt

队列的进队和出队 进队时，将新元素插入Q.rear 指示位置，再将队尾指针加1， Q.rear = Q.rear + 1 。 出队时，将Q.front所指位置 的元素取出，再将队头指针加1， Q.front = Q.front + 1 。 队满时再进队将出现“假溢出”现象。 * 解决方案： 按最大可能的插入操作次数设置顺序队列的最大元素个数，此方法有时会因估计不准而出错，并会有较大的空间浪费； 队首固定，每次出队后剩余元素向下移动 ——浪费时间 循环队列 ? * 2.循环队列：把顺序队列构造成一个头尾相连的环，形成循环队列（存储队列的数组被当作首尾相接的表处理。） an … ai ... a2 a1 Q.front Q.rear Q.front Q.rear 0 1 …... …... maxsize-1 循环队列 * 在循环队列中进行出队、入队操作时，头、尾指针仍要加1，只不过当头、尾指针指向向量上界（ MaxSize -1 ）时，其加1操作的结果是指向向量的下界0（循环加 1）。可用C语言的取模(求余数)运算实现。 入队时，队尾指针加1操作改为: Q.rear = (Q.rear + 1)% MAXQSIZE 出队时，队头指针加1操作改为: Q.front = (Q.front + 1)% MAXQSIZE 显然，因为循环队列的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 * 0 1 2 3 4 5 Q.rear Q.front J5 1 J4 J6 0 2 3 4 5 Q.rear Q.front J3 J8 J7 J4 J5 0 1 2 3 4 5 J3 Q.rear Q.front 初始状态 J3,J4,J5出队 J6,J7,J8入队 队空：Q.front = =Q. rear 队满：Q.front = = Q.rear 解决方案： 1. 另外设一个标志以区别队空、队满 2. 少用一个元素空间 * 约定队头指针在队尾指针的下一位置（指环状的下一位置）上作为队列“满”状态的标志，即以队尾指针在循环意义下加1是否等于队头指针来判断队满，则： 队满条件为：(Q.rear+1)%Maxsize==Q.front 队空条件仍然为：Q.front ==Q.rear （注意：Q.rear所指的单元始终为空） J4 J5 J6 0 1 2 3 4 5 J3 J7 Q.front Q.rear 队满 * 循环队列的C语言实现 //----循环队列的存储结构---- #define MAXSIZE 100 typedef struct { QElemType *base; int front; int rear; }SqQueue; * 循环队列基本操作的实现 (1) 初始化 Status InitQueue(SqQueue Q){ Q.base=(QElemType *) malloc(MAXSIZE*sizeof(QElemType)); if (!Q.base) exit (OVERFLOW); Q.front = Q.rear = 0; return OK; } (base+ Maxsize-1)→ base→ * *  (2) 求队列长度 int QueueLength(SqQueue Q) {//返回Q的元素个数，即队列的长度 return (Q.rear- Q.front+MAXQSIZE )%MAXQSIZE; } (3) 入队 Status EnQueue(SqQueue Q,QElemType e) { //将元素e插入队列Q的队尾 if ((Q.rear+1) % MAXSIZE == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXSIZE; return OK; } * (4) 出队 Status DeQueue(SqQueue Q,QElemType e) { //删除队列Q的队头元素并用e带回 if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXSIZE; return OK; }