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

第3章限定性线性表—栈和队列3.1栈3.2队列栈和队列是两种常用的数据类型

线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈与队列

栈是限定仅在表尾进行插入和删除的线性表。队列是限定仅在表尾进行插入、在表头进行删除的线性表。23.1栈3.1.1栈的定义3.1.2栈的表示和实现3.1.3栈的应用举例3.1.4栈与递归的实现33.1.1栈的定义：ADTStack{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定an

端为栈顶，a1端为栈底。基本操作:

}ADTStack一、栈的类型定义栈是限定仅在表尾进行插入和删除的线性表。表尾被称为栈顶，表头被称为栈底。栈又被称为后进先出(lifo)的线性表。4InitStack(S)初始化一个空栈S。基本操作：ClearStack(S)将S清为空栈IsEmpty(S)若S为空栈,则返回true,否则false。GetTop(S)若S非空,则返回它的栈顶元素,否则返回'false

'。Push(S,e)入栈,插入元素e为新的栈顶元素。Pop(S)出栈,若S非空,则删除并返回它的栈顶元素,否则返回'false

'。IsFull(S)

若S为满栈,则返回true,否则false。5二、进栈、出栈图例

根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。进栈出栈进栈出栈栈顶栈底an…a2a163.1.2栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。7一、顺序栈1、顺序栈的存储结构定义#defineMaxSize50StackElementTypeS[MaxSize];

/*用来存放栈中元素的一维数组*/inttop;

/*栈顶指针，全局变量*/82、顺序栈中的进栈和出栈图例top=-1栈空FEDCBAtop=5栈满Atop=0插入ACBAtop=2栈长度393.顺序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1）栈底位置固定在顺序表的低端，即S[0]----表示栈底元素2）入栈：top++，保存元素；3）出栈：取元素,top--；4）空栈：top=-1；5）栈满：top=MaxSize-1；上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。103、顺序栈基本操作的实现1）初始化voidInitStack(int*S){/*构造一个空栈S*/top=-1;}112）判栈空intIsEmpty(int*S)

/*判栈S为空栈时返回值为1，反之为0*/{return(top==-1?1:0);}123）判栈满intIsFull(int*S)

/*判栈S为满时返回真，否则返回假*/{return(top==MaxSize-1?TRUE:FALSE);}134）进栈intPush(int*S,intx){if(top==MaxSize-1)return(FALSE);/*栈已满*/top++;S[top]=x;return(TRUE);}145）出栈intPop(int*S,int*x){if(top==-1)/*栈为空*/return(FALSE);else

{*x=S[top];top--;/*修改栈顶指针*/return(TRUE);}}156）取栈顶元素intGetTop（int*S,int*x）{/*将栈S的栈顶元素取出，放入x所指的单元，但栈顶指针保持不变*/ if(top==-1)/*栈为空*/return(FALSE); else

{*x=S[top];return(TRUE);} }16〖例〗设有一个空栈，栈顶指针为1000H，现有输入序列为12345，PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，输出序列为______，栈顶指针为_______

2,31003Htop=1000H1top=1001Htop=1002H23top=1003H45输出序列：〖例〗在一个n个单元的顺序栈中，假定以地址高端(下标为n-1的单元)作为栈底，则向栈中压入一个元素时，栈顶指针top的变化是______top不变 top=n top=top-1 top=top+1栈低栈顶top=-1n-1n-2…10〖例〗若一个栈的输入序列是1，2，…，n，输出序列的第一个元素是n，则第i个输出元素是______

n-i n-i+1 i n-i-1top=-1nn-1…12top=n-1方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，有可能浪费空间。当程序中同时使用几个栈时，如何防止栈的上溢？5.顺序栈上溢的解决方法方法二：使用两个（或多个）栈共享存储空间办法。两栈的栈底分别设在给定存储空间的两端，然后各自向中间伸延，当两栈的栈顶相遇时才可能发生溢出。20

利用栈“栈底位置不变，而栈顶位置动态变化”的特性，为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。

共享栈的空间示意为：top[0]和top[1]分别为两个栈顶指示器。top[0]top[1]Stack：0M-1216、两栈共享的数据结构定义#defineM100StackElementTypeS[M];inttop[2];/*全局变量*//*top[0]和top[1]分别为两个栈顶指示器*/227、两栈共享基本操作的实现1）两栈共享的初始化操作算法voidInitStack(int*S){ top[0]=-1; top[1]=M;}232）两栈共享的进栈操作算法intPush(int*S,intx,inti){if(top[0]+1==top[1])/*栈已满*/return(FALSE);switch(i){case0:

top[0]++;

S[top[0]]=x;

break;

case1:

top[1]--;

S[top[1]]=x;

