-第三章栈和队列课件.ppt

1、?栈的概念栈的概念栈的存储结构栈的存储结构栈的操作算法栈的操作算法栈的应用栈的应用队列的概念队列的概念队列的存储结构与操作算法队列的存储结构与操作算法队列的操作算法队列的操作算法队列的应用队列的应用3.1 栈栈(Stack)的概念的概念?只允许在一端插入和删除的表?允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)?特点后进先出(LIFO)进栈示例进栈示例出栈示例出栈示例?例例:?假定有4个元素A，B，C，D，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后都允许出栈，如ACDB就是一种出栈序列。?解：可能的出栈序列有ABCD，ABDC，ACBD，ACDB，

2、ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。栈的基本操作1、初始化、初始化2、进栈、进栈PUSH3、出栈、出栈POP4、取栈顶元素、取栈顶元素GetTop5、判栈是否非空、判栈是否非空3.2 栈的存储结构栈的存储结构顺序存储顺序存储-顺序栈顺序栈链式存储链式存储-链栈链栈?template class SeqStackT dataMaxSize;/存放栈元素存放栈元素int top;/栈顶指针栈顶指针public:SeqStack();/构造函数构造函数void Push(T x);/入栈入栈T Pop();/出栈出栈T Top();/取

3、栈顶元素取栈顶元素bool Empty();/判断栈是否为空判断栈是否为空;链式栈的存储?链式栈无栈满问题，空间可扩充?插入与删除仅在栈顶处执行?链式栈的栈顶在链头?template class LinkStackNode*top;/栈顶指针public:LinkStack();/构造函数LinkStack();/析构函数void Push(T x);/入栈T Pop();/出栈T Top();/取栈顶元素bool Empty();/判断链栈是否为空栈;3.3 栈的操作算法栈的操作算法?1.顺序栈的操作算法顺序栈的操作算法?2.链式栈的操作算法链式栈的操作算法1 顺序栈的操作算法顺序栈的操作算

4、法(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=

5、-1)cerr 下溢;exit(1);return datatop;(5)判断顺序栈是否为空判断顺序栈是否为空?template bool SeqStack:Empty()return top=-1;2 链栈的操作算法链栈的操作算法?(6)链栈初始化链栈初始化?template LinkStack:LinkStack()top=NULL;(7)链栈入栈操作链栈入栈操作(8)template void LinkStack:Push(T x)s=new Node;s-data=x;s-next=top;top=s;(8)链栈出栈操作链栈出栈操作template T LinkStack:Pop()i

6、f(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)(11)链栈的析构函数链栈的析构函数template LinkStack:LinkStack()p=top;while(p)q=p;p=p-next;delete q;top=NULL;思考：两个栈共享同一段内容

7、空间，为了使得空思考：两个栈共享同一段内容空间，为了使得空间利用率最高，应如何分配栈空间？间利用率最高，应如何分配栈空间？-两个堆栈共享空间0maxsize-1lefttoprighttop3.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.栈的应用之二栈的应用之二:算术表达式求值算术表达式求值

