第3章栈和队列

数据结构第3章栈和队列-2-栈和队列的逻辑结构栈和队列的顺序存储及运算实现栈和队列的链式存储及运算实现栈和队列的应用掌握栈的逻辑结构、存储结构及运算的实现方法掌握队列的逻辑结构、存储结构及运算的实现方法栈和队列的运算实现第3章栈和队列内容要求重点第3章栈和队列——栈栈的定义栈是一种只能在一端进行插入或删除操作的线性表。栈顶与栈底：表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。进栈：插入操作出栈：删除操作栈也称为后进先出表-3-栈顶栈底出栈进栈栈示意图…第3章栈和队列——栈栈的定义栈的抽象数据类型定义ADTStack {数据对象：D={ai|1≤i≤n,n≥0}

数据关系：r={<ai,ai+1>|ai,ai+1∈D,1≤i≤n-1}

基本运算：InitStack(&s)：初始化栈。 DestroyStack(&s)：销毁栈。 StackEmpty(s)：判断栈是否为空。 Push(&S,e)：进栈。 Pop(&s,&e)：出栈。 GetTop(s,&e)：取栈顶元素。 }-4-第3章栈和队列——栈例3.1设有4个元素a、b、c、d进栈，给出它们所有可能的出栈次序。解：所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba

-5-dcba第3章栈和队列——栈栈的顺序存储结构顺序栈类型SqStack-6-typedefstruct{ElemTypedata[MaxSize]；

inttop； //栈顶指针}SqStack；第3章栈和队列——栈栈的顺序存储结构顺序栈运算-7-顺序栈4要素：

栈空条件：top=-1

栈满条件：top=MaxSize-1

进栈e操作：top++;将e放在top处退栈操作：从top处取出元素e;top--;第3章栈和队列——栈栈的顺序存储结构顺序栈运算初始化栈initStack(&s)撤销栈ClearStack(&s)-8-voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}voidDestroyStack(SqStack*&s){

free(s);}第3章栈和队列——栈栈的顺序存储结构顺序栈运算判断栈是否为空StackEmpty(s)进栈Push(&s,e)-9-boolStackEmpty(SqStack*s){

return(s->top==-1);}boolPush(SqStack*&s,ElemTypee){

if(s->top==MaxSize-1)//栈满的情况，即栈上溢出

returnfalse;s->top++; //栈顶指针增1s->data[s->top]=e; //元素e放在栈顶指针处

returntrue;}第3章栈和队列——栈栈的顺序存储结构顺序栈运算出栈Pop(&s,&e)-10-boolPop(SqStack*&s,ElemType&e){if(s->top==-1) //栈为空的情况，即栈下溢出

returnfalse;e=s->data[s->top]; //取栈顶指针元素的元素

s->top--; //栈顶指针减1returntrue;}第3章栈和队列——栈栈的顺序存储结构顺序栈运算取栈顶元素GetTop(s)-11-boolGetTop(SqStack*s,ElemType&e){

if(s->top==-1) //栈为空的情况，即栈下溢出

returnfalse;e=s->data[s->top]; //取栈顶指针元素的元素

returntrue;}第3章栈和队列——栈例3.4编写一个算法利用顺序栈判断一个字符串是否是对称串。-12-boolsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;InitStack(st); //初始化栈

for(i=0;str[i]!='\0';i++) //将串所有元素进栈

Push(st,str[i]); //元素进栈

for(i=0;str[i]!='\0';i++){ Pop(st,e); //退栈元素e if(str[i]!=e) //若e与当前串元素不同则不是对称串

{DestroyStack(st); //销毁栈

returnfalse; }}DestroyStack(st); //销毁栈

