第3章 栈和队列_3-3第章 栈和队列_3-3第3章 栈和队列_3-3第3章 栈和队列_3-3.ppt

2. 销毁队列 Status DestroyQueue(LinkQueue Q) { //销毁队列Q while（Q .front）{ Q.rear＝Q.front - next； free(Q.front)； Q.front＝Q.rear； } return OK； }// DestroyQueue 3. 取队头结点数据 datatype FRONT(q) linkqueue *q; { if (EMPTY(q) ) { print(“queue is empty”); return NULL; } else return(q-front-next-data); } /*FRONT*/ 3. 入队 Q Q.front Q.rear ^ … 头结点 队头结点 队尾结点 p e ^ 3. 入队 Status EnQueue(LinkQueue Q, QElemType e) { //将元素e入队 p＝(QueuePtr)malloc(sizeof(QNode))； if (!p) exit（ERROR）； p－data＝e； p－next＝NULL； Q .rear－next＝p； Q .rear＝p； return OK； }// EnQueue 4. 出队 Q Q.front Q.rear ^ … 头结点 队头结点 队尾结点 释放 p 4. 出队 Status DeQueue(LinkQueue Q, QElemType e) { //若队列非空，则将队列Q的对头元素出队并由e返回 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； }// DeQueue *3.4 队列的应用举例 1、多任务的CPU管理 2、缓冲区的设计 作业 1、设计算法判断一个算术表达式的圆括号是否正确配对 2 设单链表中存放着n个字符，试编写算法，判断该字 符串是否有中心对称关系。要求用尽可能少的时间完成。 线性表小结 线 性 表 存储结构 运 算 队列 链 表 顺序表 栈 顺序栈 链 栈 顺序队列 链队列 顺序表 typedef int datatype ; #define maxsize 1024 typedef struct { datatype data[maxsize] ; int last ; } sequenlist; 链 表 typedef int datatype; typedef struct node { datatype data; struct node *next; } linklist; linklist *head, *p; Data Structures: Chapter 3 * 3.3 队列 3.3.1 抽象数据类型队列的定义 3.3.2 链队列 3.3.3 顺序队列 队列 只允许在表的一端进行插入，而在另一端 进行删除。 队头 允许删除的一端 队尾 允许插入的一端 3.3.1 队列的概念及运算 出队 入队 队头 队尾 a1 a2 an ... 入队（插入）和出队（删除）的规则： 先进先出（FIFO） 或后进后出（LILO） 3.3.1 队列的概念及运算 ADT Queue { 数据对象：D＝{ai | ai?ElemSet, i=1,2,3, … ,n. n?0 } 数据关系：R1＝{ ai－1, ai | ai-1, ai ?D, i=2,3, … ,n } 注：约定a1端为对头，an端为队尾。 基本操作： InitQueue(Q) //构造一个空队列 EnQueue(Q,e) //将元素e入队 DeQueue (S,e) //将队头元素出队，并由e返回 } ADT Queue 3.4.3 循环队列--队列的顺序存储结构 队列的顺序存储结构简称为顺序队列。顺序队 列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的，因 而要设置两个指针，分