8、表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观的算法，即的算法，即“算符优先法算符优先法”。输入包含+、*、/、圆括号和正整数组成的中缀算术表达式，以“”“”作为表达式结束符。计算该表达作为表达式结束符。计算该表达式的运算结果。运算优先级运算优先级当前运算符()(=栈顶运算符算法思想：算法思想：为实现算符优先算法，使用两个工作栈为实现算符优先算法，使用两个工作栈。1.运算符运算符OPTR栈栈,用以寄存运算符；用以寄存运算符；2.操作数操作数OPND栈栈,用以寄存操作数用以寄存操作数或运算结果或运算结果。?（1）首先置操作数栈）首先置操作数栈OPN

9、D为空栈，表达为空栈，表达式起始符式起始符“”“”为运算符的栈底元素；为运算符的栈底元素；?（2）从左到右扫描，依次读入中缀表达）从左到右扫描，依次读入中缀表达式中的每个字符，依次读入表达式中每个式中的每个字符，依次读入表达式中每个字符字符,若是操作数若是操作数,则进则进OPND栈，若是运算栈，若是运算符，则与符，则与OPTR栈的栈顶运算符进行比较，栈的栈顶运算符进行比较，作相应操作，直至整个表达式求值完毕作相应操作，直至整个表达式求值完毕（即（即OPTR栈的栈顶元素和当前读入的字栈的栈顶元素和当前读入的字符均为符均为“”“”）。）。?若读到的是操作符（若读到的是操作符（c），则应与操作符），

10、则应与操作符栈的栈顶元素（栈的栈顶元素（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!=|OPT

11、R.Top()!=)?if(!InOPTR(ch,OP)?OPND.Push(ch);ch=getchar();?/读到的是操作数则入栈读到的是操作数则入栈?else /读到的是操作符读到的是操作符?pre_op=OPTR.Top();?switch(Precede(pre_op,ch)?case:/情况情况?b=OPND.Pop();a=OPND.Pop();?pre_op=OPTR.Pop();?OPND.Push(Operate(a,pre_op,b);?break;?return OPND.Top();后缀表达式求值后缀表达式求值?中缀表达式中缀表达式?后缀表达式后缀表达式?求值求值?

12、将中缀表达式变成等价的后缀表达式时，表将中缀表达式变成等价的后缀表达式时，表达式中操作数次序不变，而操作符次序会发达式中操作数次序不变，而操作符次序会发生变化，同时去掉圆括号。因此设置一个栈生变化，同时去掉圆括号。因此设置一个栈OPTR用以存放操作符。用以存放操作符。?中缀表达式转换为后缀表达式的基本思路中缀表达式转换为后缀表达式的基本思路:?从左到右扫描中缀表达式，依次读入表达从左到右扫描中缀表达式，依次读入表达式中的每个字符，对于不同类型的字符按不式中的每个字符，对于不同类型的字符按不情况进行处理。情况进行处理。?若读到的是操作数，则输出该操作数，并若读到的是操作数，则输出该操作数，并读入

13、下一个字符。读入下一个字符。?若读到的是左括号，则把它压入到若读到的是左括号，则把它压入到OPTR栈栈中，并读入下一个字符。中，并读入下一个字符。?若读到的是右括号，则表明括号内的中缀若读到的是右括号，则表明括号内的中缀表达式已经扫描完毕，将表达式已经扫描完毕，将OPTR栈从栈顶顶直栈从栈顶顶直到左括号之前的操作符依次出栈并输出，然到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。后将左括号也出栈，并读入下一个字符。?若读到的是操作符（若读到的是操作符（c），则应与操作符栈），则应与操作符栈的栈顶元素（的栈顶元素（pre_op）进行比较：）进行比较：?若若cpre_op

14、，则将，则将c入栈，并读下一个字符入栈，并读下一个字符;?若若c=pre_op，则将，则将pre_op出栈并输出。出栈并输出。?按照以上过程扫描到中缀表达式结束符时，按照以上过程扫描到中缀表达式结束符时，把栈中剩余的操作符依次出栈并输出，就得把栈中剩余的操作符依次出栈并输出，就得到了转换后的到了转换后的后缀表达式后缀表达式。?书中例子书中例子:?后缀表达式求值时，不需要再考虑操作后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈缀表达式即可。可设置一个栈OPND用以用以存放操作数。存放操作数。?后缀表达式求值算法的基

15、本思路后缀表达式求值算法的基本思路：?从左到右扫描，依次读入表达式中的每从左到右扫描，依次读入表达式中的每个字符，直至表达式结束。个字符，直至表达式结束。?若读到的是操作数，则入栈若读到的是操作数，则入栈OPND。?若读到的是操作符，则在若读到的是操作符，则在OPND栈中栈中退出退出2个元素（先退出的在操作符右，后个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符退出的在操作符左），然后用该操作符进行运算，并将运算结果压入进行运算，并将运算结果压入OPND栈中。栈中。?后缀表达式扫描完毕时，后缀表达式扫描完毕时，OPND栈中仅有栈中仅有一个元素，即为运算的结果一个元素，即为运算的

16、结果。?书中例子书中例子:3.5 队列(Queue)的概念?定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。?特性先进先出(FIFO,First In First Out)队列的基本操作1、构造一个队列、构造一个队列2、进队操作、进队操作-将新元素插入队尾将新元素插入队尾3、出队操作、出队操作-队列头元素出队队列头元素出队4、取队列头元素、取队列头元素5、判定队列是否为空、判定队列是否为空3.6 队列的存储结构?顺序存储顺序存储-循环队列循环队列?链式存储链式存储-链队链队?思考:为什么要构造循环队列?1队列的顺序存储结

17、构队列的顺序存储结构?template class SeqQueueT data MaxSize;/存放队列元素存放队列元素int front,rear;/队头和队尾指针队头和队尾指针public:SeqQueue();/构造函数，置空队构造函数，置空队void EnQueue(T x);/将元素将元素x入队入队T DeQueue();/将队头元素出队将队头元素出队T GetQueue();/取队头元素取队头元素bool Empty();/判断队列是否为空判断队列是否为空;?进队时队尾指针 rear=rear+1，将新元素按rear指示位置加入。?出队时队头指针 front=front+1，再

18、将下标为front 的元素取出。?思考：上图中，元素再进队，将如何？思考：上图中，元素再进队，将如何？出现出现“假上溢假上溢”现象现象?解决办法解决办法:?将存储数据元素的一维数组看成是头尾将存储数据元素的一维数组看成是头尾相接的循环结构相接的循环结构?即即循环队列循环队列循环队列的进队和出队循环队列的进队和出队队头指针队头指针:front=(front+1)%maxSize;队尾指针队尾指针:rear=(rear+1)%maxSize;队列初始化：队列初始化：front=rear=0;循环队列的队空队满问题循环队列的队空队满问题为了方便起见，约定：为了方便起见，约定：初始化建空队时，令初始化

19、建空队时，令front=rear=0,?当队空时：当队空时：front=rear?当队满时：当队满时：front=rear 亦成立亦成立?因此，只凭等式因此，只凭等式front=rear?无法判断队空还是队满。无法判断队空还是队满。?有三种方法处理上述问题：有三种方法处理上述问题：?浪费一个单元。当使用浪费一个单元。当使用MaxSize-1个单元个单元时即认为是队满时即认为是队满,此时此时(rear+1)%MaxSize=front?设置一个布尔变量设置一个布尔变量flag。当。当flag=flase时为时为空，当空，当flag=true时为满。时为满。?使用一个计数器记录队列中元素的个数。使

20、用一个计数器记录队列中元素的个数。如如num，当，当num=0时队空，时队空，当当num=MaxSize时队满。时队满。2队列的链式存储结构队列的链式存储结构?template?class LinkQueue?private:?Node*front,*rear;?public:?LinkQueue();/构造函数构造函数?LinkQueue();/析构函数析构函数?void EnQueue(T x);/将元素将元素x入队入队?T DeQueue();/将队头元素出队将队头元素出队?T GetQueue();/取链队列的队头元素取链队列的队头元素?bool Empty();/判断链队列是否为空判

21、断链队列是否为空?;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）循环队列的出队操作）循

22、环队列的出队操作?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）链队列入队操作）链队列入队操作?

23、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）问题描述）问题描

24、述?设有设有n个人排成一列，从前往后个人排成一列，从前往后“0，1”连续报连续报数。凡是报到数。凡是报到“0”的人出列，凡是报到的人出列，凡是报到“1”的的人立即站到队伍的最后。反复进行报数，直到人立即站到队伍的最后。反复进行报数，直到所有人均出列为止。要求给出这所有人均出列为止。要求给出这n个人的出列个人的出列顺序。顺序。?例如，例如，n=5时，初始序列为时，初始序列为1、2、3、4、5，?出队序列为出队序列为1、3、5、4、2。（2）数据结构的设计）数据结构的设计将将n个人排成的队伍用队列模拟。个人排成的队伍用队列模拟。采用链队列存储结构。采用链队列存储结构。?（3）算法的设计）算法的设计

25、?实质上是一个反复出队和入队的问题，实质上是一个反复出队和入队的问题，即凡是报到即凡是报到“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）掌握栈和队列的应用。）掌握栈和队列的应用。