break;default:return(FALSE)}return(TRUE);}243）两栈共享的出栈操作算法intPop(int*S,int*x,inti){switch(i){case0:if(top[0]==-1)return(FALSE);*x=S[top[0]];

top[0]--;break;

case1:if(top[1]==M)return(FALSE); *x=S[top[1]];top[1]++;break;default:return(FALSE);}return(TRUE);}25〖例〗设有一个输入序列123，元素经过一个栈到达输出序列，并且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列？分析：每一元素只能做一次入栈、一次出栈，可以入栈后停留一段时间，然后到达输出序列。那么该题就变为如何安排三次push操作（s）和pop操作(x)的顺序以得到尽量多的不同的输出。sssxxx:321ssxsxx:231ssxxsx:213sxsxsx:123sxssxx:13226补充：如果进栈的序列为123456，能否得到435612和135426的出栈序列，并说明为什么不能得到或者如何得到（写出以‘S’表示进栈,‘x’表示出栈的栈操作序列）二、链栈链栈是采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。链栈的示意图为：∧a1

…an-1antoptop为栈顶指针，始终指向当前栈顶元素前面的头结点。若top->next=NULL，则代表空栈。注意：链栈在使用完毕时，应该释放其空间。28链栈的基本操作特点1）栈底位置固定在链表的末尾p->next=NULL----表示栈底元素2）入栈：用入栈元素建立新结点，并将其插入到链表的第一个结点之前；(头插法)3）出栈：取出链表首元素结点的值，并将其第一个结点从链表中删除；4）空栈：top->next=NULL；291、链栈的存储结构定义typedefstructnode{StackElementTypedata;structnode*next;}LinkStackNode,*LinkStack;302、链栈基本操作的实现1)链栈的进栈操作intPush(LinkStacktop,StackElementTypex)

