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

第3章栈和队列栈和队列也属于线性结构，它们的逻辑结构和线性表相同。存储方式有顺序和链式两种存储结构，只是其运算规则较线性表有更多的限制，因此，可以称为操作受限的线性表。1【本章重点】①栈和队列的操作特性；②基于顺序栈和链栈的基本运算的实现；③基于循环队列和链队列的基本运算的实现。2【本章难点】①多个栈共享空间的算法设计；②循环队列的组织及队空和队满的判定条件；③基于栈、队列的算法设计及应用。3【本章内容】栈队列栈和队列的应用举例习题343.1栈栈的定义：栈是限定仅在表的一端进行插入或删除操作的线性表。插入、删除的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈是一种后进先出的（LastInFirstOut）的线性表。栈可以是空栈或非空栈。对于非空栈S=(a1,a2,…,an),a1是栈底元素,an是栈顶元素。如果进栈的顺序是a1,a2,…,an，n个元素全部进栈后再出栈，其顺序正好相反。5栈的常用基本运算（1）InitStack(&S)栈初始化，操作结果是构造一个空栈S。（2）SetNull(S)置空栈，栈S已存在，将栈S清为空栈。（3）Empty(S)判断栈空，若栈S为空则返回“真”值；否则返回“假”值。（4）Push(S，x)进栈，若栈S不满，将数据元素x插入栈顶，并返回入栈是否成功的状态信息。入栈操作会改变栈的内容。（5）Pop(S,&x)出栈，若栈S非空，删除栈顶数据元素，通过参数x带回栈顶元素，并返回出栈是否成功的状态信息。出栈操作会使栈的内容发生变化。（6）GetTop(S,&x)取栈顶元素，若栈S非空，通过参数x带回栈顶元素，并返回取栈顶元素是否成功的状态信息。该操作完成后，栈的内容不变。6栈的基本运算应用举例【例3.1】将一个非负的十进制整数转换为其它进制数（二、八、十六进制），利用栈来实现。voidConversion(intn,intbase)//以十进制数和基数作为参数{ Stack*S;intbit; InitStack(S);//建立空栈

while(n!=0)

{ Push(S,n%base);//余数入栈

n=n/base; //整除基数

}

while(!EmptyStack(S))

{ bit=Pop(S);//余数出栈

if(bit>9)printf("%c",bit+55);//将余数转为字符输出

elseprintf("%c",bit+48); }

printf("\n");}7采用除基数取余的算法，例如将十进制数123转换为八进制数173，采用栈存放余数，入栈顺序是3、7、1，出栈顺序是1、7、3。栈的顺序存储结构和基本运算的实现1、栈的顺序存储结构——顺序栈

栈的顺序存储结构简称顺序栈。顺序栈采用一维数组来存储，并且用一个称为栈顶指针的整型量Top指示当前栈顶的位置。

顺序栈的类型定义如下： typedefstruct {

datatypedata[maxsize]; //栈中元素存储空间

intTop; //栈顶指针 }SeqStack;8如果把数组中下标为0的一端作为栈底，那么S->data[0]是栈底元素，S->data[S->Top]是栈顶元素。当S->Top=-1时为空栈，满栈时S->Top=maxsize-1。对于顺序栈，入栈时要先判断栈是否已满，栈满简称为“上溢”；出栈时需判断栈是否为空，栈空简称为“下溢”。入栈操作S->Top加一，出栈操作S->Top减一。2、顺序栈基本运算的实现（1）栈初始化 voidInitStack(SeqStack*&S) //构造一个空栈S {S=(SeqStack*)malloc(sizeof(SeqStack));//生成顺序栈空间

S->Top=-1; //栈顶指针置为-1 }（2）置空栈 voidSetNull(SeqStack*S) //将栈S置为空栈 {S->Top=-1; //栈顶指针置为-1 }9（3）判断栈空 intEmpty(SeqStack*S) //若栈S为空栈，返回1；否则返回0 { if(S->Top==-1)return1; elsereturn0; }（4）入栈 intPush(SeqStack*S,datatypex) //若栈S未满，则将元素x插入栈顶，并返回1，表示入栈成功；否则返回0，表示入栈不成功 { if(S->Top==maxsize-1) {printf("栈上溢"); return0; }//上溢 else {S->data[++S->Top]=x; return1; } }10（5）出栈

intPop(SeqStack*S,datatype&x)//若栈不空，则删除栈顶元素，由参数x带回栈顶元素，并返回1，表示出栈成功；否则返回0，表示出栈失败 {if(Empty(S))//判断栈是否为空

{printf("栈下溢");

return0;

}//下溢

else

{x=S->data[S->Top--];

return1;

} }11（6）取栈顶元素 intGetTop(SeqStack*S,datatype&x) //若栈不空，则删除栈顶元素，由x带回栈顶元素，并返回1，表示取栈顶元素成功；否则返回0，表示取栈顶元素失败 {if(EmptyS(S))//调用算法4.3，判断栈是否为空

