算法与数据结构第3章栈和队列

第三章栈和队列陈守孔讲授开始学习本章前要掌握：从数据结构角度看，栈和队列仍属于线性结构，具有线性结构的共同特征；学习本章时，要注意到栈和队列所具有的线性结构的共性，更要掌握其个性；栈和队列是操作受限的线性结构；本章具体内容见本章目录。本章目录3.1栈

3.1.1栈的类型定义3.1.2栈的表示和实现

3.2栈的应用举例3.3栈与递归3.3.1如何实现递归3.3.2采用递归算法解决的问题

3.3.3将递归转换为非递归3.4队列

3.4.1队列的类型定义3.4.2循环队列－队列的顺序存储结构

3.4.3链队列－队列的链式表示和实现*3.5算法设计举例主要内容知识点栈与队列的特征栈与递归循环队列重点难点栈的操作递归循环队列栈与队列的综合应用栈〔Statck〕的定义栈是操作受限制的线性表定义：仅在表尾进行插入或删除操作的线性表；概念：栈顶：在栈顶操作，是表尾，通常用top表示；栈底：bottom，是表头；空栈:空表；通常栈底固定，栈顶移动。栈示意图a1a2a3an…栈顶top栈底bottom表头表尾操作原那么：后进先出〔LastInFirstOut〕,LIFO举例：餐馆的盘子

栈的抽象数据类型定义ADTStack{数据对象：D={ai|aiElemSet,i=1,2,...,n，n>=0}数据关系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}根本操作:栈初始化：StackInit()判栈空：StackEmpty(S)入栈：Push(S，x)出栈：Pop(S)取栈顶元素：StackGetTop(S)清空栈：StackClear(S)求栈长：StackLength(S)}ADTStack栈的表示和实现顺序存储结构：顺序栈；链式存储结构：链栈；

顺序栈利用一组地址连续的存储单元依次自栈底到栈顶存放栈的数据元素。在数组上实现时，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，可以用一个整形变量top存放栈顶的指针，数据入栈或出栈时使整形变量top分别加1或减1。

顺序栈的类型定义#defineMAXSIZE1024typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack；用顺序栈实现栈的运算(1)SeqStackSeqStackInit(){//构造一个空栈SSeqStackS；S.top=-1;returnS;}初始化用顺序栈实现栈的运算(2)intSeqStackEmpty(SeqStackS){//判断栈S是否为空if(S.top==-1)returnTRUE;elsereturnFALSE;}判栈空

