03 第3章 栈和队列.pptx

第1页：第三章栈和队列

第三章栈和队列

第2页：栈和队列的特点

栈和队列的特点

• 栈和队列是线性表
• 是操作受限制的线性表
• 栈是后进先出（LastInFirstOut,LIFO）线性表
• 队列是先进先出(FirstInFirstOut,FIFO)线性表

第3页：第三章内容提要

内容提要:

• 目的：学习栈和队列的定义、表示方法、实现、应用实例
• 第一节栈的定义、表示与实现
• 第二节栈的引用举例
• 第三节队列
• 本章重点

第4页：第一节栈的定义、表示与实现

第一节栈的定义、表示与实现

第5页：1.1抽象数据类型栈的定义

1.1抽象数据类型栈的定义

• 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，例如：铁路调度
• 表尾端称为栈顶(Top)，表头端称为栈底(bottom)
• 例如：设栈S=(a1,a2,…,an),则a1为栈底元素，an为栈顶元素进栈次序是a1,a2,…,an出栈次序是an,an-1,…,a1anan-1…a2a1栈底出栈进栈栈顶

第6页：栈的后进先出特性

栈又称后进先出(LastInFirstOut)线性表

• 基本操作：
• 插入、删除、初始化、判空、取栈顶元素

第7页：ADTStack的定义

ADTStack{

• 数据对象：D={ai|aiElemset, i=1,2,…,n,n0}
• 数据关系：R={< ai-1,ai>|ai-1,aiD,i=2,…,n}
• 基本操作：InitStack(&S)//构造一个空栈DestroyStack(&S)//消毁栈SStackEmpty(S)//将栈清空StackLength(S)//求栈的长度GetTop(S,,&e)//用e返回栈顶元素Push(&S,e)//插入元素e为新的栈顶元素Pop(&S,&e)//删除栈顶元素，并用e返回…………
• }ADTStack1.2栈的抽象数据类型定义

第8页：1.3栈的表示和实现

1.3栈的表示和实现

• 和线性表一样，栈有两种存储表示方法
• 顺序表示
• 链式表示

第9页：顺序栈的栈顶指针与栈空栈满

543210ABCDEFtop=0543210栈空栈顶指针top,指向实际栈顶后的空位置，初值为0543210进栈top出栈栈满FEDCBA设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptoptoptoptoptoptoptoptop栈空1.3.1栈的顺序表示（静态数组）

第10页：1.3.1栈顶指针与栈元素关系

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素

• 同时设置栈顶指针(top)和栈底指针(base)
• top=base表示栈空；增加一个元素，top增加1；删除栈顶元素，top减1
• 非空栈顶指针始终在栈顶元素的上一个位置topbaseAtopbaseABCtopDABbasebasetop栈顶指针和栈中元素之间的关系1.3.1栈的顺序表示（动态分配）

第11页：栈的顺序存储表示

栈的顺序存储表示

• #defineSTACK_INIT_SIZE100//初始分配量
• #defineSTACKINCREMENT10//分配增量
• Typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间
• }SqStack;

第12页：顺序栈的基本操作

基本操作

• InitStack(SqStack&S)//构造一个空栈
• DestroyStack(SqStack&S)//消毁栈S
• StackEmpty(SqStackS)//将栈清空
• StackLength(SqStackS)//求栈的长度
• GetTop(SqStackS,SElemType&e)//用e返回栈顶元素
• Push(SqStack&S,SElemTypee)//插入元素e为新的栈顶元素
• Pop(SqStack&S,SElemType&e)//删除栈顶元素，并用e返回…………

第13页：构造空栈算法

顺序表示算法描述 构造一个空栈 StatusInitStack(SqStack&S){ S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);S.stacksize=STACK_INIT_SIZE; returnOK; }

第14页：取栈顶元素算法

返回栈顶元素给e StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base)returnERROR//栈中无元素e=*(S.top–1); returnOK; }

第15页：入栈算法Push

插入元素e为栈顶元素 StatusPush(SqStack&S,SElemTypee){ if(S.top-S.base=S.stacksize){if(!S.base)exit(OVERFLOW);S.stacksize+=STACKINCREMENT; } *S.top++=e; returnOK; }

第16页：出栈算法Pop

