栈和队列的详细讲解

14.1栈4.2栈的实现4.3栈的应用4.4队列4.5队列的实现4.6队列的应用栈和队列是运算受限的线性表。第四章栈与队列23.1栈3.1.1栈的概念及运算3.1.2顺序栈3.1.3链栈33.1.1栈的概念及运算栈限制仅在一端进行插入和删除运算的线性表栈顶进行插入、删除的一端栈底栈顶栈底进栈退栈a2a1an...栈是后进先出表（LIFO表）4（1）置空栈createEmptyStack(void)：空栈；（2）判栈空isEmptytack（st）：这是一个布尔函数。若st为空栈，则函数值为“真”,否则为“假”。（3）进栈push（st，x）：在st的顶部插入(亦称压入）元素x。（4）退栈pop（st）：删除（亦称弹出）栈st的顶部元素。（5）取栈顶top（st）：取栈st的顶部元素。栈的五种基本运算3.1.1栈的概念及运算53.1.2顺序栈栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。#defineMAXNUM100/*栈中能达到的最大容量*/typedefintDataType;/*定义栈元素的数据类型*/structSeqStack/*顺序栈类型定义*/{DataTypes[MAXNUM];intt;/*栈顶*/}；typedefstructSeqStack,*PSeqStack;PSeqStackpastack;/*指向顺序栈的指针变量*/6注意:t是int型简单变量,指向栈顶元素在栈中的位置(序号)约定:1、栈空时，t=-12、栈满时，t=MAXNUM-13、栈顶元素：S[t]4、若t=-1时，执行pop,产生“下溢”5、若t=MAXNUM-1时，执行push,产生“上溢”76543210-1ABCD进栈和退栈3.1.2顺序栈83.1.2顺序栈（1）置空栈（2）判栈空（3）进栈（4）退栈（5）取栈顶在顺序栈下实现栈的五种基本运算当程序中同时使用两个栈时，可共享存储空间。91.置空栈（算法4.1）PSeqStackcreateEmptyStack_seq(void){PSeqStackpastack;pastack=malloc(sizeof(structSeqStack));if(pastack==NULL)printf(“outofspace!\n”);elsepastack-t=-1;returnpastack;}/*SETNULL*/102.判栈空（算法4.2）intisEmptyStack_seq(pastack)PSeqStackpastack;{if(pastack-t=0)returnFALSE;elsereturnTRUE;}113.进栈（算法4.3）先修改t值，再放入数据t++s[t]=x(*pastack).t++(*pastack).s[(*pastack).t]=xpush_seq(pastack,x)12push_seq(pastack,x)PSeqStackpastack;datatypex;{if(pastack-t==MAXNUM-1)print(“overflow”);else{pastack-t++;pastack-s[pastack-t]=x;}}/*push_seq*/3.进栈（算法4.3）134.退栈（算法4.4）pop_seq(pastack)修改t值t--pastack-t--14pop_seq(pastack)PSeqStackpastack;{if(pastack-t==-1)print(“underflow”);elsepastack-t--;}/*pop_seq*/4.退栈（算法4.4）155.取栈顶元素（算法4.5）datatypetop_seq(pastack)PSeqStackpastack;{if(pastack-t==-1){print(“stackisempty”);returnNULL;}elsereturn(pastack-s[pastack-t];}/*top_seq*/16多个栈共享存储空间……...栈1栈2栈1底栈1顶栈2底栈2顶让多个栈共享存储空间，可以相互调节余缺，节约存储空间，降低发生上溢的概率。17多个栈共享存储空间多栈共享：采用链栈Typedefstruct{datatypes[MAXNUM];inttop1,top2;}DStack;Push(x,i)Pop(i)183.1.3链栈栈的链式存储结构称为链栈。它是运算受限的单链表。由于只能在链表头部进行操作，故链栈没有必要象单链表那样需附加头结点。栈顶指针top就是链表的头指针head。19typedefintDataType;structNode;typedefstructNode*pNode;structNode/*单链表结点结构*/{DataTypeinfo;pNodelink;};structLinkStack/*链接栈类型定义*/{pNodetop;/*指向栈顶结点*/};typedefstructLinkStack*PLinkStack;3.1.3链栈pLinkstackplstack;/*变量声明*/^plstacktopinfolink栈的链接表示213.1.3链栈相当于链表在top结点前插入出栈相当于链表在将top结点删除进栈22voidpush_link(PLinkStackplstack,DataTypex)/*在栈中压入一元素x*/{PNodep;p=(PNode)malloc(sizeof(structNode));if(p==NULL)printf(Outofspace!\n);else{p-info=x;p-link=plstack-top;plstack-top=p;}}进栈算法（算法4.8）23voidpop_link(PLinkStackplstack){PNodep;if(isEmptyStack_link(plstack))printf(Emptystackpop.\n);else{p=plstack-top;plstack-top=plstack-top-link;free(p);}}退栈算法（算法4.9）243.2栈的应用栈的应用非常之广，只要问题满足LIFO原则，均可使用栈做数据结构。我们先看几个例子。例3.1文字编辑器例3.2栈与递归例3.3数制转换例3.4括号匹配的检验例3.5表达式求值25例3.1设计一个简单的文字编辑器，使其具有删除打错字符的功能。‘#’——删除前面一个字符‘@’——删除前面所有字符‘*’——输入结束“abc#d@efg*”我们用栈来实现这种功能的文字编辑器每读入一个字符退栈置空栈编辑结束26PSeqStackstr;/*顺序栈str是全程变量*/EDIT()/*编辑好的字符串在str中*/{charc;str=createEmptyStack();c=getchar();while(c!=‘*’)/*字符‘*’为编辑结束符*/{if(c==‘#’)POP(str);elseif(c==‘@’)str=createEmptyStack();elsePUSH(str,c);c=getchar()；}}/*EDIT*/例3.1设计一个简单的文字编辑器，使其具有删除打错字符的功能。27如果一个对象部分的由自己组成，或者是按它自己定义的，则称为递归的。一个递归定义必须一步比一步简单，最后是有终结的，决不能无限循环下去。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。例3.2栈与递归递归的定义28例3.2栈与递归递归函数的特点：在函数内部可以直接或间接地调用函数自身。如阶乘函数：n!=1,n=0n*(n-1)!,n0阶乘的递归计算（算法4.11）intfact(intn){if(n==0)return1;elsereturn(n*fact(n-1));};r2main(){intn;scanf(“%d\n”,&n);printf(“%8d%8d\n”,n,fact(n));}r133r12r21r20r2112630调用前：（1）为被调用函数的局部变量分配存储区；（活动记录，数据区）（2）将所有的实参、返回地址传递给被调用函数；实参和形参的结合，传值。（3）将控制转移到被调用函数入口。调用后返回：（1）保存被调用函数的计算结果；（2）释放被调用函数的存储区；（3）依照被调用函数保存的返回地址将控制转移到调用函数。递归函数到非递归函数的转换函数嵌套调用时，按照“后调用先返回”的原则进行。intmain(){intm,n;...first(m,n);1:…}intfirst(ints,intt){inti;…second(i);2:…}intsecond(intd){intx,y;3:…}intmain(){intm,n;...{inti;…{intx,y;3:…}2:…}1:…}firstmainsecond函数嵌套结构算法4.12阶乘的非递归计算程序员自己管理一个栈，并模拟函数调用的执行过程。intnfact(intn);{intres;pSeqStackst;st=createEmptyStack-seq();while(n0)while(!isEmptyStack-seq(st)){push-seq(st,n);{res=res*top-seq(st);n=n-1;}pop-seq(st);}res=1;free(st);return(res);}阶乘递归算法：intfact(intn){if(n==0)return1;elsereturn(n*fact(n-1));};34例3.3数制转换十进制数N和其它d进制数的转换基于下列原理：N=(Ndivd)xd+NmoddNNdiv8mod8134816841682102125202405235程序要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好与计算过程相反。例3.3数制转换因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。36PSeqStackstr;voidCONVERSION(){str=createEmptyStack();scanf(“%d”,X);while(X){PUSH(str,X%8);X=X/8;}while(!EMPTY(str)){printf(“%d”,TOP(str));POP(str);}}/*CONVERSION*/例3.3数制转换37例3.3数制转换voidCONVERSION(intX){If(X/8!=0)conversion(X/8);Printf(“%d”,X%8);}用递归函数实现：用递归编程时，不需要用户自行定义栈。它是由编译程序加以设立和处理的。38例3.4括号匹配的检验假设表达式中允许三种括号：（）、[]和{}，其嵌套的顺序随意。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。[（{}[]）]1234567839Judgement()/*判断表达式是否配对，表达式以‘#’结束*/{PSeqStacksta;charch,chpop;intvalid;SETNULL(&sta);PUSH(&sta,‘#’);/*把’#’放在栈底*/ch=getchar();valid=TRUE;/*valid为FALSE表示括号配对失败*/例3.4括号匹配的检验40例3.4括号匹配的检验while(ch!=‘#’){/*当读入字符为左括号时进栈*/if((ch==‘(’)||(ch==‘[’)||(ch==‘{’))PUSH（&sta,ch）；