DS03栈和队列04队列.ppt

第3章 栈和队列;3.4.1 抽象数据类型队列的定义;队尾(Rear): 表中允许插入的一端 队头(Front): 允许删除的一端 入队：将一个数据插入到队尾的操作 出队：读取队头结点数据并删除该结点的操作;队列的抽象数据类型定义;队列的基本操作：;6）GetHead(Q, e) 初始条件：Q为非空队列 操作结果：用e返回Q的队头元素 7) EnQueue(Q, e) 初始条件：队列Q已存在 操作结果：插入元素e为Q的新的队尾元素 8）DeQueue(Q, e) 初始条件：Q为非空队列 操作结果：删除Q的队头元素，用e返回值 9）QueueTraverse(Q,visit()) 从队头到队尾，依次对Q的每个数据元素调用函数visit();第3章 栈和队列; 与栈类似，队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，队列的存储方式也分为两种，即顺序队列和链式队列。;队列运算指针变化状况;链队列的类型定义;队列的基本操作--构造一个空队列;销毁空队列;入队列;出队列;第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列——队列的链式表示和实现 3.4.3 循环队列——队列的顺序表示和实现;3.4.3 循环队列—队列的顺序表示和实现;头、尾指针和队列中元素之间的关系;循环队列引入;;循环队列队空和队满的条件;;判空和满的解决方案;循环队列的类型定义;J5;构造空队列;int QueueLen(SqQueue Q) { //求队列Q的元素个数 return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; };Status InsertQueueLen(SqQueue Q, QElemType e) {//元素e入队列Q if ((Q.rear + 1) % MAXSIZE == Q.front) //队列满 return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXSIZE; return OK; };// 出队列 int DeQueue ( SeqQueue Q, QElemType e ) { if ( Q.front==Q.rear ) return ERROR; e = Q.base[Q.front]; Q.front = ( Q.front+1) % MAXQSIZE; return OK; };本章小结 1. 掌握栈和队列这两种ADT的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。 3. 熟练掌握循环队列和链队列的基本操作实现算法，特别应注意队满和队空??条件以及它们的描述方法。;队列的习题;作业--约瑟夫环