returntrue;}第3章栈和队列——栈栈的链式存储链栈类型LiStack：-13-typedefstructlinknode{ElemTypedata; //数据域

structlinknode*next; //指针域}LiStack;第3章栈和队列——栈栈的链式存储链栈四要素：链栈操作初始化栈initStack(&s)-14-

栈空条件：s->next=NULL

栈满条件：不考虑进栈e操作：将包含e的节点插入到头节点之后退栈操作：取出头节点之后节点的元素并删除之voidInitStack(LiStack*&s){s=(LiStack*)malloc(sizeof(LiStack));s->next=NULL;}第3章栈和队列——栈栈的链式存储链栈操作撤销栈DestroyStack(&s)-15-voidDestroyStack(LiStack*&s){

LiStack*p=s,*q=s->next;while(q!=NULL){ free(p); p=q; q=p->next;}free(p); //此时p指向尾节点,释放其空间}第3章栈和队列——栈栈的链式存储链栈操作判断栈是否为空StackEmpty(s)进栈Push(&s,e)-16-boolStackEmpty(LiStack*s){return(s->next==NULL);}voidPush(LiStack*&s,ElemTypee){LiStack*p;p=(LiStack*)malloc(sizeof(LiStack));p->data=e; //新建元素e对应的节点*pp->next=s->next; //插入*p节点作为开始节点

s->next=p;}第3章栈和队列——栈栈的链式存储链栈操作出栈Pop(&s,&e)-17-boolPop(LiStack*&s,ElemType&e){LiStack*p;if(s->next==NULL) //栈空的情况

returnfalse;p=s->next; //p指向开始节点

e=p->data;s->next=p->next; //删除*p节点

free(p); //释放*p节点

returntrue;}第3章栈和队列——栈栈的链式存储链栈操作取栈顶元素GetTop(s,e)-18-boolGetTop(LiStack*s,ElemType&e){if(s->next==NULL) //栈空的情况

returnfalse;e=s->next->data;returntrue;}第3章栈和队列——栈栈的链式存储例3.5编写一个算法判断输入的表达式中括号是否配对（假设只含有左、右圆括号）。解题思路在表达式括号配对时返回true，否则返回false设置一个顺序栈St，扫描表达式exp，遇到左括号时进栈遇到右括号时：若栈顶为左括号，则出栈，否则返回false当表达式扫描完毕，栈为空时返回true；否则返回false-19-第3章栈和队列——栈boolMatch(charexp[],intn){inti=0;chare;boolmatch=true;SqStack*st;InitStack(st); //初始化栈

while(i<n&&match) //扫描exp中所有字符

{ if(exp[i]=='(') //当前字符为左括号,将其进栈

Push(st,exp[i]); elseif(exp[i]==')') //当前字符为右括号

{if(GetTop(st,e)==true) { if(e!='(') //栈顶元素不为'('时表示不匹配

match=false; else Pop(st,e);//将栈顶元素出栈

} elsematch=false;//无法取栈顶元素时表示不匹配

} i++; //继续处理其他字符

}if(!StackEmpty(st)) //栈不空时表示不匹配

match=false;DestroyStack(st); //销毁栈

returnmatch;}-20-第3章栈和队列——队列队列的定义队列是一种仅允许在表的一端进行插入，而在另一端进行删除的线性表队尾（rear）：允许插入的一端队头（front）：允许删除的一端入队：向队列中插入新元素，新元素进队后就成为新的队尾元素出队：从队列中删除元素元素，其后继元素就成为队首元素队列又称为先进先出表-21-第3章栈和队列——队列队列的定义队列的抽象数据类型定义ADTStack {数据对象：D={ai|1≤i≤n,n≥0}

数据关系：r={<ai,ai+1>|ai,ai+1∈D,1≤i≤n-1}

基本运算：InitQueue(&q):初始化队列。 DestroyQueue(&q):撤销队列。 QueueEmpty(q):判断队列是否为空。 enQueue(&q,e):进队列。 deQueue(&q,&e):出队列。 }-22-第3章栈和队列——队列队列的顺序存储顺序队列类型SqQueue定义-23-typedefstruct{ ElemTypedata[MaxSize]；

intfront,rear；//队首和队尾指针

}SqQueue;第3章栈和队列——队列队列的顺序存储顺序队列运算顺序队的四要素（初始时front=rear=-1）队空条件：front=rear队满条件：rear＝MaxSize－1元素e进队：rear++;data[rear]=e;元素e出队：front++;e=data[front];-24-第3章栈和队列——队列队列的顺序存储顺序队列运算初始化队列InitQueue(q)销毁队列DestroyQueue(q)-25-voidInitQueue(SqQueue*&q){

q=(SqQueue*)malloc(sizeof(SqQueue));

q->front=q->rear=-1;}voidDestroyQueue(SqQueue*&q){free(q);}第3章栈和队列——队列队列的顺序存储顺序队列运算判断队列是否为空QueueEmpty(q)进队列enQueue(q,e)-26-boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}boolenQueue(SqQueue*&q,ElemTypee){if(q->rear==MaxSize-1) //队满上溢出

returnfalse; q->rear++; q->data[q->rear]=e; returntrue;}第3章栈和队列——队列队列的顺序存储顺序队列运算出队列deQueue(q,e)-27-booldeQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear) //队空下溢出

