队列及其应用.pptVIP

清华大学 黄维通 设计制作 第13章 队列及其应用 清华大学 黄维通 设计制作 * 第13章 队列及其应用 本章主要内容 队列的定义及基本操作 队列的实现 队列的应用 队列是删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行的特殊线性表(First In First Out) 13.1 队列的定义及基本操作 队列作为一种抽象数据类型，其基本操作如下： lFront(Q, e)：返回队列Q的队头元素，但不删除该元素 lEnqueue(Q, e)：将元素e插入队列Q的队尾，此操作也常简称为“入队” lDequeue(Q, e)：返回队列Q的队头元素，并删除该元素，简称为“出队” lEmpty(Q)：判断队列是否为空 lClearQueue(Q)：清空队列中的所有元素 队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列，实际上，队列也是一种特殊的线性表。不过，队列中的元素的个数通常不固定，因此常用循环数组和线性表两种方法实现队列 13.2 队列的实现 循环队列－队列的顺序表示和实现 链队列的缺点： 空队列 J1、J2、J3 相继入列 J1、J2 被删除 数据无法继续存进去，但是栈并没有满，如何解决呢？ J4，J5，J6相继插入之后，J4被删除 初始化队列时，令rear=front=0; Q.front Q.rear Q.rear Q.rear Q.rear Q.front Q.front Q.front J1 J2 J3 J3 J5 J6 13.2.1用循环数组实现队列 队列“满”的情况 队列“空”的情况 这样，队列的类型QueueType说明为： #define MAXLENGTH 32 #define TYPE int #define NEXT(x) ((x+1)%MAXLENGTH) struct TQueue { int front; int rear; int size; TYPE element[MAXLENGTH]; }; typedef struct TQueue Queue; （1）清空队列中的所有元素的操作 void ClearQueue(Queue * q) //清空队列中的所有元素 { q-rear = MAXLENGTH-1; q-front = 0; q-size = 0; } （2）返回队列Q的队头元素，但不删除该元素的操作 void Front(Queue q, TYPE * e) //返回队头元素，但不删除该元素 { if(Empty(q)) e = NULL; else *e = q.element[q.front]; } （3）将元素e插入队列Q的队尾的操作 void Enqueue(Queue *q, TYPE e) //将元素e插入队列Q的队尾 { if(q-size == MAXLENGTH) return; else { q-rear = NEXT(q-rear); q-element[q-rear] = e; q-size ++; } } （4）返回队列Q的队头元素，并删除该元素的操作 void Dequeue(Queue * q, TYPE * e) { if(Empty(*q)) e = NULL; else { *e = q-element[q-front]; q-front = NEXT(q-front); q-size --; } } （5）判断队列是否为空的操作 int Empty(Queue q) { return(q-front==q-rear); } 用线性表实现队列时，单元类型及队列类型可说明如下: #define TYPE int struct TNode //定义线性表结构 { TYPE element; struct TNode *next; }; typedef struct TNode Node; 13.2.2 用线性表实现队列操作 链式队列 用链表表示的队列简称链式队列；它必须由头指针和尾指针才能唯一确定，实际上，链式队列的操作即为单链表插入和删除的特殊情况 Q.front Q.rear 空队列 Q.front Q.rear x 元素x入队列 元素y入队列 Q.front Q.rear y x 头元素出列 y x Q.front Q.rear struct TQueue //定义队列结构 { Node * head; Node * front; Node * rear; }; typedef struct TQueue Queue; ? void InitQueue