西安电子科技大学计算机学院数据结构课件 第3章（3）.pptVIP

4. 双端队列（Deque） 限定插入和删除操作在表的两端进行的线性表。 初始化 InitQueue(LinkQueue Q) { Q.front = Q.rear = (QueuePtr)malloc(…); if(!Q.front) exit(OVERFLOW); Q.front-next = NULL; return OK; } 入队列 EnQueue(LinkQueue Q, QElemType e) { p = new QNode; if(!p) exit(OVERFLOW); p-data = e; p-next = NULL; ①Q.rear-next = p; ②Q.rear = p; return OK; } 出队列DeQueue(LinkQueue Q, QElemType e) { if(Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; ①Q.front-next = p-next;(Q.front-next-next) ②if(Q.reat == p) Q.rear = Q.front; delete p; return OK; } 循环队列 typedef struct{ QElemType *base; int front; int rear; }SqQueue; 约定：空队列Q.front = Q.rear; 入队列（插入元素）Q.rear++; 出队列（删除元素）Q.front++; 非空队列，front指针始终指向队头元素， rear指针始终指向队尾元素的下一位置。 ⑤循环队列中元素的个数 初始化 InitQueue(SqQueue Q) { Q.base = (QElemType *) malloc(……); if(!Q.base) exit(OVERFLOW); Q.front = Q.rear = 0; return OK; } 入队列EnQueue(SqQueue Q, QElemType e) { if((Q.rear+1)%MAXQSIZE)==Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear+1) %MAXQSIZE; return OK; } 出队列 DeQueue(SqQueue Q, QElemType e) { if(Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1)%MAXQSIZE; return OK; } 6.队列总结 队列是一种具有线性结构的数据结构，是操作受限的线性表； 队列的特点是先进先出，只能在队尾插入元素和队头删除元素，称为入队列和出队列； 循环队列中，队空标志：Q.front == Q.rear 队满标志： (Q.rear+1)%MAXQSIZE == Q.front; 链队列中，Q.front = Q.rear, 在用户空间范围内不会出现队满的情况。 练习： 1.设A是一个栈，栈中共有n个元素a1a2…an，an为栈顶元素，B是一个队列，队列中有n个元素b1b2…bn，b1为队头元素，bn为队尾元素，A，B采用顺序存储结构且空间足够大，现将栈中元素全部移到队列中，使得队列中元素与栈中元素交替排列，即B中元素为b1a1b2a2…bnan，问至少多少次基本操作才能完成上述工作。（除A，B外使用的其它附加存储量为1）。 ①先将栈中元素依次入队列，栈空； ②将b1b2…bn依次出队列，入队列； ③将anan-1…a1出队列，入栈； ④顺次bi出队列，入队列， ai出栈，入队列。 2n+2n+2n+4n = 10n 个基本操作 2.（3.28)带头结点的循环链表表示队列，只设尾指针。 typedef struct QNode{ QElemType data;