数据结构之队列小结.ppt

思考题 * 数据结构 * 3.4 队列 3.4.1 抽象数据类型队列的定义 队列(Queue):一种运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 　　先进入队列的成员总是先离开队列。故队列亦称先进先出(First In First Out)的线性表，简称FIFO表。 （a1, a2, ……, an） 队尾 队头 下图是队列的示意图： 　　　　　 　　　　　 　　 　　　　　 队列的抽象数据定义见书Ｐ59 除了栈和队列之外，还有一种限定性数据结构，它们是双端队列 a1 a2 a3 入队 队尾 队头 出队 队头 端1 端2 插入 删除 ? ? 双端队列示意图 a1 a2 ai a0 an-1 删除 插入 ? ? … … 3.4.2 链队列—队列的链式表示和实现 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。 rear front ∧ … ∧ front rear 非空队 rear front a1 an ∧ 　 … a2 Q rear front Q a1 ∧ 　 rear front Q ∧ 空队 只有一个元素结点 头尾指针封装在一起的链队 front rear x入队 ^ x front rear y入队 x ^ y front rear x出队 x ^ y front rear y出队 ^ typedef struct QNode{ QElemType data; QNode *next; } QNode ,*QueuePtr; typedef struct { QueuePtr front,rear; // 队头、队尾指针 } LinkQueue; Status InitQueue(LinkQueue Q) { // 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); Q.front-next=NULL; return OK; } front rear 空队 ^ Status DestroyQueue(LinkQueue Q) { // 销毁队列Q(无论空否均可) while(Q.front){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } return OK; } Status EnQueue(LinkQueue Q,QElemType e) { // 插入元素e为Q的新的队尾元素 if(!(p=(QueuePtr)malloc(sizeof(QNode))))//失败 exit(OVERFLOW); p-data=e; p-next=NULL;Q.rear-next=p; Q.rear=p; return OK; } p front a2 an ∧ rear ∧ rear a1 e Status DeQueue(LinkQueue Q,QElemType e) { // 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR if(Q.front==Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; } front a1 a2 an ∧ rear p front a1 p ∧ rear ∧ rear 3.4.3 循环队列－队列的顺序表示和实现　 初始空队列：front = rear=0 ; 插入新的元素时, rear++; 删除队头元素时,front++; 0 1 2 3 4 入队 出队 a3 a4 Q.rear Q.front a5 Q.rear 假溢出 如何解决假溢出？ Q.rear a6 Q.rear 1 0 maxsize-1 ... Q.front Q.rear ... 队列 当Q.rear Q.front时: Q.rear – Q.fr