第4章 栈和队列

《第4章 栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法作者：胡明王红梅出版社：电子工业出版社邮箱：wanghm@mail.ccut.edu.cn第4章栈和队列本章的基本内容是：两种特殊的线性表——栈和队列从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。4.1引言例4-1括号匹配问题C语言对于算术表达式中括号的配对原则是：右括号“)”与其前面最近的尚未配对的左括号“(”相配对。例如，算术表达式((x+5)*6-38))%5中的括号没有正确配对，多了一个“)”。如何判断给定表达式中所含括号是否正确配对呢？如果顺序扫描表达式，当扫描到右括

2、号“)”时，需要查找已经扫描过的最后一个尚未配对的左括号“(”，对于“(”具有最后扫描到最先配对的特点。如何保存已经扫描过的尚未配对的左括号“(”，并对其实施配对操作呢？4.1引言例4-2函数的嵌套调用函数的嵌套调用是在函数的执行过程中再调用其他函数。当函数C执行结束时，应该返回到什么位置呢？工作栈是如何保证调用次序的正确性呢？4.1引言例4-3银行排队问题在需要顺序操作但人群众多的场合，排队是现代文明的一种表现。例如，储户到银行办理个人储蓄业务，需要领取一张排队单，在排队单上打印了储户的顺序号以及前面的人数，储户只需坐在椅子上等待，储蓄窗口会顺次叫号。如何实现这种

3、先来先服务的功能呢？4.1引言例4-4打印缓冲区在计算机系统中，经常会遇到两个设备在处理数据时速度不匹配的问题。例如，将计算机内存中的数据传送到打印机上打印输出。如何实现这种先来先服务的功能呢？栈的逻辑结构（a1,a2,……,an）栈：限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。空栈：不含任何数据元素的栈。栈顶栈底4.2栈a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的逻辑结构4.2栈栈的操作特性：后进先出a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈的逻辑结构4.

4、2栈例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构4.2栈栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况1：4.2栈栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构4.2栈栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插

5、入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况2：4.2栈栈的抽象数据类型定义ADTStackData栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系OperationInitStack前置条件：栈不存在输入：无功能：栈的初始化输出：无后置条件：构造一个空栈4.2栈DestroyStack前置条件：栈已存在输入：无功能：销毁栈输出：无后置条件：释放栈所占用的存储空间Push前置条件：栈已存在输入：元素值x功能：在栈顶插入一个

6、元素x输出：如果插入不成功，抛出异常后置条件：如果插入成功，栈顶增加了一个元素栈的抽象数据类型定义4.2栈Pop前置条件：栈已存在输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值，否则，抛出异常后置条件：如果删除成功，栈减少了一个元素GetTop前置条件：栈已存在输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值后置条件：栈不变栈的抽象数据类型定义4.2栈Empty前置条件：栈已存在输入：无功能：判断栈是否为空输出：如果栈为空，返回1，否则，返回0后置条件：栈不变endADT栈的抽象数据类型定义4.2栈栈的顺序存储结构及实现顺序栈——栈

7、的顺序存储结构如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。top4.2栈出栈：top减1进栈：top加1栈空：top=-1012345678a1topa2topa3top栈满：top=MAX_SIZE-1栈的顺序存储结构及实现4.2栈顺序栈的存储结构定义：constintStackSize=10;//假定栈元素最多10个typedefintDataType;//DataType为栈元素的数据类型typedefstruct{DataTypedata[StackSize];//存放栈元素的