{printf("栈下溢");

return0;

}//下溢

else

{x=S->data[S->Top];

return1;

} }12两个顺序栈共享连续空间，降低溢出的概率进栈操作的算法：voidpush(SeqStack*S,datatypex,inti)//将元素x插入i号栈{if(S->Top1+1==S->Top2)printf("数组空间已占满，发生上溢");elseif(i==1){S->Top1++;S->v[S->Top1]=x;} //入1号栈else{S->Top2--;S->v[S->Top2]=x;} //入2号栈}13出栈操作的算法：datatypepop(SeqStack*S,inti)//i号栈的栈顶元素出栈{datatypex;if(i==1)

if(S->Top1==-1)printf(“1号栈下溢”);

else{x=S->v[S->Top1];S->Top1--;}//1号栈出栈else

if(S->top2==maxsize)printf(“2号栈下溢”);

else{x=S->v[S->Top2];S->Top2++;}//2号栈出栈returnx;//返回出栈元素的值}14【例3.2】检查表达式中的括号是否匹配。

以表达式((1+2)*3-4)/5为例。表达式作为字符串存储在字符数组ex中，charex[]="((1+2)*3-4)/5";

在检查过程中，对字符数组进行扫描，当遇到“(”时入栈，遇到“)”时出栈。当整个表达式扫描完毕时，若栈为空，则表达式中的括号是匹配的；否则不匹配。voidcorrent(charex[]){ SeqStack*S; InitStack(S); i=0; while(i<length) { ch=ex[i]; switch(ch) { case'(':Push(S,ch);

break; case')':if(Empty(S)||Pop(S)!='(')

return"期望("; } i++; } if(!Empty(S)) return"期望)"; elsereturn"OK";}15栈的链式存储结构和基本运算的实现1、栈的链式存储结构栈的链接存储结构（链栈）用单链表来表示。链栈的结点结构类型定义如下：typedefstructnone{datatypedata; //data为结点的数据信息structnode*next; //next为后继结点的指针}StackNode; //链栈结点类型typedefstruct{StackNode*Top; //指向栈顶结点的指针}LinkStack;//含有栈顶指针Top的链栈结构体类型16将单链表的表头作为栈顶，由于只能在栈顶进行入栈和出栈操作，所以只能在单链表的表头进行插入和删除。17S是LinkStack类型的指针，指向链栈，可以看作是栈的接口。Top是栈顶指针，指向栈顶结点，当Top等于NULL时，为空栈。2、链栈基本运算的实现链栈的入栈和出栈都是在栈顶（单链表的表头）进行，所以算法的时间复杂度均为O(1)。18【算法3.7】建立空链栈。voidInitStack(LinkStack*&S)//构造一个空栈S{S=(LinkStack*)malloc(sizeof(LinkStack));S->Top=NULL;}【算法3.8】链栈置空。voidSetNull(LinkStack*S)//将栈S置为空栈{S->Top=NULL;}【算法3.9】链栈入栈。voidPush(LinkStack*S,datatypex)//将元素x入栈{StackNode*p=(StackNode*)malloc(sizeof(StackNode));

p->data=x;p->next=S->Top;//将新结点*p插入栈顶 S->Top=p;}19由于链栈不存在上溢的问题，所以在入栈时不需要判断栈满的情况20【算法3.10】链栈栈顶元素出栈。intPop(LinkStack*S,datatype&x)//若栈非空，则删除栈顶元素，由x带回栈顶元素，并返回1；否则返回0{StackNode*p=S->Top;//指针p指向栈顶结点if(Empty(S))//判断栈是否为空{printf("栈下溢");return0;}//下溢else{ x=p->data;

S->Top=p->next;//将栈顶结点*p从链上摘下

free(p);//释放原栈顶结点空间

return1;}}21【算法3.11】取链栈的栈顶元素。intGetTop(LinkStack*S,datatype&x)//若栈非空，则取栈顶元素，由x带回栈顶元素，并返回1；否则返回0{StackNode*p=S->Top;//指针p指向栈顶结点if(Empty(S))//判断栈是否为空{printf("栈下溢");return0;}//下溢else{ x=p->data;

