[新大纲] 4 栈与队.ppt

1、第二部分 数据结构,主讲教师：王永波 中国矿业大学环境与测绘学院 2013年10月26日,提纲,概述 线性表 栈与队 树与二叉树 图 查找 排序,三、栈与队 栈和队列是两种特殊的线性表，是操作受限的线性表 栈和队列是限定插入和删除只能在表的“端点”进行的线性表,1 栈,只允许在一端插入和删除的线性表 允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom） 特点 后进先出（LIFO） 先进后出（FILO）,S=(a0,a2,an-1),退栈,进栈,a0,an-1,an-2,top,bottom,1.1 栈的抽象数据类型,template class Stack public: S

2、tack ( int = 10 ); / 构造函数 void Push (Type / 判栈满否 ,1.2 栈的存储结构,顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 栈的操作只能在一端进行 栈顶位置随进栈和出栈而变化 栈的顺序存储结构实际上是一维数组 链栈 用链式存储结构来表示栈 对于最大空间需要量事先不知的情况，不能使用顺序栈，需要采用链栈,1.3 栈的数组表示 顺序栈,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,1.3 栈的数组表示

3、顺序栈,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,1.3.1 顺序栈的类定义,template class Stack private: int top; / 栈顶指针 Type *elements; / 栈元素数组 int maxSize; / 栈最大容量 public: Stack ( int = 10 ); / 构造函数 Stack ( ) delete elements; void Push ( Type / 进栈,1.3.1 顺序栈的类定义,Type Pop ( ); / 出栈 Type GetTop

4、 ( ); / 取栈顶 void MakeEmpty ( ) / 置空栈 top = -1; int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize-1; ,1.3.1 顺序栈的类定义,template Stack :Stack ( int s ) : top (-1) , maxSize (s) elements = new TypemaxSize;assert ( elements != NULL ); / 断言 ,1.3.1 顺序栈的类定义,template void Stack :

5、Push ( Type / 退出栈顶元素 ,1.3.1 顺序栈的类定义,template Type stack:GetTop ( ) assert ( !IsEmpty ( ) );/ 先决条件断言 return elementstop; / 取出栈顶元素 ,1.3.2 顺序栈相关说明,若elements的值为NULL，则表明栈结构不存在 若top=-1可作为栈空的标志 栈顶指针top 初值为-1 top=-1,栈空，此时出栈，则下溢（underflow) top=M-1,栈满，此时入栈，则上溢（overflow) 非空栈中的栈顶指针始终在栈顶元素的下一个位置上 插入新的栈顶元素时，指针top

6、增1 删除栈顶元素时，指针top减1,1.4 链式栈栈的链接表示,结构定义 存储结构 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头,1.4.1 链式栈（Linked Stack）类的定义,template class StackNode private: Type data; / 结点数据 StackNode *link; / 结点链指针 public: StackNode ( Type d = 0, StackNode *l = NULL ) : data ( d ), link ( l ) ;,1.4.1 链式栈（Linked Stack）类的定义,templ

7、ate class Stack private: StackNode *top; / 栈顶指针 public: Stack ( ) : top ( NULL ) Stack ( ); void Push ( const Type ,1.4.1 链式栈（Linked Stack）类的定义,template Stack:Stack ( ) StackNode *p; while ( top != NULL ) / 逐结点回收 p = top; top = top-link; delete p; template void Stack:Push ( const Type / 新结点链入*top之前,

8、 并成为新栈顶 ,1.4.1 链式栈（Linked Stack）类的定义,template int Stack:Pop ( ) assert(!IsEmpty(); StackNode *p = top; Type retValue=p-data; top = top-link; / 修改栈顶指针 delete p; return retValue; / 释放 template Type Stack:GetTop ( ) assert ( !IsEmpty ( ) ); return top-data; ,1.5 实例：表达式求值,一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和

9、分界符组成。 算术表达式有三种表示： 中缀（infix）表示 ，如 A+B； 前缀（prefix）表示 ，如 +AB； 后缀（postfix）表示 ，如 AB+；,1.5.1 表达式的中缀表示,表达式中相邻两个操作符的计算次序为： 优先级高的先计算； 优先级相同的自左向右计算； 当使用括号时从最内层括号开始计算。,a + b * ( c - d ) - e f / g,rst1,rst2,rst3,rst4,rst5,rst6,1.5.2 C+中操作符的优先级,优先级 操作符 1 单目-、！ 2 *、/、% 3 +、- 4 、= 5 =、!= 6 double newoperand; whil

10、e (cin ch, ch != =) switch (ch) case + : case - : / 执行计算 case * : / 并将结果 case / : / 放回输入流 DoOperator(ch); break;,default: / 将字符放回输入流 cin.putback (ch); / 重新读操作数 cinnewoperand; / 将操作数放回栈中 AddOperand(newopera); ,1.5.5 利用栈将中缀表示转换为后缀表示,使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。 为了实现这种转换，需要考虑各操作符的优先级。,各个算术操作符的优先级,isp叫做

11、栈内（in stack priority）优先数 icp叫做栈外（in coming priority）优先数。,各个算术操作符的优先级特点,左括号的栈外优先数最高，进栈后最低 其他操作符进栈后优先级升1（+1），满足自左向右计算的要求 操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。,1.5.5 中缀表达式转换为后缀表达式的算法,操作符栈初始化，将结束符#进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch =#，同时栈顶的操作符也是#，停止循环。 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位

12、于栈顶的操作符op的优先级isp：,1.5.5 中缀表达式转换为后缀表达式的算法,1）若 icp (ch) isp (op)，令ch进栈，读入下一个字符ch。 2）若 icp (ch) isp (op)，退栈并输出。 3）若 icp (ch) = isp (op)，退栈但不输出，若退出的是“（”号读入下一个字符ch。 算法结束，输出序列即为所需的后缀表达式。,A+B*(C-D)-(EF)/G ABCD-*+EFG/-,1.5.5 中缀表达式转换为后缀表达式的算法,void postfix(expression e) stack s; char ch, op; s.Push ( ; ); cin

13、.Get ( ch ); while (!s.IsEmpty() ,else if (isp(s.GetTop() icp ( ch ) ) op = s.GetTop ( ); s.Pop( ); cout op; else op = s.GetTop ( ); s.Pop( ); if ( op = ( ) cin.Get ( ch ); ,1.5.6 中缀算术表达式求值,使用两个栈，操作符栈OPTR (operator)，操作数栈OPND(operand)，对中缀表达式求值的一般规则： 1）建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个“#” 2）从头扫描中缀表达式，取一

14、字符送入ch 3）当ch != “#” 时, 执行以下工作, 否则结束算法。此时在OPND栈的栈顶得到运算结果,1.5.6 中缀算术表达式求值,（3-1）若ch是操作数，进OPND栈，从中缀表达式取下一字符送入ch； （3-2）若ch是操作符，比较icp(ch)的优先级和isp(OPTR)的优先级： 若icp(ch) isp(OPTR)，则ch进OPTR栈，从中缀表达式取下一字符送入ch； 若icp(ch) isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出, 形成运算指令 (a1)(a2)，结果进OPND栈； 若icp(ch) = isp(OPTR) 且ch = “)”，则从

15、OPTR栈退出栈顶的“(”，对消括号，然后从中缀表达式取下一字符送入ch；,A+B*(C-D)-(EF)/G,2 队列,队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。 队尾（rear）允许插入的一端 队头（front）允许删除的一端 队列中没有元素时，称为空队列 队列特点 先进先出（ FIFO ）,队列定义,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头，an 端为队列尾 基本操作： ADT Queu

16、e,队列类型,顺序队列 用一维数组表示的队列 循环队列 将顺序队列臆造为一个环状的空间 链队列 用链表表示的队列,顺序队列,顺序存储结构采用一维数组结构 顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。 在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。 规定队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。,#define MAXSIZE n int queueMAXSIZ； int fro

17、nt,rear;,顺序队列约定,设数组维数为M，则： front为队头指针,指示队头元素的前一个位置 rear 为队尾指针,指示队尾元素的位置 初值front=rear=-1 空队列条件：front=rear 入队列： sq+rear=x; rear=rear+1; sqrear=x; 出队列： x=queue+front front = front +1 ；x = queuefront；,顺序队列入队/出队操作,1）空队列 2）A、B、C入队 3）A、B出队 D、E入队,顺序队列入队/出队操作,4）反复出队/入队 假溢出 随着元素不断入队列、出队列，rear和front指针会不断向后移动（如

18、图(2)（3）所示），最终会指向数组的最大下标位置（如图(4)所示）。由于rear和front指针只能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置,这种情况称为假溢出。,顺序队列真假溢出,当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢出 假溢出的解决方法？,当rear = MAXSIZE+1 时，即超过队列末端时， 令rear = 1；从而使队列的首尾相连接。 用表达式描述: if （rear MAXSIZE ） rear = 1 ; else rear = rear + 1 ;,循环队列,基本思

19、想 把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0; 实现 入队 rear=(rear+1)%M; sqrear=x; 出队 front=(front+1)%M; x=sqfront;,循环队列,为了将队空和队满的条件加以区分，一般不使用front指针所指的位置 队空条件为front=rear 队满条件为（rear+1）% M=front,循环队列入队操作,Step1：判别队列是否已满 Step2：队尾指针后移一个位置,将新结点元素值存入当前结点单元,addQueue(int x) if (front = = rear % MAXIZE +1 ) print

20、f(“循环队列已满n”); exit(1); else rear = rear % MAXSIZE +1; queuerear = x ; ,循环队列出队操作,Step1：判别队列是否为空;若空,则显示队列下溢 Step2：队头指针后移一个位置,delqueue( ) int m; if ( front = = rear ) printf( “ 循环队列已空n”) ; m = -1 ； else front = front % MAXSIZE +1 ； m= queuefront ； return m ； ,链队列,链队列实质上就是只能在头部删除元素、只能在尾部插入元素的单链表 队头指针fro

21、nt就是单链表的头指针 队尾指针rear则是指向单链表最后一个结点的指针,存储结构的C语言描述， struct qnode int data ； struct qnode * next； ； typedef struct qnode QNODE ； QNODE *front， *rear；,链队列入队操作,空队 x入队 y入队,Queue.front = Queue.rear,链队列入队操作算法,Step1：申请建立一个新结点T; Step2：判别T是否为空;若空,表示队列已满; Step3：非空,将T插入链中,修改rear指针。,addqueue(int x) QNODE *t; t = (QNODE*)malloc(sizeof(QNODE); if （ t = = NULL） printf（“ 内存无可用空间n”); exit(1); else rear - next = t; rear = t; t -data = x; t -next = NULL ; ,链队列出队操作,x出队 y出队,