739第三章 栈和队列.ppt

栈的概念栈的存储结构栈的操作算法栈的应用队列的概念队列的存储结构与操作算法队列的操作算法队列的应用,第三章 栈和队列,3.1 栈(Stack)的概念,只允许在一端插入和删除的表允许插入和删除 的一端称为栈顶(top)，另一端称 为栈底(bottom)特点 后进先出(LIFO),进栈示例,出栈示例,例:假定有4个元素A，B，C，D，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如ACDB就是一种出栈序列。解：可能的出栈序列有ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。,栈的基本操作,1、初始化2、进栈PUSH3、出栈POP4、取栈顶元素GetTop5、判栈是否非空,3.2 栈的存储结构,顺序存储-顺序栈链式存储-链栈,template class SeqStack T dataMaxSize;/存放栈元素 int top;/栈顶指针public:SeqStack();/构造函数 void Push(T x);/入栈 T Pop();/出栈 T Top();/取栈顶元素 bool Empty();/判断栈是否为空;,链式栈的存储,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头,template class LinkStack Node*top;/栈顶指针public:LinkStack();/构造函数 LinkStack();/析构函数 void Push(T x);/入栈 T Pop();/出栈 T Top();/取栈顶元素 bool Empty();/判断链栈是否为空栈;,3.3 栈的操作算法,1.顺序栈的操作算法2.链式栈的操作算法,1 顺序栈的操作算法,顺序栈的初始化 template SeqStack:SeqStack()top=-1;,(2)顺序栈的入栈操作,template void SeqStack:Push(T x)if(top=MaxSize-1)cerr上溢;exit(1);top+;datatop=x;,(3)顺序栈的出栈操作,template T SeqStack:Pop()if(top=-1)cerr下溢;exit(1);x=datatop;top-;return x;,(4)取栈顶元素操作,template T SeqStack:Top()if(top=-1)cerr下溢;exit(1);return datatop;,(5)判断顺序栈是否为空,template bool SeqStack:Empty()return top=-1;,2 链栈的操作算法,(6)链栈初始化 template LinkStack:LinkStack()top=NULL;,链栈入栈操作 template void LinkStack:Push(T x)s=new Node;s-data=x;s-next=top;top=s;,(8)链栈出栈操作template T LinkStack:Pop()if(top=NULL)cerrdata;p=top;top=top-next;delete p;return x;,(9)取栈顶元素操作,template T LinkStack:Top()if(top=NULL)cerrdata;,(10)判断链栈是否为空,template bool LinkStack:Empty()return top=NULL;,(11)链栈的析构函数template LinkStack:LinkStack()p=top;while(p)q=p;p=p-next;delete q;top=NULL;,思考：两个栈共享同一段内容空间，为了使得空间利用率最高，应如何分配栈空间？-两个堆栈共享空间,0,maxsize-1,lefttop,righttop,3.4 栈的应用举例1.栈的应用之一:递归调用例:Hanoi塔问题.void Hanoi(int n,char a,char b,char c)if(n=1)Move(a,c);else Hanoi(n-1,a,c,b);Move(a,c);Hanoi(n-1,b,a,c);一定要搞清执行过程,2.栈的应用之二:算术表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观的算法，即“算符优先法”。输入包含+、*、/、圆括号和正整数组成的中缀算术表达式，以“”作为表达式结束符。计算该表达式的运算结果。,运算优先级,当前运算符,栈顶运算符,算法思想：为实现算符优先算法，使用两个工作栈。1.运算符OPTR栈,用以寄存运算符；2.操作数OPND栈,用以寄存操作数 或运算结果。,（1）首先置操作数栈OPND为空栈，表达式起始符“”为运算符的栈底元素；（2）从左到右扫描，依次读入中缀表达式中的每个字符，依次读入表达式中每个字符,若是操作数,则进OPND栈，若是运算符，则与OPTR栈的栈顶运算符进行比较，作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“”）。,若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）进行比较，会出现以下三种情况：若pre_opc，则pre_op出栈，并在操作数栈中退栈2次，依次得到操作数b和a，然后进行a pre_op b运算，并将运算的结果压入操作数栈中。(举例),算法描述,double Expression_Eval()SeqStack OPTR;/运算符栈SeqStack OPND;/运算数栈OPTR.Push();ch=getchar();,while(ch!=|OPTR.Top()!=)if(!InOPTR(ch,OP)OPND.Push(ch);ch=getchar();/读到的是操作数则入栈else/读到的是操作符 pre_op=OPTR.Top();switch(Precede(pre_op,ch)case:/情况 OPTR.Push(ch);ch=getchar();break;,case=:/情况OPTR.Pop();ch=getchar();break;case:/情况b=OPND.Pop();a=OPND.Pop();pre_op=OPTR.Pop();OPND.Push(Operate(a,pre_op,b);break;return OPND.Top();,后缀表达式求值,中缀表达式后缀表达式求值将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发生变化，同时去掉圆括号。因此设置一个栈OPTR用以存放操作符。,中缀表达式转换为后缀表达式的基本思路:从左到右扫描中缀表达式，依次读入表达式中的每个字符，对于不同类型的字符按不情况进行处理。若读到的是操作数，则输出该操作数，并读入下一个字符。若读到的是左括号，则把它压入到OPTR栈中，并读入下一个字符。若读到的是右括号，则表明括号内的中缀表达式已经扫描完毕，将OPTR栈从栈顶顶直到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。,若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）进行比较：若cpre_op，则将c入栈，并读下一个字符;若c=pre_op，则将pre_op出栈并输出。按照以上过程扫描到中缀表达式结束符时，把栈中剩余的操作符依次出栈并输出，就得到了转换后的后缀表达式。书中例子:,后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈OPND用以存放操作数。后缀表达式求值算法的基本思路：从左到右扫描，依次读入表达式中的每个字符，直至表达式结束。,若读到的是操作数，则入栈OPND。若读到的是操作符，则在OPND栈中退出2个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符进行运算，并将运算结果压入OPND栈中。后缀表达式扫描完毕时，OPND栈中仅有一个元素，即为运算的结果。书中例子:,3.5 队列(Queue)的概念,定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out),队列的基本操作,1、构造一个队列2、进队操作-将新元素插入队尾3、出队操作-队列头元素出队4、取队列头元素5、判定队列是否为空,3.6 队列的存储结构,顺序存储-循环队列链式存储-链队思考:为什么要构造循环队列?,template class SeqQueue T data MaxSize;/存放队列元素 int front,rear;/队头和队尾指针public:SeqQueue();/构造函数，置空队 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队 T GetQueue();/取队头元素 bool Empty();/判断队列是否为空;,1队列的顺序存储结构,进队时队尾指针 rear=rear+1，将新元素按 rear 指示位置加入。出队时队头指针 front=front+1，再将下标为 front 的元素取出。思考：上图中，元素再进队，将如何？,出现“假上溢”现象,解决办法:将存储数据元素的一维数组看成是头尾相接的循环结构即循环队列,循环队列的进队和出队,队头指针:front=(front+1)%maxSize;队尾指针:rear=(rear+1)%maxSize;队列初始化：front=rear=0;,循环队列的队空队满问题,为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear 当队满时：front=rear 亦成立 因此，只凭等式front=rear 无法判断队空还是队满。,有三种方法处理上述问题：,浪费一个单元。当使用MaxSize-1个单元时即认为是队满,此时(rear+1)%MaxSize=front 设置一个布尔变量flag。当flag=flase时为空，当flag=true时为满。使用一个计数器记录队列中元素的个数。如num，当num=0时队空，当num=MaxSize时队满。,2队列的链式存储结构,template class LinkQueueprivate:Node*front,*rear;public:LinkQueue();/构造函数 LinkQueue();/析构函数 void EnQueue(T x);/将元素x入队 T DeQueue();/将队头元素出队 T GetQueue();/取链队列的队头元素 bool Empty();/判断链队列是否为空;,3.7 队列的操作算法,1循环队列的操作 2链队列的操作,1循环队列的操作,（1）循环队列的初始化template SeqQueue:SeqQueue()front=rear=0;,（2）循环队列的入队操作template void SeqQueue:EnQueue(T x)if(rear+1)%MaxSize=front)cerr上溢;exit(1);rear=(rear+1)%MaxSize;datarear=x;队尾处插入元素,（3）循环队列的出队操作,template T SeqQueue:DeQueue()if(rear=front)cerr下溢;exit(1);front=(front+1)%MaxSize;return datafront;,（4）判断循环队列是否为空,template bool SeqQueue:Empty()return rear=front;,2链队列的操作,(1)链队列的初始化 template LinkQueue:LinkQueue()s=new Node;s-next=NULL;front=rear=s;,（2）链队列入队操作,template void LinkQueue:EnQueue(T x)s=new Node;s-data=x;s-next=NULL;rear-next=s;/将结点s插入到队尾rear=s;/将队尾指针指向结点s,(3)链队列的出队操作,template T LinkQueue:DeQueue()if(rear=front)cerrnext;x=p-data;front-next=p-next;if(p-next=NULL)rear=front;delete p;return x;,3.8 队列的应用示例,（1）问题描述设有n个人排成一列，从前往后“0，1”连续报数。凡是报到“0”的人出列，凡是报到“1”的人立即站到队伍的最后。反复进行报数，直到所有人均出列为止。要求给出这n个人的出列顺序。例如，n=5时，初始序列为1、2、3、4、5，出队序列为1、3、5、4、2。,（2）数据结构的设计 将n个人排成的队伍用队列模拟。采用链队列存储结构。,（3）算法的设计 实质上是一个反复出队和入队的问题，即凡是报到“0”的人出列，凡是报到“1”的人入队，直至队列为空。,算法的基本思想是：反复执行以下步骤，直至队列为空。将队头元素出队，并输出其编号。若队列不空，则再出队一个元素，并将该元素再次入队。,void Number()LinkQueue linkq;for(i=1;i=n;i+)linkq.EnQueue(i);while(!linkq.Empty()x=linkq.DeQueue();coutx;/报到0的人出列if(!linkq.Empty()/报到“1”的人到队伍的最后y=linkq.DeQueue();linkq.EnQueue(y);,本 章 小 结,（1）理解栈和队列的特点及它们的差异。（2）掌握顺序栈和链栈的定义及操作。（3）掌握循环队列和链队列的定义及操作。（4）掌握栈和队列的应用。,