return1;}}在链栈中取栈顶元素与出栈是类似的，只是没有下面两条语句：S->Top=p->next;//将栈顶结点*p从链上摘下free(p);//释放原栈顶结点空间3.2队列1、队列的定义及基本运算队列也是一种运算受限的线性表。它只允许在表的一端进行插入，该端称为队尾（Rear）；在表的另一端进行删除，该端称为队头（Front)。队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。当队列中没有元素时称为空队列。22队列的主要基本运算（1）InitQueue(&Q)队列初始化。构造一个空队列Q。（2）SetNull(Q)置空队。将队列Q清空。（3）Length(Q)求队列长度。返回队列中元素的个数。（4）Empty(Q)判空队。若队列Q为空队列，返回“真”值；否则返回“假”值。（5）EnQueue(Q,x)入队。若队列Q非满，将元素X插入Q的队尾。（6）DeQueue(Q)出队。若队列Q非空，删除队头元素，返回Q的队头元素。（7）GetFront(Q)取队头元素。若队列Q非空，返回Q的队头元素。Q中元素保持不变。23队列的基本运算应用【例】利用队列Q将栈S中的元素逆置。voidreverseS(Stack*S){InitQueue(&Q);while(!EmptyStack(S))EnQueue(Q,Pop(S));while(!Empty(Q))Push(S,DeQueue(Q));}241、队列的顺序存储结构——顺序队列队列的顺序存储结构称为顺序队列，采用数组存储队列中的元素。我们约定，在非空队列中队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置。（也可以约定，队头指针front指向队头元素的位置，队尾指针rear指向队尾元素的后一个位置）如果是空队，队头、队尾指针相等。队尾指针减去对头指针就是队列的长度。顺序队列的结构类型定义如下：typedefstruct{datatypedata[maxsize];intfront;intrear;}SeQueue;SeQueue*sq=(SeQueue*)malloc(sizeof(SeQueue));25队列的顺序存储结构和基本运算的实现循环队列

顺序队列中可能出现“上溢”和“下溢”情况，并且还存在“假上溢”现象，例如在教材中图3.6中的（c）或（d）的情况下，再进行入队操作，则出现“假上溢”。

循环队列可以解决“假上溢”问题。26sq->rear=(sq->rear+1)%maxsize;sq->front=(sq->front+1)%maxsize;在循环队列中区分空队和满队的方法在循环队列中，由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，在队空和队满时都有sq->front等于sq->rear，无法区分空队和满队。如果在循环队列中少用一个元素空间，则可以区分空队和满队。判断空队的条件：sq->rear==sq->front判断满队的条件：sq->front==(sq->rear+1)%maxsize272、循环队列基本运算的实现28【算法3.12】生成空循环队列。voidInitQueue(SeQueue*&sq)//建立空循环队列sq{ sq=(SeQueue*)malloc(sizeof(SeQueue));

sq->front=sq->rear=0;/*对于循环队列来说，只要队头和队尾指针相等即为空队，所以这里置为0~maxsize-1之间的任何一个值都可以，但一般置为0*/}【算法3.13】循环队列置空。voidSetNull(SeQueue*sq)//置队列sq为空队{sq->front=sq->rear=0;}29【算法3.14】求循环队列长度intLength(SeQueue*sq){return(sq->rear-sq->front+maxsize)%maxsize;}【算法3.15】循环队列入队。intEnqueue(sequeue*sq,datatypex)//将新元素x插入队列*sq的队尾，入队成功返回1，不成功返回0{ if(sq->front==(sq->rear+1)％maxsize) {printf("队列上溢");return(0);} else{sq->rear=(sq->rear+1)％maxsize;sq->data[sq->rear]=x;return(1); }}30【算法3.16】循环队列出队intDequeue(SeQueue*sq,datatype&x)//通过参数x带回该元素值，出队成功返回1，不成功返回0{ if(sq->rear==sq->front) {printf("队列下溢");return(0);} else{sq->front=(sq->front+1)％maxsize;x=sq->data[sq->front];return(1); }}31【算法3.17】取循环队列的队头元素intGetFront(SeQueue*sq,datatype&x)//通过参数x带回该元素值，取队头元素成功返回1，不成功返回0{if(sq->rear==sq->front){

printf("队列下溢");return(0);}