删除栈顶元素，并用e返回 StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)returnERROR//栈中无元素e=*--S.top; returnOK } 
第17页：1.3.2栈的链式表示
1.3.2栈的链式表示
当栈的长度无法估计时最好用栈的链式表示
TypedefstructSNode{SElemTypedata;structSNode*next;
}*Link,*StackPtr;
Typedefstruct{Linktop;intlen;
}ListStack;栈顶栈底S.topdatanext
第18页：链栈的入栈算法
链式表示算法描述 插入元素e为栈顶元素 StatusPush(ListStack&S,SElemTypee){ p=(StackPtr)malloc(sizeof(SNode))//生成一个结点p->data= e; p->next=S.top; S.top=p; S.len++; returnOK; }
第19页：链栈的出栈算法
删除栈顶元素，并用e返回 StatusPop(ListStack&S,SElemType&e){ if(S.top=NULL)returnERROR;S.top=S.top->next; e =p->data; free(p);returnOK; }
第20页：栈的压入和弹出应用程序
栈的线性链表的压入和弹出应用程序
第21页：第二节栈的应用举例
第二节栈的应用举例
第22页：栈的后进先出应用价值
栈结构具有后进先出的特性，是程序设计的有用工具
例如
数制转换
括号匹配的检验当前输入的括号总是与前一个输入的括号相配
行编辑程序
迷宫求解
表达式求值
第23页：2.1数制转换
2.1数制转换
十进制数N和其它d进数的转换是计算机实现计算的基本问题，原理是:N=(Ndivd)*d+Nmodd(div整除，mod求余)
例如(1348)10=(2504)8的运算过程为：Nmod8Ndiv8N
41681348
021168
5221
202
这个过程是从低位到高位顺序产生八进制数的各个位，如果先依次压入一个堆栈，然后就可从高位到低为弹出，弹出的结果就是八进制数
利用栈实现上述过程可以简化程序
第24页：算法3.1十进制转八进制
算法3.1十进制转换为八进制
Voidconversion(){
InitStack(S);
Scanf(“%d”,N);//输入整型数
While(N)
{Push(S,N%8)//将余数压入栈N=N/8;//取整后赋给原变量N
}
while(!StackEmpty(S))//如果栈不为空
{Pop(S,e);Printf(“%d”,e);//打印
}
}
第25页：2.2括号匹配的检验
2.2括号匹配的检验
实例，假设只有圆括号和方括号
[([][])]
12345678
则4与3配，6与5配，7与2配，8与1配
括号匹配的检验思路是：需要匹配的括号期待的紧急程度是后输入的括号高于前面输入的括号，所以可以用一个堆栈来放表达式的括号，后进栈的括号期待紧急程度最高
第26页：2.3行编辑程序
2.3行编辑程序
行编辑程序的基本思路是：设置一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区
允许用户使用退格符（#）和退行符（@）
例如:whli##ilr#e(s#*s)outcha@putchar(*s=#++)
的实际有效行为：while(*s)putchar(*s++)
第27页：行编辑程序的算法思路
算法思路：
设置一个缓冲区为栈结构，每接受一个字符进行以下判断
不是退格符也不是退行符，将该字符压入栈顶
如果是退格符，则从栈顶删去一个字符
如果是退行符，则栈清空
第28页：算法3.2行编辑程序实现
VoidLineEdit(){
InitStack(S);
ch=getchar();
while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘\n’){//‘\n’为换行符switch(ch){case‘#’:Pop(S,c);break;//删除符case‘@’:ClearStack(S);break;//退行符default:Push(S,ch);break;}ch=getchar();}//while2算法3.2行编辑程序
第29页：行编辑程序续：栈内容传送
//将栈内的所有字符传输到调用这个过程的数据区（全局变量或成员变量）ClearStack(S);if(ch!=EOF)ch=getchar();
}//while1
DestroyStack(S);
}
第30页：2.4表达式求值
2.4表达式求值
算术运算规则：先乘除后加减，从左到右，括号内优先
设计两个栈实现表达式运算，一个称做OPTR，用以寄存运算符；一个称做OPND，用以寄存操作数或计算结果
算法的基本思路是：
置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素
依次读入表达式中的每个字符
若是操作数则进OPND；
若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作，直到整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）
第31页：算法3.4表达式求值操作
算法3.4表达式求值操作
OperandTypeEvaluateExpression(){
//OPTR和OPND分别为运算符栈和运算数栈
InitStack(OPTR);Push(OPTR,’#’);
InitStack(OPND);c=getchar();
while(c!=‘#’||GetTop(OPTR)!=‘#’){
if(!In(c,OP) {Push(OPND,c);c =getchar();}//不是运算符，进OPND栈
else
switch(Precede(GetTop(OPTR),c){//与OPTR栈顶运算符比较
case‘<‘://栈顶元素优先权低Push(OPTR,c);c=getchar();break;如3*(7-2)中，-的优先权高于)，要进行7-2运算
第32页：算法3.4续：运算符优先级比较
case‘=‘://脱括号并接受下一字符，括号才会出现相等情形（见表3.1）Pop(OPTR,x);c=getchar();break;
case‘>’://栈顶元素优先权高，退栈并将运算结果入OPND栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));Break;
}//switch
}//while
returnGetTop(OPND);
}
第33页：第四节队列
第四节队列
第34页：4.1抽象数据类型队列的定义
4.1抽象数据类型队列的定义
和栈相反，队列(Queue)是一种先进先出（FirstInFirstOut)的线性表
只允许在表的一端进行插入，而在另一端删除元素，如日常生活中的排队现象
允许插入的一端叫队尾(rear)，允许删除的一端称队头(front)
假设队列为q=(a1, a2, …, an),则a1为队头元素，an为队尾元素
队列中出队的顺序和进队顺序一致…a1a2a1an出队列入队列队头队尾
第35页：队列在程序设计中的应用
程序设计中：操作系统的作业排队
基本操作与栈类似
初始化、清空、销毁
求长度、得到对头元素
插入、删除
第36页：ADTQueue的定义
ADTQueue{
数据对象：D={ai|aiElemset,i=1,2,…,n,n0}
数据关系：R={< ai-1,ai>|ai-1,aiD,i=2,…,n}
基本操作：InitQueue(&Q)//构造一个空队列DestroyQueue(&Q)//消毁队列QQueueEmpty(Q)//队列为空，返回TrueQueueLength(Q)//求队列的长度GetHead(Q,&e)//用e返回队头元素EnQueue(&Q,e)//插入元素e队对尾元素DeQueue(&Q,&e)//删除队头元素，并用e返回…………
}ADTQueue队列的抽象数据类型定义
第37页：4.2队列的链式表示和实现
4.2队列的链式表示和实现
用链表来表示的队列，简称链队列
需要两个分别指向队头和队尾的指针
与线性表的单链表类似，设置头结点
队列为空的条件是队头指针和队尾指针均指向头结点
链队列的操作为单链表的插入和删除操作的特殊情况队头队尾Q.frontdatanextQ.rear
第38页：链队列指针变化情况
(1)队列指针变化情况Q.frontQ.rearQ.frontQ.rearxQ.frontQ.rearxyQ.frontQ.rearxy空队列元素x入队元素y入队元素x出队
第39页：链队列的链式存储结构
(2)链队列的链式存储结构
TypedefstructQNode{QElemTypedata;StructQNode*next;
}QNode,*QueuePtr;
Typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针
}LinkQueue;
第40页：链队列的基本操作
基本操作
InitQueue(LinkQueue&Q)//构造一个空队列
DestroyQueue(LinkQueue&Q)//消毁队列Q
QueueEmpty(LinkQueueQ)//队列为空，返回True
QueueLength(LinkQueueQ)//求队列的长度
GetHead(LinkQueueQ, &e)//用e返回队头元素
EnQueue(LinkQueue&Q,e)//插入元素e队对尾元素
DeQueue(LinkQueue&Q,&e)//删除队尾元素，并用e返回
…………
第41页：构造空队列算法
(3)基本操作实现算法StatusInitQueue(LinkQueue&Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK; }
第42页：销毁队列算法
//销毁队列Q StatusDestroyQueue(LinkQueue&Q){ while(Q.front){ Q.rear =Q.front->next; free(Q.front); Q.front =Q.rear;} returnOK; } (3)基本操作实现算法(续)
第43页：入队算法EnQueue
//插入元素e为Q的新的队尾元素 StatusEnQueue(LinkQueue&Q,QElemTypee){ p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=preturnOK; } Q.frontQ.rearxP(3)基本操作实现算法(续)
第44页：出队算法DeQueue
//若队列不为空，删除队头元素 StatusDeQueue(LinkQueue&Q,QElemType&e){ if(Q.front==Q.rear)returnEEROR; p=Q.front->next;Q.front->next =p->next; if(Q.rear==p)Q.rear=Q.front;returnOK; } Q.frontQ.rearxyP(3)基本操作实现算法(续)
第45页：链式队列的算法应用程序
链式队列的算法应用程序
第46页：队列的顺序表示和实现
4.2队列的顺序表示和实现
用一组地址连续的存储单元依次存放从队头到队尾的元素
还需要设置两个指针分别指向队头元素和队尾元素
初始化时Q.front=Q.rear=0,插入元素时尾指针加1，删除元素时，头指针增加1Q.rearQ.front01234J2J3J3J4J5Q.frontQ.rearQ.rearQ.frontJ1Q.frontQ.rear
第47页：顺序队列的一维数组实现
队列的顺序存储结构(一维数组实现sq[M]）432150队空rear=0front=0432150frontJ1,J1,J3入队J3J2J1rear432150J6J5J4J4,J5,J6入队设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=0,rear=0空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[front++];rearrearrear3front21450J1,J2,J3出队J1J2J3frontfrontfrontrearrearrearfrontrear
第48页：循环队列的提出
循环队列示意图一般情况Q.frontQ.rearJ3J4J567504132Q.front1Q.rearmaxsize-10队列
为保证插入新元素时不会使数组越界，并充分利用队头删除元素后的空间，可设计一个环行空间，循环队列
第49页：循环队列空与满的判断
队列满132Q.frontJ3J4Q.rearJ5J667504J7J8J9J1032167504Q.frontQ.rear空队列
注意：凭Q.front=Q.rear无法判断队列是满还是空
处理方法
另设置标志位
少用一个元素空间，队头指针在队尾指针的下一位置上时作为队列呈“满”标志处理方法：少用一个元素空间（队列满）Q.frontQ.rearJ3J4J2J8J5J667504132J1
第50页：循环队列的存储空间限制
注意：无法用动态分配的一维数组实现循环队列
方法：
设置一个最大队列长度
当无法估计时，采用链队列
第51页：循环队列的顺序存储结构
(1)循环队列的顺序存储结构
#defineMAXQSIZE100
Typedefstruct{QElemType*base;//动态空间intfront;//头指针，序号intrear;//尾指针，序号
}SqQueue;
第52页：循环队列构造空队列算法
(2)循环队列基本操作方法StatusInitQueue(SqQueue&Q){ Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0; returnOK; } 321054Q.front67Q.rear
第53页：求循环队列长度算法
//返回队列长度
intQueueLength(SqQueue&Q){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}(2)循环队列基本操作方法(续)0Q.frontQ.rearJ3J4J56754132（7-4+8）%8=3Q.frontQ.rearJ3J4J2J8J5J667504132J1（0-1+8）%8=7少用一个元素空间,队满
第54页：循环队列入队算法
(2)循环队列基本操作方法(续)StatusEnQueue(SqQueue&Q,QElemTypee){ if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.rear=(Q.rear+1)%MAXQSIZE;} Q.frontQ.rearJ3J4J2J8J5J667504132J1（0-1）%8=1=Q.front少用一个元素空间,队满
第55页：循环队列出队算法
//删除队头元素给e返回 StatusDeQueue(SqQueue&Q,QElemType&e){ if(Q.front=Q.rear)returnERROR;Q.front=(Q.front+1)%MAXQSIZE;} (2)循环队列基本操作方法
第56页：循环队列的算法应用程序
循环队列的算法应用程序
第57页：队列应用举例
(3)队列应用
模拟日常生活中的排队现象，例如
统计一天中顾客在银行逗留的时间，一个窗口一个队列，顾客来到时到客户最少的队排队
多CPU计算机时程序作业排队
第58页：本章重点
栈和队列的定义、特点
栈和队列的存储表示方法（结构设计）
栈和队列的插入与删除算法
应用举例：数制转换本章重点
第59页：习题（一）
习题：
1、栈的特点是先进后出，对列的特点是先进先出。
2、栈和对列的共同特点是只允许在端点插入和删除元素。
3、向一个栈顶指针为HS的链中插入一个s所指结点时，则执行：s->next=HS;HS=s;
4、向一个栈顶指针为HS的链中删除一个s所指结点时，用x保存被删除结点的值，则执行：x=HS->data;HS=HS->next;
5、判定一个队列QU（最多元素为MaxSize）为空的条件是:QU->front==QU->rear。
6、判定一个队列QU（最多元素为MaxSize）为满队列的条件是: QU->rear-QU->front==MaxSize。
第60页：习题（二）
7、判定一个循环队列QU（最多元素为MaxSize）为空的条件是:QU->front==QU->rear。
8、判定一个队列QU（最多元素为MaxSize）为满队列的条件是:QU->front==(QU->rear+1)%MaxSize。
8、循环队列用数组A[0,m-1]存放其元素，已知其头为指针分别是front和rear，则当当前队列元素个数是：(rear-front+m)%m。
9、在一个链队列中，假设f和r分别指向对头和队尾指针，则插入s所指结点的操作是：r->next=s;r=s习题：
第61页：习题（三）
10、回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符串是否是回文。提示：将一般字符入栈
11、编写一个算法，利用栈的基本运算将指定栈中的内容进行转换。
12、有两个栈s1和s2共享存储空间c[0…m0]，其中一个栈底设在c[1]处，另一个栈底设在c[m0]处，分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置空栈setnull(i)的函数，其中i=1,2。注意仅当整个空间c[0…m0]占满时才产生上益。习题：
第62页：习题（四）
13、栈的静态顺序存储结构为 #defineMAXSTACK500; typedefstructseqstack{ ElemTypedata[MAXSTACK]; inttop; } SQSTACK; SQSTACKss; 这时设置栈底位置固定在数组最低段，即top=-1表示栈空，栈中存放元素的位置是事实ss.data[0],…,ss.data[MAXSTACK-1]共MAXSTACK个元素，元素进栈ss.top加1，出栈减1，问： 栈空的条件是：ss.top=-1，栈满的条件是：ss.top=MAXSTACK-1，栈顶元素的表达式是：ss.data[ss.top]，栈底元素的表达式是：ss.data[0]。习题：
第63页：