数据结构-课件第3章栈和队列

3和队两种特殊的线性表——栈和队栈栈栈的逻辑结栈：限定仅在表的一端进行和删除操作的线性允 （a1,a2,……, 栈 栈栈栈栈的逻辑结入入出栈 ：入栈、进栈栈 删除：出栈、弹栈栈栈的逻辑结入入出栈 ：入栈、进栈栈 删除：出栈、弹栈栈的操作特性：后进先栈的逻辑结情况栈栈cba栈cba栈栈栈的逻辑结情况cba出栈序列cba栈栈 出栈序列：c、栈 出栈序列：c、b、栈栈的逻辑结情况ba出栈序列ba栈栈的逻辑结情况ca出栈序列ca栈 出栈序列：b、栈栈 出栈序列：b、c、注注意：栈只是对制，并没有限和删除操作的位置进行了和删除操作进行的时栈的抽象数据类型定ADTStack栈中元素具有相同类型及后进先出特性相邻元素具有前驱和后继关前置条件：栈不输入：后置条件：构造一个空栈的抽象数据类型定后置条件：栈所占用的空功能：在栈顶一个元素输出：如果不成功，抛出异后置条件：如果成功，栈顶增加了一个元栈的抽象数据类型定功能：删除栈输出：如果删除成功，返回被删元素值，否则，抛出异后置条件：如果删除成功，栈减少了一个元功能：当前的栈顶元输出：若栈不空，返回当前的栈顶元素后置条件：栈不栈的抽象数据类型定功能：判断栈是否为输出：如果栈为空，返回1，否则，返回0后置条件：栈不变栈的顺序结构及实顺序栈——栈的顺序结如何改造数组实现栈的顺序012345678确定确定用数组的哪一端表示栈底附设指针top指示栈顶元素在数组中的位置栈的顺序结构及实012345678

