数据结构第3章栈队列

第三章栈和队列『数据结构

·DATASTRUCTURES』第三章栈和队列本章要求掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法；熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法；理解递归算法执行过程中栈的状态变化过程。重点和难点掌握栈和队列的基本操作实现算法，递归第三章栈和队列栈栈的定义栈的表示和实现栈与递归的实现栈的应用举例队列要点小结第三章栈和队列栈栈的定义栈的表示和实现栈与递归的实现栈的应用举例队列要点小结线性表的概念线性表(LinearList)是由n(n≥0)个数据元素(结点)a1,a2,……,an组成的有限序列。数据元素的个数n定义为表的长度。当n=0时，称为空表。将非空的线性表(n＞0)记作:(a1，a2，…，an)数据元素ai(1≤i≤n)只是个抽象符号，其具体含义在不同情况下可以不同。它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。线性表分类Datacanbeinsertedanddeleted

anywhere.Datacanonlybeinsertedanddeletedattheendsofthestructure.栈的定义后进先出策略，即LIFO(LastIn,FirstOut)栈的定义栈作为一种限定性线性表,将线性表的插入和删除运算限制为仅在表的一端进行,即LIFO表。通常将表中允许进行插入、删除操作的一端称为栈顶

(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈的抽象数据类型定义数据元素：可以是任意类型的数据，但必须属于同一个数据对象。关系：栈中数据元素之间是线性关系基本操作：PushPopStackTopInitStackClearStackIsEmptyIsFullGetTop…第三章栈和队列栈栈的定义栈的表示和实现栈与递归的实现栈的应用举例队列要点小结栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构链式存储结构顺序存储的栈为顺序栈。链式存储的栈为链栈。顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。由于栈的操作的特殊性，还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。

用C语言定义栈的顺序存储结构#defineTRUE1#defineFALSE0#defineStack_Size100

typedefstruct{StackElementTypeelem[Stack_Size];/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标*/}SeqStack;PushoperationinastackPushaddsanitematthetopofthestack.PopoperationinastackPopremovestheitematthetopofthestack.顺序栈Push、Pop操作演示顺序栈基本操作的实现voidInitStack(SeqStack*S){/*构造一个空栈S*/S->top=-1;}InitStackIsEmptyIsFullPushPopGetTop可以改写成带返回值的形式吗？如果可以，如何改写？顺序栈基本操作的实现intIsEmpty(SeqStack*S)/*判栈S为空栈时返回值为真，反之为假*/{return(S->top==-1?TRUE:FALSE);}InitStackIsEmptyIsFullPushPopGetTop顺序栈基本操作的实现intIsFull(SeqStack*S)/*判栈S为满时返回真,否则返回假*/{return(S->top==Stack_Size-1?TRUE:FALSE);}InitStackIsEmptyIsFullPushPopGetTop为什么栈满的条件在这里是Stack_Size-1，而不是Stack_Size？？顺序栈基本操作的实现intPush(SeqStack*S,StackElementTypex){if(S->top==Stack_Size-1)

return(FALSE);/*栈已满*/S->top++;S->elem[S->top]=x;return(TRUE);}InitStackIsEmptyIsFullPushPopGetTop顺序栈基本操作的实现intPop(SeqStack*S,StackElementType*x){if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];S->top--;/*修改栈顶指针*/return(TRUE);}}InitStackIsEmptyIsFullPushPopGetTop比较Push和Pop实现时的异同哪个是正确的？顺序栈基本操作的实现intGetTop（SeqStack*S,StackElementType*x）{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->elem[S->top];return(TRUE);}}InitStackIsEmptyIsFullPushPopGetTop链栈链栈是采用链表作为存储结构实现的栈。相对于顺序栈，也可采用带头结点的单链表实现栈。链栈在使用完毕时，应该释放其空间。