用顺序栈实现栈的运算(3)voidSeqStackPush(SeqStackS,ElemTypex){//插入元素x为新的栈顶元素if(S.top==MAXSIZE-1) {printf(“Overflow〞);exit(0);}//栈满，退出运行S.top++; S.data[S.top]=x;}入栈

用顺序栈实现栈的运算(4)ElemTypeSeqStackPop(SeqStackS){//假设栈S不空，删除S的栈顶元素，并返回其值if(S.top==-1)//栈已空，退出运行{printf(“Empty\n〞);exit(0);}x=S.data[S.top];S.top--;returnx;}出栈

用顺序栈实现栈的运算(5)ElemTypeSeqStackGetTop(SeqStackS){if(S.top==-1){printf(“栈空!\n〞);exit(0);}elsereturn(S.data[S.top]);}取栈顶元素

双向栈栈1底栈2底栈1栈2…两个栈共享一个向量空间，栈底分别设在两端，写出进栈和退栈操作双向栈的类型定义#definem64typedefstruct{ElemTypedata[m];inttop[2];//top[0],top[1]分别是两个栈的栈顶指针}TStack;初始化时，top[0]=-1和top[1]=m表示栈空，栈顶相遇时表示栈满，入栈时栈顶指针相向移动。链栈用链式存储结构实现的栈称为链栈。通常链栈可用单链表表示，因此其结点结构与单链表的结构相同。

链栈结点的类型描述：typedefstructStackNode{ElemTypedata;structStackNode*next;}StackNode，*LinkedStack;由于栈只在栈顶操作，因此，通常不设头结点。链栈图示top

∧

用链栈实现栈的运算(1)LinkedStackLinkedStackInit〔〕{//构造一个空栈，栈顶指针为topLinkedStacktop;top=NULL;returntop;}链栈的初始化用链栈实现栈的运算(2)intLinkedStackEmpty(LinkedStacktop〕{//判定栈S是否是空栈if〔top==NULL〕returnTRUE;elsereturnFALSE;}判栈空用链栈实现栈的运算(3)LinkedStackPush(LinkedStacktop,ElemTypex〕//插入元素x为新的栈顶元素，链栈用栈顶指针top表示{s=(LinkedStack)malloc(sizeof(StackNode));//创立一个新结点s->data=x; //设置新结点的数据域s->next=top; //设置新结点的指针域top=s; //设置新栈顶指针returntop;}入栈

用链栈实现栈的运算(4)ElemTypePop(LinkedStacktop){//假设栈S不空，那么删除S的栈顶元素，并返回其值if〔top！=NULL〕{x=top->data; p=top;top=top->next;free(p);returnx;}else{printf(“栈空\n〞);exit(0);}}退栈

自测题设栈的输入序列是1，2，3，4,那么〔〕不可能是其出栈序列。A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2E.3，2，1，4，【烟台大学2007一.4(2分)】D自测题设输入元素为1、2、3、P和A，输入次序为123PA，如图〔编者略〕。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。【中山大学1997】PA321P3A21P32A1P321AAP321自测题1．假设元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，那么不可能得到的出栈序列是A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b【2010年全国硕士研究生入学统一考试计算机学科专业根底综合】D栈的应用栈与过程调用表达式求值栈与递归过程栈与过程调用过程的嵌套调用图示：算法举例3.1栈的应用:数制转换把十进制数转换为八进制数。N=(N/d)*d+Nmodd;例如:(1348)10=(2504)81348/8=168, 1348%8=4 最低位168/8=21, 168%8=021/8=2, 21%8=52/8=0, 2%8=2 最高位(1348)10=1*103+3*102+4*101+8*100;(2504)8=2*83+5*82+0*81+4*80;数制转换的非递归算法voidconversion(){//把十进制转换为八进制 InitStack(S); scanf(“%d〞,&N); while(N) {Push(S,N%8); N=N/8;} while(!StackEmpty(S)) {Pop(S,e);printf(“%d〞,e); }}数制转换的递归算法voidConvert(intn){//把十进制n转换为八进制if(n!=0) {Convert(n/8);printf(“%d〞,n%8); }}算法举例3.2:中缀表达式的求值算术表达式中运算符(+,-,*,/等)的优先规那么设置两个工作栈：运算符栈S1和操作数栈S2。S2存放表达式的运算结果。算法思想：1首先置操作数栈S2为空栈，置运算符栈的栈底为表达式的起始符#(优先级最低)。2依次读入表达式的每个字符ch,直至表达式结束：假设ch是操作数,那么进S2栈；假设ch是运算符，假设其优先级不高于栈顶运算符的优先级时，那么取出栈S2的栈顶和次栈顶的两个元素以及栈S1的栈顶运算符，进行相应的运算，并将结果放入栈S2中；如此下去，直至ch的优先级高于栈顶运算符的优先级，将ch入S1栈。举例:3*(5-2)步骤optr栈S1opnd栈S2输入字符主要操作

－－－－－－－－－－－－－－－－－－－－－－－－－－1#3*(5-2)#push(s2,’3’)2#3*(5-2)#push(s1,’*’)3#*3(5-2)#push(s1,’(’)4#*(35-2)#push(s2,’5’)5#*(35-2)#push(s1,’-’)6#*(-352)#push(s2,’2’)7#*(-352)#operate(‘5’,’-’,’2’)8#*(33)#pop(s1){消除一对括号}9#*33#operate(‘3’,’*’,’3’)10#9#return(gettop(s2))中缀表达式求值算法ElemTypeEvalExpression(){charch,opnd[maxch],optr[maxch];//opnd是运算数栈,optr是运算符栈init(optr);push(optr,‘#’);init(opnd);ch=getchar();while(ch!=‘#’||gettop(optr)!=‘#’)if(!in(ch,op)){push(opnd,ch);ch=getchar();}//不是运算符就进栈elseswitch(precede(gettop(optr),ch)){case‘<’://栈顶元素优先级低push(optr,ch);ch=getchar();break;case‘=’://脱括号并接收下一字符pop(optr,x);ch=getchar();break;case‘>’://退栈并将运算结果入栈pop(optr,theta);pop(opnd,b);pop(opnd,a);push(opnd,operate(a,theta,b));break;}//switchreturngettop(opnd);}中缀表达式转为后缀表达式概念：前缀表达式，中缀表达式，后缀表达式+ab,a+b,ab+〔1〕中缀表达式转为后缀表达式设中缀表达式和后缀表达式分别在向量IFX和PFX申，用栈S实现中缀式转为后缀式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下：栈初始化从左到右扫描向量IFX，重复下述两步操作，直到表达式尾：①从IPX中取出下个TOKEN(数字、运算符、左括号、右括号)；②CASETOKENOF‘(’：将TOKEN压入栈S;‘)’：退栈并将退栈元素送PFX，直到碰到左括号，左括号退栈不送PFX。操作数：将操作数直接送入PFX;操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否那么，退栈并将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之;当遇到中缀表达式结束符号，连续退栈并送退栈元素到PFX，直至栈空。举例：将中缀表达式

8-(3+5)*(5-6/2〕

转为后缀表达式表达式转换的简单方法中缀表达式转为后缀表达式有三步：〔1〕加括号：将中缀表达式中所有的子表达式按计算规那么用嵌套括号括起来；〔2〕移运算符：顺序将每对括号中的运算符移到相应括号的后面；〔3〕删括号：删除所有括号。例如，将中缀表达式8-(3+5)*(5-6/2〕转为后缀表达式。按如上步骤：执行完上面第一步后为：(8-((3+5)*(5-(6/2))))；执行完上面第二步后为：(8((35)+(5(62)/)-)*)-；执行完上面第三步后为：835+562/-*-。可用类似方法将中缀表达式转为前缀表达式。后缀表达式求值〔2〕对后缀表达式求值用实型数栈S存放计算后缀式的中间及最终结果，求值算法可描述如下。栈初始化。从左到右扫描向量PFX，重复下述两步操作，直到表达式尾。①从PFX中取出下个TOKEN(操作数、运算符)②CASETOKENOF操作数：将操作数直接送入栈S1;操作符：出栈两个操作数，对其进行TOKEN操作，结果压人栈S1当遇到后缀表达式结束符号，栈顶的值就是结果(应是栈中唯一元素)。后缀表达式求值举例中缀表达式：8-(3+5)*(5-6/2〕后缀表达式：835+562/-*-对后缀表达式求值835+562/-*-

算法举例3.3后缀表达式求值

详见教材算法3.31－－3.34自测题中缀表达式〔A+B〕*〔C-D〕/(E-F*G)的后缀表达式是_____；A.A+B*C-D/E-F*GB.AB+CD-*EFG*-/C.AB+C*D-E/F-G*D.ABCDEFG+*-/-*【北京邮电大学2005一.2(2分)】B栈与递归过程递归：假设在一个函数、过程或者数据结构定义的内部，直接〔或间接〕出现定义本身的应用，那么称它们是递归的，或者是递归定义的。递归过程的应用：问题的定义是递归的：f(n)=n*f(n-1)数据结构是递归的：链表问题的解法是递归的：Hanoi塔问题“递归工作栈〞——栈顶为“工作记录〞，包括参数、局部变量以及上一层的返回地址递归过程的应用〔1〕〔1〕问题的定义是递归的：求n的阶乘n!longFact(intn){if(n==0)return(1);elsereturn(n*Fact(n-1));}求阶乘(n!)过程的模拟n=3fac(3)n=2F=3*fac(2)n=1F=2*fac(1)n=0F=1*fac(0)fac(0)returnfac(3)=3*2*1returnfac(2)=2*1returnfac(1)=1*1returnfac(0)=1递归过程的应用〔2〕〔2〕数据结构是递归的：逆序打印无头结点单链表中各结点的值。voidprint(LinkedListhead){if(head!=null){print(head->next);printf(“%d〞,head->data);//设元素为整型}}递归过程的应用〔3〕(3)问题的解法是递归的：Hanoi塔问题递归过程的应用〔3〕n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，…,n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规那么为：每次只能移动一个园盘；园盘可以在任一塔上做屡次移动；在任何时刻，大盘不能压在小盘的上面。XYZ用递归实现Hanoi的算法思想使用数学归纳法：n=1,OK;设n=k时，假设可以以Y为辅助塔，把k个盘从X移动到Z;当n=k+1时，方法：把X中k个盘，以Z为辅助塔，移动到Y;把X中第k+1个盘，移动到Z;把Y中k个盘，以X为辅助塔，移动到Z;用递归实现Hanoi的算法voidHanoi(intn,charx,chary,charz){ if(n==1) move(x,1,z); //把1号盘，从x移到z else {Hanoi(n–1,x,z,y);//把n-1个盘从x移到y，z为辅助塔 move(x,n,z); //把n号盘，从x移到z Hanoi(n–1,y,x,z);//把n-1个盘从y移到z，x为辅助塔 }}Hanoi塔算法的模拟H(3,a,b,c)H(1,c,a,b)H(2,a,c,b)H(1,a,b,c)a

ca

bc

ba

cH(2,b,a,c)H(1,b,c,a)b

ab

cH(1,a,b,c)a

cn=1n=2n=3递归算法的优缺点优点：递归过程结构清晰程序易读正确性容易证明

缺点：时间效率低空间开销大算法不容易优化对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递归算法转换为非递归算法。递归算法转换为非递归算法有如下方法：采用迭代算法尾递归的消除利用栈消除任何递归将递归转换为非递归

采用迭代算法longFact2(intn){∥用迭代算法求n!x=1;for(i=1;i<=n;i++)x*=i;returnx;}∥Fact2递归从顶到底n!(n-1)!(n-2)!...2!1!0!迭代从底到顶

将递归转换成迭代使用尾递归的算法递归算法voidOutput1(LinkedListL){∥顺序输出单链表结点数据的递归算法if(L){printf(L->data);∥输出结点的值

Output1(L->next);∥尾递归调用}}∥Output1尾递归的消除〔1〕非递归算法voidOutput2(LinkedListL){∥顺序输出单链表结点数据的非递归算法一p=L;∥设局部变量p=LLbl:∥在第一个可执行语句前设标号if(p){printf(p->data);∥输出结点的值p=p->next;∥修改变量值gotoLb1;∥转到第一个可执行语句}}∥Output2尾递归的消除〔2〕voidOutput3(LinkedListL){∥顺序输出单链表结点数据的非递归算法二p=L;∥设局部变量p=Lwhile(p){printf(p->data);∥输出结点的值p=p->next;∥向里一层修改变量值}}∥Output3非递归算法利用栈消除任何递归〔1〕利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下：入栈处理设一个工作栈代替递归函数中的栈，栈中每个记录包括函数的所有参数：函数名、局部变量和返回地址。所有递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。修改确定本次递归调用时的实在参数之新值。转到函数的第一个语句。〔转下页〕利用栈消除任何递归〔2〕〔接上页〕退栈处理假设栈空，算法结束，执行正常返回。假设栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址。转到执行返回地址处的语句，继续执行。算法举例3.4栈的应用回文指正读和反读都相同的字符序列，写一算法判断含给定的字符串是否是回文。intsympthy(charstr[],chars[]){inti=0,j,n;while(str[i]!=‘\0’)i++;//查字符个数n=i;for(i=0;i<n/2;i++)s[i]=str[i];//前一半字符入栈j=i-1;if(n%2==1)i++;//n为奇数时中间字符不用比较while(i<n&&str[i]==s[j])//比较字符串是否是回文{i++;j--;}if(i==n)printf(“字符串是回文\n〞)；elseprintf(“字符串不是回文\n〞)；}队列(Queue)定义和概念队列：队列是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。

概念：队尾rear：插入端，线性表的表尾。队头front：删除端，线性表的表头。队列(Queue)图示FIFO〔FirstInFirstOut〕〔先进先出表〕a1a2a3an-1出队列入队列队头队尾……队列的抽象数据类型ADTQueue{数据对象：D={ai|aiElemSet，i=1，2，...，n，n>=0}数据关系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}根本操作：队列初始化：QueueInit()入队：QueueIn(Q,x)出队：QueueOut(Q)读队头元素： QueueGetHead(Q)判队空：QueueEmpty(Q)求队列长：QueueLength(Q)}ADTQueue队列的表示和实现顺序存储结构：循环队列；链式存储结构：链队列；队列的顺序表示和实现frontJ1J2J3J4frontrearJ1J2J3J4frontrearfrontrearJ1frontrear问题：如何解决“假上溢〞现象?J1J2J3J4J6J5rear543210543210约定队头指针指向队头元素的前一个位置，队尾指针指向队尾元素队列的顺序表示和实现循环队列：循环队列操作示意图循环队列空队列条件：Q.rear=Q.front;满队列条件：Q.rear=Q.front;问题：如何区别队空和队满有三种方法1.牺牲一个存储空间2.引入一个标志变量区别空和不空3.使用计数器循环队列类型定义#defineMAXSIZE256typedefstruct{ElemTypedata[MAXSIZE];//

数据的存储区intfront,rear;//队头队尾指针}SeQueue;//循环队循环队列的初始化SeQueueSeQueueInit(){SeQueueQ;

Q.front=Q.rear=0;returnQ;}

循环队列的入队voidSeQueueIn(SeQueueQ,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {printf(“Full\n〞);exit(0); //队列满,退出运行 }Q.rear=(Q.rear+1)%MAXSIZE;Q.data[Q.rear]=x;}循环队列的出队ElemTypeSeQueueOut(SeQueueQ){if(Q.front==Q.rear){printf(“Empty\n〞);exit(0); //队已空,退出运行 }Q.front=(Q.front+1)%MAXSIZE;x=Q.data[Q.front];//读出队头元素returnx;//出队完成}循环队列的判空intSeQueueEmpty(SeQueueQ){if(Q.front==Q.rear)returntrue;elsereturnfalse;}求队中元素个数intSeQueueLength(SeQueueQ){∥返回队列Q的元素个数

return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}链队列用链表表示的队列简称为链队列。为便于操作，一个链队列需要分别指示队头和队尾的两个指针。

…a2rearfronta1an∧链队示意图(a)非空队frontreara1an∧

…a2Q(b)空队rearfrontQ

∧

(c)链队中只有一个元素结点frontrearQa1∧

链队列的类型描述

typedefstructLQNode{ElemTypedata;structLQNode*next;}LQNode,*LinkedQNode;//链队结点的类型及指针

typedefstruct{StructLQNode*front,*rear;}LQueue,*LinkedQueue;//将头尾指针封装在一起的链队链队列的初始化创立一个带头结点的空队LinkedQueueLinkedQueueInit(){Q=(LinkedQueue)malloc(sizeof(LQueue));//申请头尾指针结点p=(LinkedQNode)malloc(sizeof(LQNode));

//申请链队头结点p->next=NULL;Q->front=Q->rear=p;returnQ;}

链队列的入队voidLinkedQueueIn(LinkedQueueQ,ElemTypex){p=(LinkedQNode)malloc(sizeof(LQNode));p->data=x;p->next=Q->rear->next;//或p->next=NULL;Q->rear->next=p;Q->rear=p;}链队列的判空intLinkedQueueEmpty(LinkedQueueQ){if(Q->front==Q->rear)returntrue;elsereturnfalse;}

链队列的出队出队

LinkedQueueOut(LinkedQueueQ){if(!LinkedQueueEmpty(Q)){p=Q->front->next;//队列带头结点Q->front->next=p->next;x=p->data;//队头元素放x中

if(p==Q->rear)Q->rear=Q->front;

//只有一个元素时，出队后队空，此时还要修改队尾指针free(p);returnx;}}

算法举例3.5假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，不设头指针，试设计相应的入队列和出队列的算法

typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

voidQueueIn(Queueptrrear,ElemTypex){//入队列s=(Queueptr)malloc(sizeof(LQueue));s->data=x;s->next=rear->next;//元素插入队尾rear->next=s;rear=s;//求得新的队尾}

ElemTypeQueueOut(Queueptrrear){//出队列if(rear->next==rear)printf("队列为空");else{p=rear->next;q=p->next;

p->next=q->next;x=q->data;if(q==rear)rear=p;free(q);//删除队头元素return(x);

}}

算法举例3.6要求完全利用循环队列中的元素空间，设置一个标志域tag，并以tag的值是0或１来区分尾指针和头指针相同时的队列状态是“空〞还是“不空〞。请编写与此结构相对应的入队和出队的算法。类型定义：typedefstruct{ElemTypedata[m];intrear,front;//队尾和队头指针inttag;//标记,0为空,1为非空}CycQueue;

只设标志的循环队列的入队voidQueueIn(CycQueuecq,ElemTypex){if(cq.tag==1&&cq.front==cq.rear){printf(“队满\n〞);exit(0);}else{cq.rear=(cq.rear+1)%m;cq.data[cq.rear]=x;if(cq.tag==0)cq.tag=1;//由空变不空标记}}只设标志的循环队列的出队voidQueueOut(CycQueuecq);{if(cq.tag==0){printf(“队空\n〞);exit(0);}else{cq.front=(cq.front+1)%m;if(cq.front==cq.rear)cq.tag=0;//队列由不空变空}}算法举例3.7用栈模拟队列请利用两个栈S1和S2来模拟一个队列。栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列；dequeue:删除一个元素出队列；queue_empty：判队列为空。【上海交通大学1999二(12分)】【厦门大学2005六(15分)】算法举例3.7栈模拟队列－－入队inttop1;∥top1是栈s1的栈顶指针，是全局变量intenqueue(stacks1,ElemTypex)∥用入栈模拟入队{