/*将数据元素x压入栈top中*/{

LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));/*申请空间*/if(temp==NULL)return(FALSE);/*失败*/temp->data=x;/*构造结点*/temp->next=top->next;top->next=temp;/*修改当前栈顶指针*/return(TRUE);}312)链栈的出栈操作intPop(LinkStacktop,StackElementType*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkStackNode*temp;temp=top->next;if(temp==NULL)/*栈为空*/ return(FALSE);top->next=temp->next;*x=temp->data;free(temp);/*释放存储空间*/return(TRUE);}323.1.3栈的应用举例例1、括号匹配的检验则检验括号是否匹配可用栈来实现。假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。33分析可能出现的不匹配的情况:1)到来的右括弧并非是所“期待”的；2)到来的是“不速之客”；3)直到结束，也没有到来所“期待”的括弧。不正确的格式：［（］）或（［］））或（［（）］34算法的设计思想:1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。[([][])][([])[]][([[35括号匹配算法: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左括号多余!");}36例2、数制转换算法基于原理：

N=(Ndivd)×d+Nmodd计算顺序输出顺序例如：（1348)10=(2504)8

，其运算过程如下：

NNdiv8Nmod8

13481684

168210

2125

20237十进制转换为二进制（例如：25）有余数是1没余数是025除2=12......112除2=6......06除2=3......03除2=1......11除2=0......1然后我们将余数按“从下往上”的顺序书写就是：11001，那么这个11001就是十进制25的二进制形式top11100toptop出栈：toptoptoptoptop数制转换算法voidConversion(intN)

/*对任意非负十进制数N，打印等值的八进制数*/{StackS;intx;/*S为顺序栈或链栈*/InitStack(&S); while(N>0) {x=N%8;Push(&S,x);N=N/8;} while(！IsEmpty(S)) {Pop(&S,&x);printf(“%d”,x);} }393.1.4栈与递归的实现

当在一个函数的运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三项任务：

将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。40

从被调用函数返回调用函数之前,应该完成下列三项任务：

保存返回的计算结果(用函数名,引用参数)

；释放被调函数的数据区(局部量)；依照被调函数中保存的返回地址将控制转移到调用函数。41多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：main(){voida(){voidb(){………a();b();……}//main}//a}//bmain的数据区函数a的数据区函数b的数据区

每个函数数据区含：参数、局部变量、返回地址等信息42递归工作栈:递归函数执行过程中占用的数据区工作记录:每一层的参数、局部变量、返回地址等构成的记录(数据区)当前活动记录:栈顶工作记录(当前函数数据区)当前环境指针:递归工作栈的栈顶指针,指向当前活动记录。(指示当前函数数据区)可见：栈是函数过程嵌套调用及递归调用管理的有效手段

递归函数执行过程是直接或间接地调用自己,可视为同一函数自己对自己进行嵌套调用。例如：voida(){voida(){voidb(){………a();b();a();………}//a直接递归

}//a}//b间接递归

43例Hanoi塔问题：有3个塔座x,y,z,在塔座x上插有n个大小不同的圆盘,从小到大且自上而下编号为1,2,…n;按规则将它们一个个搬到塔座z上,y可用作辅助塔座。规则为：(1)每次只能移动一个圆盘；(2)圆盘可放在任意塔座上；(3)任何时刻塔座上都不得将大盘压在小盘之上。分析：n=1时：直接从塔座x移动到塔座z上；n>1时：先将上面的n-1个圆盘移到塔座y上,然后将n号盘移到塔座z上,再将y上的n-1个圆盘移到塔座z上。这样就将问题的规模缩小1,利用递归可实现。44voidhanoi(intn;charx,chary,charz)

/*将塔座x上按直径由小到大且至上而下编号为1至n的

n个圆盘按规则搬到塔座z上，y可用作辅助塔座。*/1

{2IF(n==1)3move(x,1,z);/*将1号盘从x移到z*/9}4ELSE{5hanoi(n-1,x,z,y);/*将x上n-1个盘移到y,z作辅助塔*/6move(x,n,z);/*将n号圆盘从x移到z*/7hanoi(n-1,y,x,z);/*将y上n-1个盘移到z,x作辅助塔*/8}45voidhanoi(intn;charx,chary,charz)1

{2IF(n==1)3move(x,1,z);4ELSE{hanoi(n-1,x,z,y);

move(x,n,z);hanoi(n-1,y,x,z);8}}调用程序:返回地址为0hanoi(3,'A','B','C);0......03ABC62ACB61ABC

81CAB

返址nxyz46ABC

…...move(x,1,z);1CAB…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);…...…...move(x,1,z);2BAC1BCA…...move(x,1,z);1ABC…...hanoi(n,'A','B','C');…...…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);…...…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);………...move(x,1,z);3ABCn,x,y,z2ACB1ABCmove(x,n,z);move(x,n,z);move(x,n,z);1A->C2A->B1C->B3A->C1B->A2B->C1A->C47

递归程序结构清晰、程序可读性强，且其正确性易于证明，给用户编程带来很大方便。

但递归程序效率很低(时、空两方面)，使用时多加权衡。当问题满足如下条件是，可设计地归算法：1、原问题可以层层分解为类似的子问题，子问题规模比原问题小；2、规模最小的子问题具有直接解。设计递归算法的方法是：1.寻找分解方法，将原问题分解为类似的子问题求解；2.设计递归出口,按最小规模子问题确定递归终止条件;483.2队列3.2.1队列的定义3.2.2

队列的表示和实现3.2.3队列的应用举例

队列(Queue)：只允许在表的一端进行插入,在表的另一端进行删除的线性表，又称先进先出(FirstInFirstOut,FIFO)线性表。允许插入的一端为队尾(rear,tail),允许删除的一端为队头(front)。它和日常生活中的排队是一致的,在操作系统中的作业排队就是它的典型应用。49ADTQueue{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

约定其中a1

端为队列头，an

端为队列尾基本操作：3.2.1队列的类型定义}

ADTQueue50队列的基本操作：InitQueue(Q)初始化构造一个空队列Q。IsEmpty(Q)若Q为空,则返回true,否则返回false。IsFull(Q)若Q为满,则返回true,否则返回false。EnterQueue(Q,e)入队,插入e为Q的新队尾元素。DeleteQueue(Q,*e)出队,若Q非空,则队头元素出队由e带回,并返回true,否则返回false。GetHead(Q,*e)取队头,若Q非空,由e带回队头元素,

并返回true,否则返回false。ClearQueue(Q)将Q清为空队列。513.2.2队列的表示和实现一、链队列typedefstructNode{QueueElementtypedatastructNode*next}LinkQueueNode/*结点类型*/typedefstruct{LinkQueueNode*front/*队头指针*/LinkQueueNode*rear/*队尾指针*/

}LinkQueue

/*链队列类型*/1、链队列存储结构定义52a1∧an…q.frontq.rearq.frontq.rear∧空队列LinkQueueq2、链队列示意图531)初始化intinitQueue(LinkQueue*q){q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));

/*申请头结点空间*/if(q->front!=null){q->rear=q->front;q->front->next=null;

/*头、尾指针均指向头结点*/return(true);}elsereturn(false);}

3、链队列基本操作的实现542)入队intEnterqueue(LinkQueue*q,QueueElementTypex){LinkQueueNode*newnode;

newnode

=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));/*申请新结点空间*/if(newnode!=null){newnode->data=x;newnode->next=null;/*构造结点*/

q->rear->next=newnode;q->rear=newnode;/*以尾插法方式插入结点*/return(true);}return(false);}

55intdeletequeue(LinkQueue*q,QueueElementType*x){LinkQueueNode*p;if(q->front==q->rear)/*空队列*/return(false);

p=q->front->next;/*找到要删除的元素*/

q->front->next=p->next;

/*重新链接q的队头元素*/if(q->rear==p)q->rear=q->front;/*若要删除的为队尾元素,即删除后队列为空,则修改尾指针*/*x=p->data;free(p);/*删除该元素*/

return(true);}

3）出队56二、循环队列

尽管链队列使用方便,但由于其指针多占存储空间,有时仍需要用顺序结构来表示队列。顺序队列中也需要两个“指针”：头指针front指示队头元素的当前位置；尾指针rear指示队尾元素的后一个位置。初始时front=rear=0。571、循环队列存储结构定义#definemaxsize50

QueueElementtypeQ[maxsize];/*保存队列元素值的数组*/

intfront,rear;/*队列的头为指针，全局变量*/58此时入队操作为：Q[rear]=x;rear=rear+1;

出队操作为：x=q[front]；front=front+1；

队空条件：rear=front假队满：rear==maxsize,队满：rear–front=maxsize或rear=frontrear–front＜maxsize假rearfrontDEGrearfrontAB