链栈链栈的结构示意用C语言定义的链栈结构typedefstructnode{dataTypedata;structnode*next;}StackNode,*LinkStack;不带头结点链栈基本操作的实现LinkStackInit_LinkStack(){returnNULL;}PushPopIsEmptyInitStack不带头结点链栈基本操作的实现intEmpty_LinkStack(LinkStacktop){if(top==NULL)return1;elsereturn0;}PushPopIsEmptyInitStack不带头结点链栈基本操作的实现LinkStackPush_LinkStack(LinkStacktop,dataTypex)/*向栈中压入元素x*/{StackNode*s;s=(LinkStackNode*)malloc(sizeof(StackNode));if(s==NULL)return(FALSE);/*申请空间失败*/s->data=x;s->next=top;top=s;/*修改当前栈顶指针*/returntop;}PushPopIsEmptyInitStack不带头结点链栈基本操作的实现LinkStackPop_LinkStack(LinkStacktop,datatype*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/StackNode*p;if(top==NULL)returnNULL;else{*x=top->data;p=top;top=top->next;free(temp);/*释放存储空间*/}return(TRUE);}PushPopIsEmptyInitStack第三章栈和队列栈栈的定义栈的表示和实现栈与递归的实现栈的应用举例队列要点小结栈与递归的实现递归在定义自身的同时又出现了对自身的调用。直接递归函数如果一个函数在其定义体内直接调用自己，则称直接递归函数。间接递归函数如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数。栈与递归的实现递归的实现应用递归算法的前提：原问题可以层层分解为类似的子问题，且子问题比原问题规模更小；规模最小的子问题具有直接解，即不需要再调用自身。设计递归的方法：寻找分解方法；（递归式）设计递归出口；（递归终止条件）栈与递归的实现--TowersofHanoi栈与递归的实现--TowersofHanoiHanoiTower—SolutionforthreedisksMovetwodisksfromsourcetoauxiliaryneedle.Movetwodisksfromauxiliarytodestinationneedle.HanoiTower—SolutionforthreedisksvoidHanoi(intn,charx,chary,charz)/*将塔座x上从上到下编号为1至n且按直径由小到大叠放的n个圆盘，按规则移动到塔座z上，塔座y用作辅助塔座*/{if(n==1)move(x,n,z);//将编号为n的圆盘从x移到z上else{Hanoi(n-1,x,z,y);//将x上编号为1到n-1的圆盘移到y，z作辅助塔move(x,n,z);//将编号为n的圆盘从x上移动z上Hanoi(n-1,y,x,z);//将y上编号为1到n-1的圆盘移到z，x作辅助塔}}第三章栈和队列栈栈的定义栈的表示和实现栈与递归的实现栈的应用举例队列要点小结ExampleShowtheresultofthefollowingoperationsonastackS.

push(S,10)

push(S,12)push(S,8)

ifnotempty(S),thenpop(S)

push(S,2)

例一、数制转换

算法基于原理：

N=(Ndivd)×d+Nmodd

例如：（1348)10=(2504)8，其运算过程如下：

NNdiv8Nmod8

210

2125

202计算顺序输出顺序栈的应用举例----数制转换/*对于任意的一个非负十进制数N，打印出与其等值的二进制数*/voidConversion(intN){StackS;intx;/*S为顺序栈或链栈*/InitStack(&S);while(N>0){x=N%2;Push(&S,x);N=N/2;}while(!IsEmpty(S)) {Pop(&S,&x);printf(“%d”,x);}}2.

括号匹配问题思想：在检验算法中设置一个栈，若读入的是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。算法:voidBracketMatch(char*str){StackS;inti;charch;InitStack(&S);For(i=0;str[i]!='\0';i++){switch(str[i]){case'(':case'[':case'{':Push(&S,str[i]);break;case')':case']':case'}':if(IsEmpty(S)) {printf("\n右括号多余!");return;}else{GetTop(&S,&ch);if(Match(ch,str[i]))Pop(&S,&ch);else{printf("\n对应的左右括号不同类!");return;}}}/*switch*/}/*for*/if(IsEmpty(S)) printf("\n括号匹配!");else printf("\n左括号多余!");}3.表达式求值1)无括号算术表达式求值表达式运算及运算符优先级3+4*5#+-*/**①0123②置空栈OVS、OPTR进OVS读字符W退OVS顶、次顶，OPTR顶将T(i)=>OVS新顶进OPTR栈W是操作符N结束NYNYYYW=‘#’’OPTRZ栈空YW优先级≤OPTR栈顶优先级N无括号算术表达式的处理过程如右图2)算术表达式处理规则规定优先级表；(2)设置两个栈：OVS(运算数栈)和OPTR(运算符栈)；(3)自左向右扫描，遇操作符则与OPTR栈顶优先级比较：当前操作符>OPTR栈顶则进OPTR栈；当前操作符≤OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T（i），T（i）进OVS栈。例：实现A/B↑C+D*E#的运算过程时栈区变化情况3)带括号算术表达式实现算符优先算法时需要使用两个工作栈：一个称作运算符栈operator；另一个称作操作数栈operand。算法的基本过程如下：A.初始化操作数栈operand和运算符栈operator，并将表达式起始符“#”压入运算符栈；B.读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：

