《C语言数据结构第04讲栈.ppt》由会员分享，可在线阅读，更多相关《C语言数据结构第04讲栈.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实用数据结构基础实用数据结构基础第第3 3章章 栈栈第 3 3 章 栈 知识点栈的定义和特点栈的定义和特点栈的基本运算和算法栈的基本运算和算法栈的典型应用栈的典型应用难难点点后缀表达式的算法后缀表达式的算法数制的换算数制的换算利用本章的基本知识设计相关的应用问题利用本章的基本知识设计相关的应用问题要求掌握栈的特点掌握栈的特点掌握栈的基本运算掌握栈的基本运算熟悉栈的各种实际应用熟悉栈的各种实际应用能设计栈的应用的典型算法能设计栈的应用的典型算法了解栈的运算时间复杂度分析了解栈的运算时间复杂度分析第3 3章 目录31栈的定义与运算栈的定义与运算32栈的存储和实现栈的存储和实现33栈的应用举例栈的应
2、用举例小小结结实验实验3栈子系统栈子系统习题习题33-1 栈的定义和运算311栈（栈（Stack）的定义）的定义1.栈的定义栈的定义栈是限制在表尾进行插入和删除的线性表。栈是限制在表尾进行插入和删除的线性表。a1a2a3进栈进栈出栈出栈图图31栈的栈的示意图示意图2.栈的特性栈的特性（1）栈的主要特点是）栈的主要特点是“后进先出后进先出”（2）允允许许插插入入、删删除除的的这这一一端端称称为为栈栈顶顶（Top），另一端称为栈底（另一端称为栈底（Bottom）。）。3.应用实例应用实例（1）分币筒；）分币筒；（2）铁路调度站。）铁路调度站。312栈的运算栈的运算1进栈：进栈：Push（&s，x）
3、初始条件：栈初始条件：栈s已存在且非满。已存在且非满。操操作作结结果果：在在栈栈顶顶插插入入一一个个元元素素x，栈栈中中多多了了一一个元素。个元素。2出栈：出栈：Pop（&s）初始条件：栈初始条件：栈s存在且非空。存在且非空。操作结果：删除栈顶元素，栈中少了一个元素。操作结果：删除栈顶元素，栈中少了一个元素。3读栈顶元素：读栈顶元素：ReadTop（s，&e）初始条件：栈初始条件：栈s已存在且非空。已存在且非空。操作结果：输出栈顶元素，但栈中元素不变。操作结果：输出栈顶元素，但栈中元素不变。4.判栈空：判栈空：SEmpty（s）初始条件：栈初始条件：栈s已存在。已存在。操作结果：若栈空则返回为
4、操作结果：若栈空则返回为0，否则返回为，否则返回为1。5.判栈满：判栈满：SFull（s）初始条件：栈初始条件：栈s已存在。已存在。操作结果：若栈满则返回为操作结果：若栈满则返回为0，否则返回为，否则返回为1。6.显示栈元素：显示栈元素：ShowStack(s)初始条件：栈初始条件：栈s已存在已存在，且非空。，且非空。操作结果：显示栈中所有元素。操作结果：显示栈中所有元素。3-2栈的存储和实现321顺序栈顺序栈1顺序栈的实现顺序栈的实现（1）用一维数组实现顺序栈用一维数组实现顺序栈设设栈栈中中的的数数据据元元素素的的类类型型是是字字符符型型，用用一一个个足足够够长长度度的的一一维维数数组组s来
5、来存存放放元元素素，数数组组的的最最大大容容量量为为MAXLEN，栈栈顶顶指指针针为为top，则则顺顺序序栈栈可可以以用用C（或或C+）语语言言描描述述如如下：下：#defineMAXLEN10/分配最大的栈空间分配最大的栈空间charsMAXLEN；/数据类型为字符型数据类型为字符型inttop；/定义栈顶指针定义栈顶指针（2）用结构体数组实现顺序栈用结构体数组实现顺序栈顺序栈的结构体描述：顺序栈的结构体描述：#defineMAXLEN10/分配最大的栈空间分配最大的栈空间typedefstruct/定义结构体定义结构体datatypedataMAXLEN;/datatype可根据用需要定义
6、类型可根据用需要定义类型inttop；/定义栈顶指针定义栈顶指针SeqStack；再定义一个指向顺序栈的指针：再定义一个指向顺序栈的指针：SeqStack*S；/定义定义S为结构体类型的指针变量为结构体类型的指针变量（3）栈操作的示意图如图）栈操作的示意图如图33所示。所示。AFEDCBAFEDCBAJIHGFEDCBAtop=-1top=0top=5top=3top=9(a)(b)(c)(d)(e)当当top=1时，表示栈空，如图时，表示栈空，如图33（a）；）；当当top=0时时，表表示示栈栈中中有有一一个个元元素素，如如图图33（b）表表示示栈栈中已输入一个元素中已输入一个元素A；入入栈
7、栈时时，栈栈顶顶指指针针上上移移，指指针针top加加1，如如图图33（c）是是6个元素入栈后的状况；个元素入栈后的状况；出出栈栈时时，栈栈顶顶指指针针下下移移，指指针针top减减1，如如图图33（d）是是在在F、E相相继继出出栈栈后后的的情情况况。此此时时栈栈中中还还有有A、B、C、D4个个元元素素，top=3，指指针针已已经经指指向向了了新新的的栈栈顶顶。但但是是出出栈栈的的元元素素F、E仍仍然然在在原原先先的的存存储储单单元元，只只是是不不在在栈栈中中了了，因因为为栈栈是是只只能能在栈顶进行操作的线性表。在栈顶进行操作的线性表。当当 top=9时时，即即 top=MAXLEN1，表表 示示
8、 栈栈 满满，如如 图图 33（e）。）。2顺序栈运算的基本算法顺序栈运算的基本算法（1）置空栈）置空栈首先建立栈空间，然后初始化栈顶指针。首先建立栈空间，然后初始化栈顶指针。SeqStack*Snull（）（）SeqStack*s；s=new(SeqStack)；/在在C语言中用语言中用s=malloc（sizeof（SeqStack）；stop=1；/置栈空置栈空returns；（2）进栈进栈进栈运算是在栈顶位置插入一个新元素进栈运算是在栈顶位置插入一个新元素x，其算法步骤为：，其算法步骤为：(a)判判栈栈是是否否为为满满，若若栈栈满满，作作溢溢出出处处理理，并并返返回回0；(b)若栈未满
9、，栈顶指针若栈未满，栈顶指针top加加1；(c)将新元素将新元素x送入栈顶，并返回送入栈顶，并返回1。intPush(SeqStack*s，datatypex)if（stop=MAXLEN1）return0；/栈栈满满不不能能入入栈栈，且且返返回回0elsestop+；sdatastop=x；/栈不满，则压入元素栈不满，则压入元素xreturn1；/进栈成功，返回进栈成功，返回1（3）出栈）出栈出出栈栈运运算算是是指指取取出出栈栈顶顶元元素素，赋赋给给某某一一个个指指定定变变量量x，其算法步骤为：其算法步骤为：(a)判栈是否为空，若栈空，作下溢处理，并返回判栈是否为空，若栈空，作下溢处理，并返
10、回0；(b)若栈非空，将栈顶元素赋给变量若栈非空，将栈顶元素赋给变量x；(c)指针指针top减减1，并返回，并返回1。intPop（SeqStack*s，datatype*x）if(SEmpty(s)return0；/若栈空不能出栈若栈空不能出栈，且返回，且返回0else*x=sdatastop；/栈不空则栈顶元素存入栈不空则栈顶元素存入*xstop；return1；/出栈成功，返回出栈成功，返回1（4）读栈顶元素）读栈顶元素datatypeReadTop（SeqStack*s）if(SEmpty(s)return0；/若栈空，则返回若栈空，则返回0elsereturn(sdatastop)；
11、/否则，读栈顶元素，但指针未移动否则，读栈顶元素，但指针未移动（5）判栈空）判栈空intSEmpty（SeqStack*s）if（stop=1）return1；/若栈空，则返回若栈空，则返回1elsereturn0；/否则返回否则返回0（6）判栈满）判栈满intSFull（SeqStack*s）if（stop=MAXLEN1）return1；/若栈满，则返回若栈满，则返回1elsereturn0；/否则返回否则返回0322链栈链栈1链栈的实现链栈的实现用用链链式式存存储储结结构构实实现现的的栈栈称称为为链链栈栈。因因为为链链栈栈的的结结点点结结构构与与单单链链表表的的结结构构相相同同，通通常常
12、就就用用单单链链表表来来实实现现，在在此此用用LinkStack表示，即有：表示，即有：typedefstructstacknode/栈的存储结构栈的存储结构datatypedata;/定义数据类型定义数据类型 structstacknode*next;/定义一个结构体的链指针定义一个结构体的链指针stacknode;，*Linkstack；Linkstacktop；/top/top为栈顶指针为栈顶指针由由于于栈栈中中的的操操作作只只能能在在栈栈顶顶进进行行的的，所所以以用用链链表表的头部做栈顶是最合适的。链栈结构如图的头部做栈顶是最合适的。链栈结构如图34所示。所示。图图34链栈示意图链栈示
13、意图top43212链栈基本操作：链栈基本操作：（1）入栈）入栈voidPush(linkstack*s,intx)stacknode*p=newstacknode;/申请一个新结点申请一个新结点pdata=x;/数据入栈数据入栈pnext=stop;/修改栈顶指针修改栈顶指针stop=p;（2）出栈出栈intPop(linkstack*s)intx;/定义一个变量定义一个变量x x，用以存放出栈的元素，用以存放出栈的元素stacknode*p=stop;/栈顶指针指向栈顶指针指向p p x=pdata;/栈顶元素送栈顶元素送x xstop=pnext;/修改栈顶指针修改栈顶指针deletep
14、;/回收结点回收结点p preturnx;/返回栈顶元素返回栈顶元素（3）显示显示voidShowStack(linkstack*s)stacknode*p=stop;if(p=NULL)/若栈空，作若栈空，作“栈空栈空”显示显示printf(栈为空栈为空);elseprintf(栈元素为：栈元素为：);while(p!=NULL)/栈非空，则显示栈中所有元素栈非空，则显示栈中所有元素printf(%6d,pdata);/输出一个元素输出一个元素p=pnext;/修改栈顶指针修改栈顶指针printf(n);33.栈的应用举例331数制转换数制转换数数值值进进位位制制的的换换算算是是计计算算机机
15、实实现现计计算算和和处处理理的的基基本本问问题题。比比如如将将十十进进制制数数N转转换换为为j进进制制的的数数，其其解解决决的的方方法法很很多多，其其中中一一个个常常用用的的算算法法是是除除j取取余余法法。将将十十进进制制数数每每次次除除以以j，所所得得的的余余数数依依次次入入栈栈，然然后后按按“后进先出后进先出”的次序出栈便得到转换的结果。的次序出栈便得到转换的结果。其算法原理是：其算法原理是：N=（N/j）*j+N%j其中：其中：/为整除，为整除，%为求余为求余【例【例31】将十进制数】将十进制数138转换为二进制数转换为二进制数NN/2（整除）（整除）N%2（求余）（求余）1386906
16、93413417进进0出出178栈栈1栈栈84次次0次次42序序0序序210101（138）10=（10001010）21算法思想如下：算法思想如下：（1）若若N0，则则将将N%j取取得得的的余余数数压压入入栈栈s中中，执行（，执行（2）；）；若若N=0，将栈，将栈s的内容依次出栈，算法结束。的内容依次出栈，算法结束。（2）用用N/j代替代替N（3）当当N0，则重复步骤（，则重复步骤（1）、（）、（2）。）。2.算法的实现：算法的实现：voidConversion(intn)/将十进制数将十进制数n转换为二进制数转换为二进制数linkstacks;intx;s.top=NULL;dox=n%2
17、;/除除2取余取余n=n/2;stacknode *p=new stacknode;/申申请请一一个个新新结结点点pnext=s.top;/修改栈顶指针修改栈顶指针s.top=p;s.topdata=x;/入栈入栈while(n);printf(转换后的二进制数值为：转换后的二进制数值为：);while(s.top)/余数出栈处理余数出栈处理printf(%d,s.topdata);/输出栈顶的余数输出栈顶的余数stacknode*p=s.top;/修改栈顶指针修改栈顶指针s.top=s.topnext;deletep;/回收一个结点，回收一个结点，C语言中用语言中用freep332表达式求值
18、表达式求值表达式是由运算对象、运算符、括号等组成的有意义的式子。表达式是由运算对象、运算符、括号等组成的有意义的式子。1 1中缀表达式（中缀表达式（Infix NotationInfix Notation）一一般般我我们们所所用用表表达达式式是是将将运运算算符符号号放放在在两两运运算算对对象象的的中中间间，比比如如：a+ba+b，c/dc/d等等等等，我我们们把把这这样样的的式式子子称称为为中中缀缀表表达达式。式。2 2后缀表达式（后缀表达式（Postfix NotationPostfix Notation）后缀表达式规定把运算符放在两个运算对象（操作数）后缀表达式规定把运算符放在两个运算对象
19、（操作数）的后面。在后缀表达式中，不存在运算符的优先级问题，也的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次不存在任何括号，计算的顺序完全按照运算符出现的先后次次序进行。次序进行。3 3中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式其其转转换换方方法法采采用用运运算算符符优优先先算算法法。转转换换过过程程需需要要两两个个栈栈：一个运算符号栈和一个后缀表达式输出符号栈。一个运算符号栈和一个后缀表达式输出符号栈。（1）读入操作数，直接送输出符号栈。）读入操作数，直接送输出符号栈。（2）读入运算符，压入运算符号栈。）读入运算符，压入运算
20、符号栈。(a)(a)若后进的运算符优先级高于先进的，则继续进栈；若后进的运算符优先级高于先进的，则继续进栈；(b)(b)若若后后进进的的运运算算符符优优先先级级不不高高于于先先进进的的，则则将将运运算算符符号号栈栈内高于或等于后进运算符级别的运算符依次弹出后，自己进栈。内高于或等于后进运算符级别的运算符依次弹出后，自己进栈。（3）括号处理：）括号处理：(a)(a)遇到开括号遇到开括号“（”，进运算符号栈；，进运算符号栈；(b)(b)遇遇到到闭闭括括号号“）”，则则把把最最靠靠近近的的开开括括号号“（”，以以及及其其后后进进栈栈的的运运算算符符依依次次弹弹出出到到输输出出符符号号栈栈（括括号号均
21、均不不压压入入输输出出符符号栈）。号栈）。（4）遇遇到到结结束束符符“#”，则则把把运运算算符符号号栈栈内内的的所所有有运运算算符符号号依依次弹出，并压入输出符号栈。次弹出，并压入输出符号栈。（5）若若输输入入为为+、单单目目运运算算符符，改改为为0 0与与运运算算对对象象在在前前，运运算符在后。算符在后。例如：例如：AA，转换为：，转换为：0A0A。【例【例3-23-2】A/B C+D*EA*CA/B C+D*EA*C输入符号输入符号运算符栈运算符栈输出结果输出结果操作说明操作说明AA输出输出A/A/进栈进栈B/A,B输出输出B/,A,B优先级高于优先级高于/，继续进栈，继续进栈C/,A,B
22、,C输出输出C+A,B,C,/，/依次弹出依次弹出D+A,B,C,/,D输出输出D*+,*A,B,C,/,D*优先级高于优先级高于+，继续进栈，继续进栈E+,*A,B,C,/,D,E输出输出EA,B,C,/,D,E,*,+*，+依次弹出，依次弹出，进栈进栈AA,B,C,/,D,E,*,+,A输出输出A*,*A,B,C,/,D,E,*,+,A*优先级高于优先级高于，继续进，继续进栈栈C,*A,B,C,/,D,E,*,+,A,C输出输出C#A,B,C,/,D,E,*,+,A,C,*,遇到结束符遇到结束符#，依次弹出，依次弹出*，【例【例3-33-3】3+4/3+4/（2525（6+156+15）*
23、8*8 输入符号输入符号运算符栈运算符栈输出结果输出结果操作说明操作说明33输出输出3+3+进栈进栈4+3,4输出输出4/+,/3,4/继续进栈继续进栈(+,/,(3,4（进栈（进栈25+,/,(3,4,25输出输出25+,/,(,3,4,25进栈进栈(+,/,(,(3,4,25（再进栈（再进栈6+,/,(,(3,4,25,6输出输出6+,/,(,(,+3,4,25,6+进栈进栈15+,/,(,(,+3,4,25,6,15输出输出15)+,/,(,3,4,25,6,15,+遇），依次弹出第遇），依次弹出第2个（后的符号个（后的符号)+,/3,4,25,6,15,+,遇），依次弹出第遇），依次弹
24、出第1个（后的符号个（后的符号*+,*3,4,25,6,15,+,/弹出弹出/，但，但*高于高于+，继续进栈，继续进栈8+.*3,4,25,6,15,+,/,8输出输出8#3,4,25,6,15,+,/,8,*,+遇到结束符遇到结束符#，依次弹出，依次弹出*，+得得到到后后缀缀表表达达式式为为：3 3 4 4 25 25 6 6 15 15 +/8 8 *+4 4后缀表达式求值后缀表达式求值后后缀缀表表达达式式求求值值的的运运算算要要用用到到一一个个数数栈栈stackstack和和一一个个存存放放后后缀缀表表达达式式的的字字符符型型数数组组expexp。其其实实现现过过程程就就是是从从头头至至
25、尾尾扫扫描数组中的后缀表达式：描数组中的后缀表达式：（1 1）当遇到运算对象时，就把它插入到数栈）当遇到运算对象时，就把它插入到数栈stackstack中；中；（2 2）当当遇遇到到运运算算符符时时，就就执执行行两两次次出出栈栈的的操操作作，对对出出栈栈的的数数进进行行该该运运算算符符指指定定的的运运算算，并并把把计计算算的的结结果果压压入入到到数数栈栈stackstack。把它插入到数栈。把它插入到数栈stackstack中；中；（3 3）重重复复（1 1）、（2 2），直直至至扫扫描描到到表表达达式式的的终终止止符符“#”，在数栈的栈顶得到表达式的值。，在数栈的栈顶得到表达式的值。以例【例
26、以例【例3-33-3】的结果看后缀表达式的计算过程：】的结果看后缀表达式的计算过程：3 4 25 6 15+-/8*+3 4 25 6 15+-/8*+第第1 1次次计计算算结结果果为为：2121 第第2 2次计算结果为：次计算结果为：4 4 第第3 3次计算结果为：次计算结果为：1 1 第第4 4次计算结果为：次计算结果为：8 8 第第5 5次计算结果为：次计算结果为：11113-3-3 3-3-3 子程序调用（子程序调用（Subroutine CallSubroutine Call）在在计计算算机机程程序序设设计计中中，子子程程序序的的调调用用及及返返回回地地址址就就是是利利用堆栈来完成的
27、。用堆栈来完成的。在在C(C(或或C+)C+)语语言言的的主主函函数数对对无无参参子子函函数数的的嵌嵌套套调调用用过过程程中中，在在调调用用子子程程序序前前，先先将将返返回回地地址址保保存存到到堆堆栈栈中中，然然后后才才转转去去执执行行子子程程序序。当当子子函函数数执执行行到到returnreturn语语句句（或或函函数数结结束束）时时，便便从从栈栈中中弹弹出出返返回回地地址址，从从该该地地址址处处继继续续执执行程序。行程序。例例如如：主主函函数数调调用用子子函函数数a()a()时时，则则在在调调用用之之前前先先将将a a函函数数返返回回地地址址压压入入栈栈中中；在在子子函函数数a()a()中
28、中调调用用子子函函数数b()b()时时，又又将将b b函函数数返返回回地地址址压压人人栈栈中中；同同样样，在在子子函函数数b()b()中中调调用用子子函函数数c()c()时时，又又将将c c函函数数返返回回地地址址压压人人栈栈中中。其其调调用用返返回回地址进栈示意图如图地址进栈示意图如图3-53-5所示。所示。图图35无参函数嵌套调用返回地址进栈示意图无参函数嵌套调用返回地址进栈示意图当当执执行行完完子子函函数数c c()()以以后后，就就从从栈栈顶顶弹弹出出c c()()函函数数返返回回地地址址，回回到到子子函函数数b b()()；子子函函数数b b()()执执行行完完毕毕返返回回时时，又又
29、从从栈栈顶顶弹弹出出b b函函数数返返回回地地址址，回回到到子子函函数数a a()()；子子函函数数a a()()返返回回时时，再再在在栈栈顶顶弹弹出出a a函函数数返返回回地地址址，回回到到主主函函数数，继继续续执执行行主主函函数数程程序序。无参函数嵌调用返回示意图如图无参函数嵌调用返回示意图如图3-63-6所示。所示。c函数返回地址函数返回地址b函数返回地址函数返回地址a函数返回地址函数返回地址返回地址栈：返回地址栈：图图36无参函数嵌套调用返回示意图无参函数嵌套调用返回示意图3-3-4 3-3-4 递归调用递归调用1 1递归递归一一个个直直接接调调用用自自己己，或或者者通通过过一一系系列
30、列调调用用语语句句间间接接地地调调用用自自己己的的函函数数称称为为递递归归函函数数。在在程程序序设设计计中中，有有许许多多实实际际问问题题是是递递归归定定义义的的，使使用用递递归归的的方方法法编编写写程程序序将将使使许许多多复复杂杂的的问问题题大大大大简简化化。所所以以，递递归归是是程程序序设设计计中中的的一一个个强强有有力的工具。力的工具。2 2典型例子典型例子（1 1）2 2阶斐波那契（阶斐波那契（FibonacciFibonacci）数列）数列0n=01n=1Fib(n1)+Fib(n2)其它情况Fib(n)=（2）阶乘函数）阶乘函数n!的定义为：的定义为：Fac(n)=1n=0/递归终
31、止条件递归终止条件n*Fac(n1)n0/递归步骤递归步骤根据定义不难写出相应的递归函数：根据定义不难写出相应的递归函数：intfac(intn)if(n=0)return1；elsereturn(n*fac(n1)；3-3-5 3-3-5 中断处理和现场保护中断处理和现场保护1.1.中断处理（中断处理（Interrupt ProcessingInterrupt Processing）在在C+语语言言中中，系系统统调调用用是是通通过过中中断断来来进进行行，中中断断调调用示意图如图用示意图如图38所示。所示。图图38中断调用示意图如中断调用示意图如如果把中断处理想象成函数调用，则中断处理程序果把
32、中断处理想象成函数调用，则中断处理程序可以看成被调用的函数。可以看成被调用的函数。2.2.现场保护和恢复现场保护和恢复执执行行中中断断时时，微微处处理理机机有有时时必必须须对对状状态态寄寄存存器器，累累加加器器，以以及及相相关关的的寄寄存存器器对对进进行行现现场场保保护护（压压栈栈）；中中断断处处理理完完毕毕，则则必必须须按按后后进进先先出出的的原原则则恢恢复复现现场场（出出栈栈）。下下面面，我我们们以以汇编语言来说明现场保护和恢复的原理汇编语言来说明现场保护和恢复的原理：；接受中断处理；接受中断处理 PUSH AX PUSH AX ；保护现场；保护现场 PUSH BX PUSH BX PUS
33、H CX PUSH CX PUSH BP PUSH BP PUSHF PUSHF ；F F状态寄存器进栈状态寄存器进栈 ；中断处理；中断处理 POPF POPF ；恢复现场，后进栈的先出栈；恢复现场，后进栈的先出栈 POP BP POP BP POP CX POP CX POP BX POP BX POP AX POP AX（1）栈栈是是一一种种运运算算受受限限制制的的线线性性表表，它它只只允允许许在在栈栈顶顶进行插入和删除等操作。进行插入和删除等操作。（2）栈栈的的逻逻辑辑结结构构和和线线性性表表相相同同，数数据据元元素素之之间间存存在在一对一的关系，其主要特点是一对一的关系，其主要特点是“
34、后进先出后进先出”。（3）栈栈的的存存储储结结构构有有顺顺序序栈栈和和链链栈栈之之分分，要要求求掌掌握握栈栈的的C C语言描述方法。语言描述方法。（4）重重点点掌掌握握在在顺顺序序栈栈和和链链栈栈上上实实现现：进进栈栈、出出栈栈、读栈顶元素、判栈空和判栈满等基本操作。读栈顶元素、判栈空和判栈满等基本操作。（5）熟熟悉悉栈栈在在计计算算机机的的软软件件设设计计中中的的各各种种应应用用，能能灵灵活应用栈的基本原理解决一些综合性的应用问题。活应用栈的基本原理解决一些综合性的应用问题。小 结 实验3 3 栈子系统 1实验目的实验目的（1）掌握栈的特点及其描述方法。掌握栈的特点及其描述方法。（2）用链式
35、存储结构实现一个栈。用链式存储结构实现一个栈。（3）掌握建栈的各种等基本操作。掌握建栈的各种等基本操作。（4）掌握栈的几个典型应用的算法。）掌握栈的几个典型应用的算法。2.实验内容实验内容（1）设计一个字符型的链栈；）设计一个字符型的链栈；（2）编写进栈、出栈、显示栈中全部元素的程序；）编写进栈、出栈、显示栈中全部元素的程序；（3）编写一个把十进制整数转换成二进制数的应用程序；）编写一个把十进制整数转换成二进制数的应用程序；（4）编编写写一一个个把把中中缀缀表表达达式式转转换换成成后后缀缀表表达达式式（逆逆波波兰兰式）的应用程序；式）的应用程序；（5）设计一个选择式菜单，以菜单方式选择上述操作
36、。）设计一个选择式菜单，以菜单方式选择上述操作。栈栈 子子 系系 统统*1-*1-进进 栈栈 *2-*2-出出 栈栈 *3-*3-显显 示示 *4-*4-数制转换数制转换 *5-*5-逆波兰式逆波兰式 *0-*0-返返 回回 *请选择菜单号：请选择菜单号：*教材教材p64第第3行行voidStack()，在作为子系统上机时上，在作为子系统上机时上机时机时改为：改为：voidmain()习题3 参考习题解答参考习题解答返回实用数据结构基础实用数据结构基础第第4 4章章 队列队列第4 4章 队列 知识点队列的定义和特点队列的定义和特点队列的存储实现及运算实现队列的存储实现及运算实现队列的应用举例队
37、列的应用举例难难点点循环队列的特点及判断溢出的条件循环队列的特点及判断溢出的条件利用队列的特点设计相关的应用问题利用队列的特点设计相关的应用问题要求熟练掌握以下内容：熟练掌握以下内容：队列的特点和基本运算队列的特点和基本运算循环队列的特征和基本运算循环队列的特征和基本运算了解以下内容：了解以下内容：队列运算的时间复杂性分析队列运算的时间复杂性分析队列的实际应用队列的实际应用第 4 4 章 目录41队列的定义和基本运算队列的定义和基本运算42队列的存储及运算的实现队列的存储及运算的实现43队列的应用举例队列的应用举例小小结结实验实验4队列子系统队列子系统习题习题441 队列的定义和基本运算411
38、队列（队列（Queue）的定义）的定义1队列的定义队列的定义设设有有n个个元元素素的的队队列列Q=（a1，a2，a3，an），则则称称a1为为队队首首元元素素，an为为队队尾尾元元素素。队队列列中中的的元元素素按按，a1，a2，a3，an1，an的的次次序序进进队队，按按a1，a2，a3，an1，an次次序序出出队，即队列的操作是按照队，即队列的操作是按照“先进先出先进先出”的原则进行的。的原则进行的。2.队列的特性队列的特性（1）队列的主要特性是）队列的主要特性是“先进先出先进先出”。（2）队列是限制在两端进行插入和删除操作的线性表。）队列是限制在两端进行插入和删除操作的线性表。能能够够插插
39、入入元元素素的的一一端端称称为为队队尾尾（Rear），允允许许删删除除元元素素的一端称为的一端称为队首（队首（Front）。）。图图41队列示意图队列示意图a1a2a3a4a5 an入队入队出队出队4.队列的实例队列的实例（1）如车站排队买票或自动取款机排队取款。）如车站排队买票或自动取款机排队取款。（2）在在计计算算机机处处理理文文件件打打印印时时，为为了了解解决决高高速速的的CPU与与低低速速的的打打印印机机之之间间的的矛矛盾盾，对对于于多多个个请请求求打打印印文文件件，操操作作系系统统把把它它们们当当作作可可以以被被延延迟迟的的任任务务，提提出出打打印印任任务务的的先先后后顺顺序序，就就
40、是是它它们们实实际际打打印印的的先先后后顺顺序序。即即按按照照“先先进进先先出出”的的原原则则形成打印队列。形成打印队列。412队列的基本运算队列的基本运算（1）入队操作：）入队操作：InQueue（q，x）初始条件：队初始条件：队q存在且未满。存在且未满。操作结果：输入一个元素操作结果：输入一个元素x到队尾，长度加到队尾，长度加1。（2）出队操作：）出队操作：OutQueue（q，x）初始条件初始条件:队队q存在，且非空。存在，且非空。操作结果：删除队首元素，长度减操作结果：删除队首元素，长度减1。（3）读队头元素：）读队头元素：ReadFront（q，x）初始条件：初始条件：队队q存在且非
41、空。存在且非空。操作结果：操作结果：读队头元素，队列不变。读队头元素，队列不变。（4）显示队列中元素）显示队列中元素ShowQueue(q）初始条件：队列初始条件：队列q存在，且非空。存在，且非空。操作结果：显示队列中所有元素。操作结果：显示队列中所有元素。（5）判队空操作：）判队空操作：QEmpty（q）初始条件：队初始条件：队q存在。存在。操作结果：若队空则返回为操作结果：若队空则返回为0，否则返回为，否则返回为1。（6）判队满操作：）判队满操作：QFull（q）初始条件：队初始条件：队q存在。存在。操作结果：若队满则返回为操作结果：若队满则返回为0，否则返回为，否则返回为1。（7）求队列
42、长度）求队列长度Qlen（q）初始条件：队列初始条件：队列q存在。存在。操作结果：返回队列的长度。操作结果：返回队列的长度。42 队列的存储实现及运算实现 421顺序队列顺序队列1顺序队列顺序队列顺顺序序队队列列是是用用内内存存中中一一组组连连续续的的存存储储单单元元顺顺序序存存放放队队列列中中各各元元素素。所所以以可可以以用用一一维维数数组组QMAXLEN作作为为队队列列的的顺顺序序存存储储空空间间，其其中中MAXLEN为为队队列列的的容容量量，队队列列元元素素从从Q0单单元元开开始始存存放放，直直到到QMAXLEN1单单元元。因因为为队队头头和和队队尾尾都都是是活活动动的的，因因此此，除除
43、了了队队列列的的数数据据以以外外，一一般般还还设有队首（设有队首（front）和队尾（）和队尾（rear）两个指针。）两个指针。顺序队可以用顺序队可以用C+语言定义：语言定义：#defineMAXLEN10/队列的最大容量队列的最大容量typedefstructdatatypeQMAXLEN；/datatype可根据用户需要定义可根据用户需要定义intfront=1,rear=1；/定义队头、队尾指针，并置队列为空定义队头、队尾指针，并置队列为空Queue；Queue*p；/定义一个指向队的指针变量定义一个指向队的指针变量p=newQueue；/申请一个顺序队的存储空间申请一个顺序队的存储空间
44、/在在C中用中用p=malloc（sizeof（Queue）设：设：队头指针：队头指针：pfront指向队头元素前面一个位置指向队头元素前面一个位置队尾指针：队尾指针：prear指向队尾元素。指向队尾元素。（1）判队空）判队空当当pfront=prear=1时表示队空。如图时表示队空。如图42（a）（2）入队）入队在无溢出的情况下，队尾指针加在无溢出的情况下，队尾指针加1，新元素即可入队：，新元素即可入队：prear+；/先将队尾指针加先将队尾指针加1pQprear=x；/入队入队（3）出队。）出队。在队列非空的情况下允许出队，出队时队头指针加在队列非空的情况下允许出队，出队时队头指针加1，队
45、头元素即可输出：队头元素即可输出：pfront+；x=pQpfront；/队头元素送队头元素送x（4）队列的长度：）队列的长度：m=(prear)(pfront)；（5）判队满：）判队满：m=MAXLEN；判队空：判队空：m=0。EDCBAHGFJIHGFRear=-1front=-1(a)rear=4rear=7rear=9front=-1front=4front=4(b)(c)(d)图图42 从从示示意意图图中中可可以以看看到到，随随着着入入队队、出出队队操操作作的的进进行行，整整个个队队列列会会整整体体向向后后移移动动，这这样样就就出出现现了了图图4-24-2（d d）中中的的现现象象：
46、队队尾尾指指针针虽虽然然已已经经移移到到了了最最后后，而而队队列列却却未未真真满满的的“假假溢溢出出”现象，使得队列的空间没有得到有效的利用。现象，使得队列的空间没有得到有效的利用。2 2循环队列循环队列为为了了解解决决上上述述队队列列的的“假假溢溢出出”现现象象，要要做做移移动动操操作作，当当移移动动数数据据较较多多时时将将会会影影响响队队列列的的操操作作速速度度。一一个个更更有有效效的的方方法法是是将将队队列列的的数数据据区区Q0 Q0.MAXLEN-1.MAXLEN-1看看成成是是首首尾尾相相连连的的环环，即即将将表表示示队队首首的的元元素素Q0Q0与与表表示示队队尾尾的的元元素素QMA
47、XLENQMAXLEN11连连接接起起来来，形形成成一一个个环环形形表表，这这就就成成了了循循环环队队列列，如如图图4-4-3 3所示。所示。图图43循环队列示意图循环队列示意图MAXLEN-1图图4-44-4是假设长度为是假设长度为1010的循环队列操作示意图。的循环队列操作示意图。因因为为是是头头尾尾相相接接的的循循环环结结构构，所所以以将将入入队队时时的的队队尾尾指指针针加加1 1操作修改为：操作修改为：p-rear=(p-rear+1)%MAXLEN p-rear=(p-rear+1)%MAXLEN；将出队时的队头指针加将出队时的队头指针加1 1操作修改为：操作修改为：p-front=
48、(p-front+1)%MAXLEN p-front=(p-front+1)%MAXLEN；在在图图4-44-4（a a）中中，此此时时front=4front=4，rear=8rear=8，队队列列中中具具有有:a a6 6、a a7 7 、a a8 8、a a9 9四个元素；四个元素；随随着着a a1010aa1515相相继继入入队队，此此时时 front=4front=4，rear=4rear=4，队队列列已满，如（已满，如（b b）所示，可见在队满情况下有：）所示，可见在队满情况下有：front=front=rear=rear。若若在在（a a）的的情情况况下下，a a6 6aa9 9
49、相相继继出出队队，此此时时队队空空，front=8front=8，rear=8rear=8，如如（c c）所所示示，也也有有：front=front=rear=rear，也也就就是是说说，仅仅根根据据等等式式front=front=rear=rear 无无法法有有效效判判别别是是“队队满满”还是还是“队空队空”。两种常用的方法：两种常用的方法：（1 1）规定：当）规定：当front=front=rear=rear，表示循环队列为空；，表示循环队列为空；当当front=front=（rear+1rear+1）%MAXLEN%MAXLEN，表示循环队列为满。，表示循环队列为满。（2 2）在在定定义
50、义结结构构体体时时，附附设设一一个个存存储储循循环环队队列列中中元元素素个个数的变量数的变量n n，当，当n=n=0=0时表示队空；时表示队空；当当n=n=MAXLEN=MAXLEN时为队满。时为队满。循环队列的结构体类型定义如下：循环队列的结构体类型定义如下：typedef structtypedef structdatatype datatype datadataMAXLENMAXLEN；/定义数据的类型及数据的存储区定义数据的类型及数据的存储区 int frontint front，rearrear；/定义队头、队尾指针定义队头、队尾指针 int nint n；/用以记录循环队列中元素的