ch03 Stack & Queue(USE)

数据结构–DataStructures第三章栈和队列本章内容3.1栈3.1.1栈的定义及基本运算3.1.2栈的存储结构和实现3.1.3栈的应用3.2队列3.2.1队列的定义及基本运算3.2.2队列的存储结构和实现3.2.3队列的应用数据结构–DataStructures3.1.1栈的定义及基本运算栈(Stack)的定义栈是仅限定在表尾进行插入和删除操作的线性表。术语栈顶(top)－－栈的表尾栈底(bottom)－－栈的表头空栈－－没有元素的栈入栈(push)－－向栈顶压入元素出栈(pop)－－从栈顶弹出元素anan-1...a2a1栈底栈顶入栈出栈栈的特点栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。数据结构–DataStructures3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。DCBAABCDDCBA数据结构–DataStructures3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ABCDE操作序列：出栈序列：①元素A入栈AA②元素B入栈BB③元素C入栈CC数据结构–DataStructures3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈B③元素C入栈④元素C出栈CC⑤元素B出栈B数据结构–DataStructures3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈DD⑦元素D出栈D⑧元素A出栈A数据结构–DataStructures3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？E操作序列：出栈序列：①元素A入栈②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈⑦元素D出栈D⑧元素A出栈A⑨元素E入栈EE⑩元素E出栈E数据结构–DataStructures栈的基本运算InitStack(&S):初始化栈SStackEmpty():判断栈是否为空Push(e):将元素e放入栈顶Pop(e):移走栈顶的元素，同时由e带回该元素的值Gettop():获取栈顶的元素，但不从栈中移走3.1.1栈的定义及基本运算数据结构–DataStructures3.1.2栈的表示和实现顺序栈－－栈的顺序存储结构…a1a2an-1an线性表anan-1...a2a1栈栈底栈顶6F28an6F26an-1......6F02a26F00a1栈的顺序存储映象basetop数据结构–DataStructures3.1.2栈的存储结构和实现顺序栈－－栈的顺序存储结构6F28an6F26an-1......6F02a26F00a1栈的顺序存储映象basetop顺序栈基本操作的实现StackEmpty():top==basePush(e):*top++=ePop(e):e=*--topGettop():e=*(top-1)数据结构–DataStructures3.1.2栈的存储结构和实现顺序栈的C语言实现结构定义//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{ElemType*base;//栈底指针，栈构造前和销毁后为空ElemType*top;//栈顶指针，指向栈顶元素的下一位置intstacksize;//当前分配的栈的存储空间数}SqStack;数据结构–DataStructures3.1.2栈的存储结构和实现顺序栈的C语言实现基本操作的实现(1)初始化StatusInitStack(SqStack&S){//构造一个空栈S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack数据结构–DataStructures3.1.2栈的存储结构和实现顺序栈的C语言实现基本操作的实现(2)元素入栈StatusPush(SqStack&S,ElemTypee){//构造一个空栈if(S.top–S.base==S.stacksize)returnERROR;//栈满*S.top=e;S.top++;returnOK;}//Push其它操作的实现算法P47。数据结构–DataStructures3.1.2栈的存储结构和实现链栈－－栈的链式存储anan-1...a2a1栈栈底栈顶…S栈的链式存储anan-1a1^a2思考①链栈是否需要另外设置头指针？②建立链栈适合用哪种插入法？③链栈的基本操作的实现。数据结构–DataStructures3.1.3栈的应用根据栈的FILO特性，用作某些处理问题的工具。数制转换(算法P48)例：4310=1010112被除数除数商余数432211212101102505221221012010输出数据结构–DataStructures3.1.3栈的应用括号匹配设一个表达式中可以包含三种括号：“(”和“)”、“[”和“]”、“{”和“}”，并且这三种括号可以按照任意的次序嵌套使用，考查表达式中的括号是否匹配。例如：...[...{...[...}...]...]...[...]...(...)...)...例：a=b+(c-d)*(e-f));while(m(a[8]+t){m=m+1;t=t-1;}实现方法－－利用栈进行表达式中的括号匹配自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。数据结构–DataStructures3.1.3栈的应用举例迷宫问题寻找一条从入口到出口的通路。8123456781234567入口出口前进方向：上(北)、下(南)、左(西)、右(东)东南北西走步规则：首先从向东开始，按照顺时针方向搜索下一步可能前进的位置数据结构–DataStructures栈3.1.3栈的应用迷宫问题8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i数据结构–DataStructures栈3.1.3栈的应用迷宫问题8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i@@(5,2)i(5,3)i(6,3)i(6,4)i…(8,8)iiiiii数据结构–DataStructures3.1.3栈的应用迷宫问题迷宫的表示constintN=8;structPosType{intx,y;};charmaze[N][N];//位置上的标识，是否可通过迷宫初始化用二层嵌套循环对迷宫赋值迷宫求解(见教材算法)输出栈中的路径数据结构–DataStructures数据结构–DataStructuresStatusMazePath(maze,start,end){//若迷宫中存在一条从入口start到出口end的通道，则求出这样的一条通路InitStack(S);curpos=start;curstep=1;do{if(pass(curpos))//当前位置可以通过｛FootPrint(curpos);//留下记号e=(curstep,curpos,1);push(S,e);//加入路径if(curpos==end)returntrue;//到达出口curpos=NextPos(curpos,1);//下一个位置,东邻curstep++;//探索下一步}else//当前位置不能通过{if(!StackEmpty(S)){pop(S,e);//退回一步while(e.di==4&&!!StackEmpty(S))//当前位置是死胡同{Markdead(e.seat)；pop(S,e);//留下记号，沿来路返回}if(e.di4)//当前位置还有其他方向没有探索，继续试探{e.di++;push(S,e);curpos=NextPos(e.seat,e.di);}}}while(!StackEmpty(S));returnfalse;}数据结构–DataStructures3.2.5表达式求值程序设计语言中都有计算表达式的问题，这是语言编译中的典型问题，是栈的典型应用实例。数据结构–DataStructures4+2*3-10/5=4+6+2=12运算规则先乘除，后加减（四则运算）从左-〉右（+、-、*、/）先括号内，后括号外算符优先法表达式操作数(operand)算符运算符(operator)：+-*/界限符(delimiter)：左右括弧和表达式结束符数据结构–DataStructures根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一：θ1θ2：θ1的优先权低于θ2如+与*θ1=θ2：θ1的优先权等于θ2如+与-（认为θ1θ2）θ1θ2：θ1的优先权高于θ2如*与+数据结构–DataStructures表3-1算符之间的优先关系实现算符优先算法时需要使用两个工作栈：一个称作operator（OPTR），用以存放运算符；另一个称作operand（OPND），用以存放操作数或运算的中间结果。算法的基本过程如下：(1)初始化操作数栈operand和运算符栈operator，并将表达式起始符“＃”压入运算符栈；(2)依次读入表达式中的每个字符:自左向右，栈顶原来的运算符是最优先的运算符操作数，则直接进入操作数栈OPND运算符（现），则与运算符栈OPTR的栈顶运算符（原）进行优先权比较，做如下处理：原现：原现：原=现：现在的运算符入OPTR栈b=pop(OPND);a=pop(OPND);@=pop(OPTR);a@b，并将结果push到OPND左右括号相遇，将OPTR栈顶（左括号）退栈数据结构–DataStructures具体算法：53页输入：3*（7+3*6/2-5#)运算对象栈运算符栈3#*(7+3*618/2916-51133数据结构–DataStructures3.3栈与递归的实现栈非常重要的一个应用是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。数据结构–DataStructures例如，很多数学函数是递归定义的，如二阶Fibonacci数列：数据结构–DataStructures3.3栈与递归的实现当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。数据结构–DataStructures3.3栈与递归的实现从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果;释放被调函数的数据