(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。当operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求值完毕。第三章栈和队列栈栈的定义栈的表示和实现两栈共享技术栈与递归的实现栈的应用举例队列要点小结两栈共享技术主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。两栈共享的数据结构定义#defineM100typedefstruct{StackElementTypeStack[M];StackElementTypetop[2];/*top[0]和top[1]分别为两个栈顶指示器*/}DqStack;两栈共享基本操作的实现voidInitStack(DqStack*S){S->top[0]=-1;S->top[1]=M;}InitStackPushPop两栈共享基本操作的实现intPush(DqStack*S,StackElementTypex,inti){if(S->top[0]+1==S->top[1])/*栈已满*/return(FALSE);switch(i){case0:S->top[0]++;S->Stack[S->top[0]]=x;break;case1:S->top[1]--;S->Stack[S->top[1]]=x;break;default:return(FALSE)}return(TRUE);}InitStackPushPop两栈共享基本操作的实现intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S->top[0]==-1)return(FALSE);*x=S->Stack[S->top[0]];S->top[0]--;break;case1:if(S->top[1]==M)return(FALSE); *x=S->Stack[S->top[1]];S->top[1]++;break;default:return(FALSE);}return(TRUE);}InitStackPushPop第三章栈和队列栈队列队列的定义队列的表示和实现队列的应用举例要点小结队列的定义Arestrictedlinearlistinwhichdatacanonlybeinsertedatoneend(rear)anddeletedfromtheotherend(front).AFIFO(FirstIn,FirstOut)datastructure.ADTQueue数据元素可以是任意类型的数据，但必须属于同一个数据对象。关系队列中数据元素之间是线性关系。第三章栈和队列栈队列队列的定义队列的表示和实现队列的应用举例要点小结队列的表示什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表队列的特点先进先出(FIFO)队列的表示和实现

a1a2a3an入队列队头队尾出队列队列的示意图队列的特点先进先出第一个入队的元素在队头，

最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素

队列的基本操作1）初始化操作InitQueue(&Q)

功能：构造一个空队列Q；

2）销毁操作DestroyQueue(&Q)

功能：销毁已存在队列Q；

3）置空操作ClearQueue(&Q)

功能：将队列Q置为空队列；4）判空操作QueueEmpty(Q)功能：若队列Q为空，则返回True，否则返回False；队列的基本操作5）取队头元素操作GetHead(Q,&e)

功能：取队头元素，并用e返回；

6）入队操作EnQueue(&Q,e)

功能：将元素e插入Q的队尾；

7）出队操作DeQueue(&Q,&e)

功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回

ERROR；队列的顺序存储和实现一．

队列的顺序存贮结构

1队列的顺序存贮结构Q.rearQ.frontJ1J2J3队列的顺序存贮结构图示2．顺序队列的类型定义#defineMAXSIZE100//最大队列长度

typedefstruct{

QElemType*base;

intfront;intrear;}SqQueue;Q.rearQ.frontJ1J2J3Q.rearQ.frontJ3（a)空队列(b)J1,J2和J3相继入队列(c)J1和J2相继出队(d)J4,J5和J6相继入队之后,J3出队Q.rearQ.front012345队头指针队尾指针和队列中元素之间的关系图示Q.rearQ.frontJ6J5J4队列的初始化操作在初始化见空队列时，令front＝rear＝0；插入：Q.rear=Q.rear+1;删除：Q.front=Q.front+13.循环队列

J6J4J5Q.rearQ.front312405543210

循环队列图示Q.rearQ.frontJ6J5J44．队空队满的判别Q.rear540312Q.frontJ6J7J8J9J4J5540312J6Q.frontQ.rearJ5J4

(a)(b)队空(c)队满540312Q.frontQ.rear有两种方法：

1）另设一个标志位以区分队空、队满。

2）少用一个存储单元，即当队列达到图（d）所示状态时，我们就认为队列已满，这时的条件是Q.front=(Q.rear+1)%MAXQSIZE;如何判断循环队列队空、队满？

？Q.rear540312Q.frontJ6J7J8J4J5（d）

设Q为SqQueue类型的变量，用于存储队列。设为队列Q分配空间大小为MAXSIZE=6，初始建队时，令Q.front=Q.rear=0;Q.frontQ.rear540312Q.base实际上，Q.front=0,Q.rear=0，用箭头指示只是为了直观二循环队列的基本操作算法Q.frontQ.rear540312建一个空队列Q初始化操作InitQueue_Sq(SqQueue&Q)