else{

x=sq->data[(sq->front+1)%maxsize];

return(1);

}}32【例】如果循环队列只有头指针front和队列长度len，实现队列的基本运算。结构类型定义如下：typedefstruct{datatypedata[maxsize];intfront,len;}sequeue;sequeue*sq;说明：由于可以区分空队和满队，所以不需要少用一个存储单元。空队：sq->len==0成立满队：sq->len==maxsize成立33（1）队列初始化voidinit(sequeue*&sq){sq=(sequeue*)malloc(sizeof(sequeue));sq->front=maxsize-1;sq->len=0;}（2）置空队voidsetnull(sequeue*sq){sq->len=0;}34（3）判队空intempty(sequeue*sq){if(sq->len==0)return(1);elsereturn(0);}（4）入队intenter(sequeue*sq,datatypex){if(sq->len==maxsize){printf(“queueisfull”);return(0);}//队列中最多可容纳maxsize个元素

else{sq->len++;sq->data[(sq->front+sq->len)%maxsize]=x;return(1);}}入队时队尾指针的操作，相当于：sq->len++;(sq->front+sq->len)%maxsize35（5）出队intdel(sequeue*sq,datatype&x){if(empty(sq)){printf(“queueisempty”);return(0);}else{sq->front=(sq->front+1)%maxsize;sq->len--;x=sq->data[sq->front];return(1);}}（6）取队头元素intget(sequeue*sq,datatype&x){if(empty(sq){printf(“queueisempty”);return(0);}else{x=sq->data[(sq->front+1)%maxsize];return(1);}}队列的链式存储结构和基本运算的实现链队列的结构类型定义：typedefstructnode{datatypedata;structnode*next;}QueueNode;//链队列的结点类型typedefstruct{QueueNode*front,*rear;}LinkQueue;//队头、队尾指针的结构体类型LinkQueue*q;将链队列的头指针和尾指针封装在一起，作为一个结构体类型q为LinkQueue类型的指针36链队列基本运算的实现37算法3.18生成空链队列。voidInitQueue(LinkQueue*&q){q=(LinkQueue*)malloc(sizeof(LinkQueue));//产生队头、队尾指针结构体q->front=q->rear=(QueueNode*)malloc(sizeof(QueueNode));//产生头结点q->front->next=NULL;//头结点指针域置空}算法3.19链队列置空。voidSetNull(LinkQueue*q){q->rear=q->front; //尾指针也指向头结点q->front->next=NULL; //头结点指针域置空}算法3.20链队列判空队。intEmpty(LinkQueue*q){if(q->front==q->rear)return(1);elsereturn(0);}38算法3.21链队列入队。voidEnQueue(LinkQueue*q,datatypex)//将新元素x加入链队列*q{q->rear->next=(QueueNode*)malloc(sizeof(QueueNode));//新结点插入队尾q->rear=q->rear->next;//尾指针指向新结点q->rear->data=x;//给新结点赋值q->rear->next=NULL;//队尾结点的指针域置空}//链队列不会出现“上溢”的情况，入队时不需要判断队满39算法3.22链队列出队。intDeQueue(LinkQueue*q,datatype&x)//通过参数x带回该元素值，出队成功返回1，不成功返回0{QueueNode*s;if(Empty(q)){printf("队列下溢");return(0);}else{s=q->front->next;//s指向被删除的队头结点

if(s->next==NULL){//当前链队列的长度等于1，出队后为空队

q->front->next=NULL;q->rear=q->front;//置为空队

}

elseq->front->next=s->next;//队列的长度大于1，修改头结点的指针域

x=s->data;

free(s);//释放被删除的结点空间

return(1);

}}40算法3.23取链队列的队头元素。intGetFront(LinkQueue*q,datatype&x)//通过参数x带回队头元素值，取队头元素成功返回1，不成功返回0{if(Empty(q)){printf("队列下溢");return(0);}else{x=q->front->next->data;return(1);}}例4.3用带有头结点的循环链表表示队列，并且只设队尾指针rear，编写入队和出队算法。可以将rear->next->next看作队头指针。根据队列长度的不同，出队操作需考虑出队之前队列为空队、长度等于1和大于1三种不同的情况。如果出队之前队列长度为1，那么出队之后就是空队了。（1）入队算法41voidEnQueue(QueueNode*&rear,datatypex){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));p->data=x; p->next=rear->next; rear->next=p; rear=p;}（2）出队算法42intDelQueue(QueueNode*&rear,datatype&x){QueueNode*p;if(rear==rear->next){printf("队列下溢");return(0);}else{ p=rear->next->next;x=p->data;

if(p==rear){

rear=rear->next;rear->next=rear; }//原队列长度等于1

elserear->next->next=p->next;//原队列长度大于1

free