returnfalse;q->front++;e=q->data[q->front];returntrue;}第3章栈和队列——队列队列的顺序存储循环队列运算把存储队列元素的表从逻辑上看成一个环，称为循环队列-28-循环队列的四要素：队空条件：front=rear队满条件：(rear+1)%MaxSize=front进队操作：rear=(rear+1)%MaxSize;出队操作：ront=(front+1)%MaxSize;第3章栈和队列——队列队列的顺序存储循环队列运算初始化队列InitQueue(q)销毁队列ClearQueue(&q)-29-voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));q->front=q->rear=0;}voidDestroyQueue(SqQueue*&q){

free(q);}第3章栈和队列——队列队列的顺序存储循环队列运算判断队列是否为空QueueEmpty(q)进队列enQueue(q,e)-30-boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}boolenQueue(SqQueue*&q,ElemTypee){if((q->rear+1)%MaxSize==q->front)//队满上溢出

returnfalse;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;returntrue;}第3章栈和队列——队列队列的顺序存储循环队列运算出队列deQueue(q,e)-31-booldeQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear) //队空下溢出

returnfalse;q->front=(q->front+1)%MaxSize;e=q->data[q->front];returntrue;}第3章栈和队列——队列队列的链式存储链队列类型-32-单链表中数据节点类型QNode:typedefstructqnode{ElemTypedata;

structqnode*next;}QNode;链队中头节点类型LiQueue:typedefstruct{QNode*front;//指向链队头节点

QNode*rear;//指向链队尾节点}LiQueue;第3章栈和队列——队列队列的链式存储链队列运算-33-链队的4要素：队空条件：front=rear=NULL队满条件：不考虑进队操作：将包含e的节点插入到单链表表尾出队操作：删除单链表首数据节点第3章栈和队列——队列队列的链式存储链队列运算初始化队列InitQueue(q)判断队列是否为空QueueEmpty(q)-34-voidInitQueue(LiQueue*&q){q=(LiQueue*)malloc(sizeof(LiQueue));q->front=q->rear=NULL;}boolQueueEmpty(LiQueue*q){

return(q->rear==NULL);}第3章栈和队列——队列队列的链式存储链队列运算撤销队列DestroyQueue(q)-35-voidDestroyQueue(LiQueue*&q){QNode*p=q->front,*r;//p指向队头数据节点

if(p!=NULL) //释放数据节点占用空间

{r=p->next; while(r!=NULL) {free(p); p=r;r=p->next; }}free(p);free(q); //释放链队节点占用空间}第3章栈和队列——队列队列的链式存储链队列运算入队enQueue(q,e)-36-voidenQueue(LiQueue*&q,ElemTypee){QNode*p;p=(QNode*)malloc(sizeof(QNode));p->data=e;p->next=NULL;if(q->rear==NULL)//若链队为空,新节点是队首节点又是队尾节点

q->front=q->rear=p;else{q->rear->next=p;//将*p节点链到队尾,并将rear指向它

q->rear=p;}}第3章栈和队列——队列队列的链式存储链队列运算出队deQueue(q,e)-37-booldeQueue(LiQueue*&q,ElemType&e){QNode*t;if(q->rear==NULL)returnfalse; //队列为空

t=q->front; //t指向第一个数据节点

if(q->front==q->rear)//队列中只有一个节点时

q->front=q->rear=NULL;else //队列中有多个节点时

q->front=q->front->next;e=t->data;free(t);returntrue;}第3章栈和队列——应用求解迷宫问题求出从入口到出口的路径-38-01234567890123456789(i-1,j)方位0(i+1,j)方位2(i,j+1)方位1(i,j-1)方位3(i，j)入口出口采用“穷举求解”的方法为了保证在任何位置上都能沿原路退回（称为回溯），需要用一个后进先出的栈来保存从入口到当前位置的路径。

第3章栈和队列——应用求解迷宫问题为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.6所示的迷宫,对应的迷宫数组mg如下:-39-intmg[M+2][N+2]={ //M=8,N=8 {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}};-40-111122222321331340240

141151162263253012345678901234567892-125-1第3章栈和队列——应用第3章栈和队列——应用为了便于回溯，对于可走的方块都要进栈，并试探它的下一可走的方位，将这个可走的方位保存到栈中，为此将栈定义为:-41-typedefstruct{inti; //当前方块的行号

intj; //当前方块的列号

intdi; //di是下一可走相邻方位的方位号}Box; //定义方块类型typedefstruct{Boxdata[MaxSize];inttop; //栈顶指针}StType; //顺序栈类型第3章栈和队列——应用-42-01234567890123456789

迷宫路径如下: (1,1)(1,2)(2,2)(3,2)(3,1) (4,1)(5,1)(5,2)(5,3