StatusInitQueue_Sq(SqQueue&Q){

//构造一个空队列Q

Q.base=(ElemType*)malloc(MAXOSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存储分配失败

Q.front=Q.rear=0;

ReturnOK;

}//InitQueue_Sq入队操作EnQueue_Sq(SqQueue&Q,QElemTypee)功能：将元素e插入队尾；

入队操作主要步骤：

1）Q是否已满，若满，返回ERROR；否则转2）；2）将元素e写入队尾；

3）修改队尾指针，使队尾指针指向队尾元素的下一个位置；Q.frontQ.rear540312J1J3J2eQ.frontQ.rear540312J1J3J2元素e入队前元素e入队后StatusEnQueue_Sq(SqQueue&Q,QElemTypee)

//将元素e插入队尾

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;//将元素e插入队尾

Q.rear=(Q.rear+1)%MAXSIZE;

//修改队尾指针

returnOK;

}//EnQueue_Sq出队操作DeQueue_Sq(SqQueue&Q,QElemType&e)

功能：删除队头元素，用e返回其值；

出队操作主要步骤：

1）Q是否为空，若空，返回ERROR；否则转2）；2）将队头元素赋值给e；

3）修改队头指针，删除队头元素；Q.frontQ.rear540312J1J3J2Q.frontQ.rear540312J1J3J2出队操作前出队操作后eJ1出队操作算法

StatusDeQueue_Sq(SqQueue&Q,QElemType&e)

//删除队头元素，用e返回其值,并返回OK；否则返回ERRORif((Q.rear==Q.front)returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXSIZE;//修改队头指针

returnOK;

}//EnQueue_Sq

链队列——队列的链式存储结构和实现一什么是链队列

用链表存储的队列称为链队列Q.frontQ.rear∧空链队列J1∧Q.frontQ.rearJ2∧链队列图示二链队列的类型定义typedefstructQnode{{////链队列结点的类型定义

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{

//链队列的表头结点的类型定义

QueuePtrfront;

QueuePtrrear;

}LinkQueue;J1∧Q.frontQ.rearJ2∧

设Q为LinkQueue类型的变量，Q为链队列的表头结点，用于存储队列队头指针和队尾指针；初始建队时，令Q.front=Q.rear=null;Q.frontQ.rear∧空链队列链队列的表头结点链队列的表头结点链队列图示链队列的头结点三链队列基本操作算法1）初始化操作InitQueue_L(LinkQueue&Q)StatusInitQueue_L(LinkQueue&Q){//建一个空队列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

//为链队列的头结点分配空间

if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;

returnOK;

}//InitQueue_LQ.frontQ.rear∧空链队列链队列的表头结点链队列的头结点2)销毁操作DestroyQueue_L(LinkQueue&Q)StatusDestroyQueue(LinkQueue&Q){//销毁队列Q while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }//while结束

returnOK;}//DestroyQueueQ.frontQ.rearJ1∧Q.frontQ.rearJ2∧nullnull

销毁前

销毁后3）入队操作EnQueue_L(LinkQueue&Q,QElemType)入队操作图示Q.frontJ1∧Q.reare∧e入队前e入队后J1∧Q.frontQ.rear算法StatusEnQueue_L(LinkQueue&Q,QElemType){

//在链队列Q队尾，插入新的队尾结点

p=(QueuePtr)malloc(sizeof(QNode));//为新元素e分配结点空间

if(!p)exit(OVERFLOW);//存储分配失败

p->date=e;p->next=NULL;

Q.rear->next=p;//修改队尾指针，插入新队尾结点

Q.rear=p;returnOK;

}Q.front∧J1∧Q.reare∧J1在链队列Q队尾，插入新的元素e4）出队操作DeQueue_L(LinkQueue&Q,QElemType&e)StatusDeQueue_L(LinkQueue&Q,QElemType&e){

if(Q.front==Q.rear)returnERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;free(p);

returnOK;

}J1Q.frontQ.rearJ2∧元素J1出队列图示J1e第三章栈和队列栈队列队列的定义队列的表示和实现队列的应用举例要点小结键盘缓冲区缓冲区:接收设备或应用程序使用数据之前，为暂时保存此数据而保留的内存区域。缓冲可防止数据流中断。键盘缓冲区：是一个“循环队列”数据结构，对于未处理的扫描码暂时储存起来，采用“先进先出”的原则操作。如果缓冲区已满，再按下键时则认为无效。键盘缓冲区问题描述：有两个进程同时存在于一个程序中。其中第一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户键入的字符并保存到输入缓冲区中。在用户输入时，键入的字符并不