数据结构－第03章 节 －栈和队列.pptVIP

3 * ( 7 – 2 ) 3 # * ( 对象栈 算符栈 3 * ( 7 – 2 ) 3 * ( 7 – 2 ) 3 7 # * ( 对象栈 算符栈 3 * ( 7 – 2 ) 3 * ( 7 – 2 ) 3 7 # * ( - 对象栈 算符栈 3 * ( 7 – 2 ) 3 * ( 7 – 2 ) 3 7 2 # * ( - 对象栈 算符栈 3 * ( 7 – 2 ) 3 * ( 7 – 2 ) 3 5 # * ( 对象栈 算符栈 3 * ( 7 – 2 ) 3 * ( 7 – 2 ) 3 5 # * 对象栈 算符栈 3 * ( 7 – 2 ) 消去一对括号 3 * ( 7 – 2 ) 15 # 对象栈 算符栈 3 * ( 7 – 2 ) 第3章 栈和队列 栈 栈的应用举例 队列 队列的应用举例 3.4.1 抽象数据类型队列的定义 队列是一种先进先出(First in First Out，FIFO)的线性表。 只允许在一端进行插入，而在另一端删除。 这和日常生活中的排队是一致的，最早进入队列的人最早离开。 3.4 队列(Queue) 队列 ( Queue ) 定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) a1 a2 a3 an front rear ?? 出队列 入队列 ADT Queue { 数据对象：D={ai |ai∈ElemSet，i =1,2,…,n，n≥0} 数据关系：R1={ ai-1 , ai |ai-1 ,ai ∈ D，i =2，…，n} a1为队列头，an为队列尾。 基本操作： InitQueue (Q) 操作结果：构造一个空队列Q。 DestroyQueue (Q) 操作结果：队列Q被销毁，不再存在 ClearQueue (Q) 操作结果：将Q清为空队列。 QueueEmpty (Q) 操作结果：若Q为空队列，则返回TRUE，否则FALSE。 ………………… 队列的抽象数据类型定义 3.4.2 链队列 链队列：用链表表示的队列。 一个链队列需要两个指针，分别指示队头和队尾的指针——头指针和尾指针。 给链队列添加一个头结点。空的链队列的判决条件为头指针和尾指针均指向头结点。 front rear (a)空队列 （c)元素y入队列 (b)元素x入队列 (d)元素x出队列 队列运算指针变化情况 y x Q.front Q.rear Q.front Q.rear y x Q.front Q.rear x Q.front Q.rear 链队列的操作需修改尾指针或头指针。 链队列的操作 //单链队列——队列的链式存储结构 typedef struct QNode{ QElemType data； struct QNode *next； }QNode，*QueuePtr； typedef struct { QueuePtr front； //队头指针 QueuePtr rear； //队尾指针 } LinkQueue； 链队列的表示与实现 //———基本操作的算法描述 Status InitQueue ( LinkQueue Q){ //构造一个空队列 Q.front=Q.rear= (QueuePtr) malloc (sizeof(QNode))； if(!Q.front) exit (OVERFLOW)； Q.front—next = NULL； return OK； } 构造一个空链队列 Q.front Q.rear Status DestroyQueue (LinkQueue Q){ //销毁队列 while(Q.front){ Q.rear = Q.front—next；