进栈：top加进栈：top加栈空：top=-出栈出栈：top减栈满：top=MAX_SIZE-constintMAX_SIZE=100;template<classDataType>classseqStackseqStack()~seqStack(voidPush(DataTypex); Pop(); GetTop();boolEmpty();DataTypedata[MAX_SIZE];inttop;}顺序栈的实现——入操作接口voidPushDataTypextemplate<classvoidseqStack<DataType>::Push(DataType{data[top]=iftopMAX_SIZE-1)throwdata[top]=data[++top]=}时间复杂度顺序栈的实现——出操作接口DataTypePop(template<classDataTypeseqStack<DataType>::Pop({iftop-1)throw“溢出”;x=data[top--];return}时间复杂度两栈共享空两个栈，如何顺序这两个栈？解决方案直接解决：为每个栈开辟一个数组空间顺序栈单向延伸——使用一个数组来两个两栈共享空两栈共享空间：使用一个数组来两个栈，让一个两栈共享空012…S-………栈1

栈2栈1的底固定在下标为0的一端栈2的底固定在下标为StackSize-1的一top1和top2分别为栈1和栈2的栈顶指针Stack_Size为整个数组空间的大小（图中用S表示两栈共享空012…S-………

什么时候栈1

top1=-1两栈共享空012012…S-………什么时候栈2

top1=-1top2=

两栈共享空012…S-…………

什么时候栈1

top1=-什么时候栈2为空 top2=什么时候栈满 top2={BothStack(~BothStack(voidPush(inti,DataTypex);DataTypePop(inti);DataTypeGetTop(inti);boolEmpty(inti);inttop1,top2;两栈共享空间的实现操作接口：voidPush(inti,DataTypex)如果栈满，则抛出上溢异常判断是插在栈1还是栈若在栈1，top1加在top1处填入若在栈2，top2减在top2处填入两栈共享空间的实现——删操作接口：DataTypePop(inti)若是在栈1删除，若栈1为空栈，抛出下溢异删除并返回栈1的栈顶元素若是在栈2若栈2为空栈，抛出下溢异删除并返回栈2的栈顶元素栈的结构及实链栈：栈的结如何改造链表实现栈的∧将哪一端作为栈顶？将链头作为栈顶，方便操作链栈需要加头结点吗？链栈不需要附设头结栈的结构及实链栈：栈 结∧an-an-栈

栈an-∧∧an-∧∧应同一种状态栈template<classDataType>classLinkStackLinkStack(~LinkStack(voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();Node<DataType>}链栈的实现template<classvoidtemplate<classvoidLinkStack<DataType>::Push(DataType{s=newNode<DataType>;s->data=x;s->next=top=}xaan-∧为什么没有判断栈满∧链栈的实现操作接口DataTypePoptemplate<class

DataTypeLinkStack<DataType>::Pop({an-if(topNULL)throw"an-x=top-p=∧top=top-∧deletep;returnx;}top++可以吗顺序栈和链栈的比顺序栈：有元素个数的限制和空间浪费的问题队队列队队列的逻辑结 （a1,a2,……,队 队出出a1a2a入3队队队队队列的操作特性：先进先队队队列的抽象数据类型定ADTQueue相邻元素具有前驱和后继关系后置条件：创建一个空队队列的抽象数据类型定后置条件：队列所占用的空功能：在队入一个元输出：如果不成功，抛出异后置条件：如果成功，队尾增加了一个元队列的抽象数据类型定功能：删除队头元输出：如果删除成功，返回被删元素后置条件：如果删除成功，队头减少了一个元前置条件：队列已存输入：功能：队头元队列的抽象数据类型定功能：判断队列是否为输出：如果队列为空，返回1，否则，返回后置条件：队列不变队列的顺序结构及实顺序队列——队列的顺序结出 入入队操作时间性能为队列的顺序结构及实如何改造数组实现队列的顺序？出 队列的顺序结构及实如何改造数组实现队列的顺序？出 队列的顺序结构及实如何改造数组实现队列的顺序？出 入出出队操作时间性能为队列的顺序结构及实如何改进出队的时间性能放宽队放宽队列的所有元素必条件，只要求队列的元在数组的前n个单元这在数组中连续的位置设置队头、队尾两个指队列的顺序结构及实例：a1a2a3a4依次出

队尾指针rear入入队操作时间性能仍为队列的顺序结构及实例：a1a2依次出出 frontfront 出出队操作时间性能提高为队列的顺序结构及实例：a1a2依次出出 入 队列的移动有什么特点队列的顺序结构及实例：a1a2依次出出 入 整个队整个队列向数组下标较大单向移动队列的顺序结构及实继续入队会出现什么情况出 入

假溢出：假溢出：后，队列的空间就用尽了，尽管此时数组 还队列的顺序结构及实如何解决假溢出01234入01234入

循环队列：将队列的数组头尾相接队列的顺序结构及实如何实现循环队出 不不存在物理的循环结构，求模：（4＋1）mod方法实队列的顺序结构及实出 入 队列的顺序结构及实出 入frontfront队队空队列的顺序结构及实出

队列的顺序结构及实出

队列的顺序结构及实为什么要将队空和队满的判定条件分开方法二：附设一个队列中元素个数的变量num，方法三：设置标志flag，当front=rear且flag=0时为队队列的顺序结构及实现(队满用方法一判断

入

入 队队满的条件：(rear+1mod{CirQueue(~CirQueue(voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();boolEmpty()；intfront,rear;循环队列的实现——入template<classvoidCirQueue<DataType>::EnQueue(DataType{if((rear+1QueueSizefrontthrow上溢";rear=(rear+1%QueueSize;data[rear]=}出 入

循环队列的实现——出template<classDataTypeCirQueue<DataType>::DeQueue({if(rear==front)throw"下溢";frontfront1)QueueSize;returndata[front];}出

循环队列的实现——读队头元template<classDataTypeCirQueue<DataType>::GetQueue({ifrearfront)throw下溢";i=(front+1)%QueueSize;returndata[i];}出

队列的结构及实链队列：队列的结如何改造单链表实现队列 ∧∧

队列的结构及实非空链队∧∧空链队∧∧template<classDataType>classLinkQueueLinkQueue(~LinkQueue(voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue()；boolEmpty()；链队列的实现——构造函操作接口LinkQueue(算法描述template<classDataType>LinkQueue<DataType>::LinkQueue(){front=newfront->next=NULL;rear=front;

∧∧}链队列的实现——入∧x∧操作接口voidEnQueue(DataTypex);∧x∧如何没有头结点会怎样

rear

∧

∧∧xrear

算法描述链队列的实现——入∧x∧操作接口voidEnQueue(DataType∧x∧如何没有头结点会怎样

rear算法描述链队列的实现——入如何没有头结点会怎样

∧xrear∧x算法描述

算法描述链队列的实现——入template<class{s=news->data=s->next=NULL;rear->next=s;rear=s;}链队列的实现——出p∧∧算法描述链队列的实现——出p∧∧考虑边界情况：队列中只有一个元素

如何判断边界情∧∧算法∧∧if(p->next==NULL)rear=front;链队列的实现——出template<class{ifrearfront)throw下溢p=front->next;x=p->data;front->next=p-if(p->next==NULL)rear=deletep;returnx;}队队循环队列和链队列的比时间性能循环队列和链队列的基本操作都需要常数时间O(1)。循环队列：必须预先确定一个固定的长度，所以有元素个数的限制和空间浪费的问题链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一应用举栈应用的典型例——表达式求值的实递迷宫求队列的应——打印三角表达式求值算表达式都是由操作数（opnd）运算符（oor）和界限符（dliir）组成的。简单算术表达式的求值问题——四则运算，所有的运算对象均为数，并以“#”为结束符常用算法——算符优先法就是根据运算符和界限符的优先次序的规定来实现达式求值的算术四则运算规则——先乘除从左算到右先括号中缀(infix)<操作数操作符><操作数>，前缀(prefix)表示——波兰式表<操作符操作数操作数>，后缀(postfix)表示——逆波兰式表<操作数操作数><操作符>，中缀表达式和后缀表达1)X- 2)5+(6-（字母表示运算数1) 2)5642/-中缀到后中缀5+(6-到后缀5642/-3*+的转5(6-4/2)*3+ 5(6-4/2)→564/2- 5642/-后缀表达式的作去掉中缀表达式的括隐含中缀表达式的运算次其右边最接近运算符的先算的次序算结果放回原处

/3*/3*计算过

5642/-3* 562–3*543* 512 ←最后结应用后缀表示计算表达式的从左向右顺序地扫描表达式，并用一个栈暂在后缀表达式的计算顺序中已隐含了加括号

/3*利用栈的计算后缀表达式的过栈55642/-3*5265345545 265345545结后缀表达式计算器的实classCalculator{Calculator(intsz=20):s(sz){};voidRun();//计算表达式voidClear();//清空计算器voidAddOperand(doublevalue);//操作数入栈BooleanGet2Operands(double&left,double& voidDoOperator(charop);//根据运算符计算，结果入Stack<double>s;//voidCalculator::AddOperand(doublevalue){s.Push(value);//操作数入栈}BooleanCalculator::Get2Operands(double&left,double&cerr<<"Missingreturn}cerr<<"MissingOperand!"<<endl;returnFalse;}returnTrue;}doubleleft,right;Booleanresult;case'+':s.Push(left+right);break;case'-':s.Push(left-right);break;case'*':s.Push(left*right);break;casecerr<<"Dividedby0!"<<endl; elses.Push(left/right);break;case'^':s.Push(pow(left,right));}elsevoidcharch; case'+':case'-':case'*':case'/‘:case'^':DoOperator(ch);break;default:cin.putback(ch);}}assert(!s.Empty());//若栈底无数，错误！终cout<<"Theresult//输出结果（栈底元素}void}voidCalculatorcal(10);}中缀表达式转换为后缀表达建立运算符栈,并向栈底压入#(若表达式以#结束从左向右依次读入表达如果是运算数,则输如果是操作符则按下面操运算符出栈输出直至栈顶运算符优先级低于栈外运算符,栈外运算符如栈.当栈外为),栈内运算符退至(为当栈外为#,栈内运算符退至#为算符优先关算符——根据前述算术四则运算三条规则，在运算的每一步中，任意两个相继出现的算符p和p2之间的优先关系至多是下面三种关系之一:op1<op2op1的优先权低于op2op1=op2op1的优先权等于op2op1>op2op1的优先权高于算符间的优先级关算符θ1在算符θ2前面。在算法中，相对应于θ1在栈内，θ2+—*/()#+>><<<>>—>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=利用栈的转换过5+(6–4/2)* 5642/-3*)/-(+#+#(+#-)/-(+#+#(+#-(+#/-(+#*+##*+#+##中缀表达式求值将前面中缀表达式转后缀表达式，及后缀表达式计算两过程结合起来，利用所给的+、-、*、/、（、）、和#的算术运算符间的优先级的关系，可计算中缀表达式。设置两个栈操作数栈（OPRD）。运算符栈（OPTR）。#首先在运算符栈中先在栈底压入一个表达式的结束符#

表表达式求值算计算表达式:5+(6-4/2)*3#的过程↑首先在运算符栈中先在栈底压入一个表达式

#运算数#

算符表表达式求值算计算表达式:5+(6-4/2)*3#的过程↑表达式第一个字符，是数，压入运算数

5运算数5

#算符#表达式第2个字符优先级：“+”>“#

5运算数5

+#算符+#表表达式求值算计算表达式5642*3的过↑表达式第3个字符优先级：在栈外“(”>“+

5运算数5

(+#算(+#计算表达式5642*3的过↑表达式第4个字符65(+65(+#

运算数

算符计算表达式5642*3的过↑表达式第5个字符优先级：在栈外“–”>栈内“(

65运算数65

—(+#—(+#计算表达式564/2*3的过↑表达式第6个字符

465运算465

—(+#—(+#计算表达式564/2*3的过↑表达式第7个字符优先级：在栈外“/”>栈内“–

465运算465

/—(+/—(+#计算表达式5642*3的过↑表达式第8个字符

2465运2465

/—(+/—(+#计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算2465/—(2465/—(+#

运算数

算符计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算2465/—(2465/—(+#

运算数

算符计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算65—(+#直至65—(+#

4/2=

运算数

算符计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算265—(+#265—(+#

运算数

算符计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算5(+#直至5(+#

6－2=

运算数

算符计算表达式5642*3的过↑表达式第9个字符优先级：在栈外“)”<栈内任何算法，算符出栈计算45(+#直至45(+#

运算数

算符计算表达式5642*3的过↑表达式第10个字优先级：在栈外“*”>栈内“+”，算符“*”入

45运算数45

*+#算*+#计算表达式5642*3#的过↑表达式第11个字运算数“3

345运算345

*+#算*+#计算表达式5642*3#的过↑表达式第12个字优先级：在栈外“#”<栈内“*”，“*”出栈计

345运算345

*+#算*+#计算表达式5642*3#的过↑表达式第12个字优先级：在栈外“#”<栈内“