教黎 栈和队列 程序设计—数据结构 基本概念及应用 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：R={R1},R1={<a-l,a>a-1,a∈D,i=2,3,…,n} 基本操作： InitQueue(&O) 操作结果：构造一个空队列Q DestroyQueue(&Q) 初始条件：队列Q已存在 操作结果：销毁队列Q ClearOueue(&O) 初始条件：队列Q已存在 操作结果：将队列Q重置为空队列 QueueEmpty(Q) 初始条件：队列Q己存在 操作结果：若Q为空队列，则返回TRUE,否则返回FALSE QueueLength(O) 初始条件：队列Q已存在 操作结果：返回队列Q中数据元素的个数 GetHead(Q,&e) 初始条件：队列Q已存在且非空 操作结果：用e返回Q中队头元素 EnQueue(&Q,e) 初始条件：队列Q己存在 操作结果：插入元素e为Q的新的队尾元素 DeQueue(&Q,&e) 初始条件：队列Q己存在且非空 操作结果：删除Q的队头元素，并用e返回其值 QueueTraverse(Q,visit()) 初始条件：队列Q已存在且非空 操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一 旦visit()失败，则操作失败 }ADT Queue 3、双端队列 1)限定插入和删除在表的两端进行，应用举例：铁道转轨网络 2)输出受限的双端队列和输入受限的双端队列 3)双端队列→两个栈底相邻接的栈：限定双端队列，从某端点插入的元素只能从该端点删 除。 3.4.2链队列 1、链队列的定义 typedef struct QNode! ElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct QueuePtr front: 体队头指针，指向头元素 */ QueuePtr rear; 体队尾指针，指向队尾元素 文档编号 完成时间 完成人张昱 修改时间 第7页程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 7 页 数据对象：D={ai |ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={<ai-1,ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitQueue(&Q) 操作结果：构造一个空队列 Q DestroyQueue(&Q) 初始条件：队列 Q 已存在 操作结果：销毁队列 Q ClearQueue(&Q) 初始条件：队列 Q 已存在 操作结果：将队列 Q 重置为空队列 QueueEmpty(Q) 初始条件：队列 Q 已存在 操作结果：若 Q 为空队列，则返回 TRUE，否则返回 FALSE QueueLength(Q) 初始条件：队列 Q 已存在 操作结果：返回队列 Q 中数据元素的个数 GetHead(Q,&e) 初始条件：队列 Q 已存在且非空 操作结果：用 e 返回 Q 中队头元素 EnQueue(&Q, e) 初始条件：队列 Q 已存在 操作结果：插入元素 e 为 Q 的新的队尾元素 DeQueue(&Q, &e) 初始条件：队列 Q 已存在且非空 操作结果：删除 Q 的队头元素，并用 e 返回其值 QueueTraverse(Q, visit()) 初始条件：队列 Q 已存在且非空 操作结果：从队头到队尾依次对 Q 的每个数据元素调用函数 visit()。一 旦 visit()失败，则操作失败 }ADT Queue 3、双端队列 1) 限定插入和删除在表的两端进行，应用举例：铁道转轨网络 2) 输出受限的双端队列和输入受限的双端队列 3) 双端队列→两个栈底相邻接的栈：限定双端队列，从某端点插入的元素只能从该端点删 除。 3.4.2 链队列 1、链队列的定义 typedef struct QNode{ ElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; /* 队头指针，指向头元素 */ QueuePtr rear; /* 队尾指针，指向队尾元素 */