第4章-栈和队列.ppt

数据结构与算法作者 胡明王红梅出版社 电子工业出版社邮箱 wanghm 第4章栈和队列 本章的基本内容是 两种特殊的线性表 栈和队列 从数据结构角度看 栈和队列是操作受限的线性表 他们的逻辑结构相同 从抽象数据类型角度看 栈和队列是两种重要的抽象数据类型 4 1引言 例4 1括号匹配问题 C语言对于算术表达式中括号的配对原则是 右括号 与其前面最近的尚未配对的左括号 相配对 例如 算术表达式 x 5 6 38 5中的括号没有正确配对 多了一个 如何判断给定表达式中所含括号是否正确配对呢 如果顺序扫描表达式 当扫描到右括号 时 需要查找已经扫描过的最后一个尚未配对的左括号 对于 具有最后扫描到最先配对的特点 如何保存已经扫描过的尚未配对的左括号 并对其实施配对操作呢 4 1引言 例4 2函数的嵌套调用 函数的嵌套调用是在函数的执行过程中再调用其他函数 当函数C执行结束时 应该返回到什么位置呢 工作栈是如何保证调用次序的正确性呢 4 1引言 例4 3银行排队问题 在需要顺序操作但人群众多的场合 排队是现代文明的一种表现 例如 储户到银行办理个人储蓄业务 需要领取一张排队单 在排队单上打印了储户的顺序号以及前面的人数 储户只需坐在椅子上等待 储蓄窗口会顺次叫号 如何实现这种先来先服务的功能呢 4 1引言 例4 4打印缓冲区 在计算机系统中 经常会遇到两个设备在处理数据时速度不匹配的问题 例如 将计算机内存中的数据传送到打印机上打印输出 如何实现这种先来先服务的功能呢 栈的逻辑结构 a1 a2 an 栈 限定仅在表的一端进行插入和删除操作的线性表 允许插入和删除的一端称为栈顶 另一端称为栈底 空栈 不含任何数据元素的栈 4 2栈 a1 a2 a3 入栈 出栈 插入 入栈 进栈 压栈删除 出栈 弹栈 栈的逻辑结构 4 2栈 栈的操作特性 后进先出 a1 a2 a3 入栈 出栈 插入 入栈 进栈 压栈删除 出栈 弹栈 栈的逻辑结构 4 2栈 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 a b c 情况1 栈的逻辑结构 4 2栈 a b c 出栈序列 c 出栈序列 c b 出栈序列 c b a 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 情况1 4 2栈 a b 出栈序列 b 情况2 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 4 2栈 a 出栈序列 b 出栈序列 b c 出栈序列 b c a c 注意 栈只是对表插入和删除操作的位置进行了限制 并没有限定插入和删除操作进行的时间 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 情况2 4 2栈 栈的抽象数据类型定义 ADTStackData栈中元素具有相同类型及后进先出特性 相邻元素具有前驱和后继关系OperationInitStack前置条件 栈不存在输入 无功能 栈的初始化输出 无后置条件 构造一个空栈 4 2栈 DestroyStack前置条件 栈已存在输入 无功能 销毁栈输出 无后置条件 释放栈所占用的存储空间Push前置条件 栈已存在输入 元素值x功能 在栈顶插入一个元素x输出 如果插入不成功 抛出异常后置条件 如果插入成功 栈顶增加了一个元素 栈的抽象数据类型定义 4 2栈 Pop前置条件 栈已存在输入 无功能 删除栈顶元素输出 如果删除成功 返回被删元素值 否则 抛出异常后置条件 如果删除成功 栈减少了一个元素GetTop前置条件 栈已存在输入 无功能 读取当前的栈顶元素输出 若栈不空 返回当前的栈顶元素值后置条件 栈不变 栈的抽象数据类型定义 4 2栈 Empty前置条件 栈已存在输入 无功能 判断栈是否为空输出 如果栈为空 返回1 否则 返回0后置条件 栈不变endADT 栈的抽象数据类型定义 4 2栈 栈的顺序存储结构及实现 顺序栈 栈的顺序存储结构 如何改造数组实现栈的顺序存储 a1 确定用数组的哪一端表示栈底 附设指针top指示栈顶元素在数组中的位置 4 2栈 出栈 top减1 进栈 top加1 栈空 top 1 a1 a2 a3 栈满 top MAX SIZE 1 栈的顺序存储结构及实现 4 2栈 顺序栈的存储结构定义 constintStackSize 10 假定栈元素最多10个typedefintDataType DataType为栈元素的数据类型typedefstruct DataTypedata StackSize 存放栈元素的数组inttop 栈顶指针 为栈顶元素在数组中的下标 SeqStack 4 2栈 顺序栈的实现 入栈 voidPush SeqStack 操作接口 voidPush SeqStack 时间复杂度 data top x 4 2栈 顺序栈的实现 出栈 DataTypePop SeqStack 操作接口 DataTypePop SeqStack 时间复杂度 4 2栈 两栈共享空间 解决方案2 顺序栈单向延伸 使用一个数组来存储两个栈 在一个程序中需要同时使用具有相同数据类型的两个栈 如何顺序存储这两个栈 会出现什么问题 如何解决 4 2栈 两栈共享空间 使用一个数组来存储两个栈 让一个栈的栈底为该数组的始端 另一个栈的栈底为该数组的末端 两个栈从各自的端点向中间延伸 两栈共享空间 4 2栈 栈1的底固定在下标为0的一端 栈2的底固定在下标为StackSize 1的一端 top1和top2分别为栈1和栈2的栈顶指针 Stack Size为整个数组空间的大小 图中用S表示 a1a2 ai 012 S 1 两栈共享空间 bj b2b1 4 2栈 top1 1 什么时候栈1为空 a1a2 ai 012 S 1 两栈共享空间 bj b2b1 4 2栈 top1 1 什么时候栈1为空 a1a2 ai 012 S 1 两栈共享空间 bj b2b1 什么时候栈2为空 top2 Stack Size 4 2栈 top1 1 什么时候栈1为空 a1a2 ai 012 S 1 两栈共享空间 bj b2b1 什么时候栈2为空 top2 Stack Size 什么时候栈满 top2 top1 1 4 2栈 两栈共享空间的存储结构定义 constintStackSize 10 假设两个栈最多10个元素typedefintDataType DataType为两个栈的数据类型typedefstruct DataTypedata StackSize 存放两个栈的数组inttop1 top2 各自栈顶元素在数组中的下标 BothStack 4 2栈 1 如果栈满 则抛出上溢异常 2 判断是插在栈1还是栈2 2 1若在栈1插入 则2 1 1top1加1 2 1 2在top1处填入x 2 2若在栈2插入 则2 2 1top2减1 2 2 2在top2处填入x 两栈共享空间的实现 插入 操作接口 voidPush inti DataTypex 4 2栈 1 若是在栈1删除 则1 1若栈1为空栈 抛出下溢异常 1 2删除并返回栈1的栈顶元素 2 若是在栈2删除 则2 1若栈2为空栈 抛出下溢异常 2 2删除并返回栈2的栈顶元素 两栈共享空间的实现 删除 操作接口 DataTypePop inti 4 2栈 栈的链接存储结构及实现 链栈 栈的链接存储结构 链栈需要加头结点吗 如何改造链表实现栈的链接存储 将哪一端作为栈顶 将链头作为栈顶 方便操作 链栈不需要附设头结点 4 2栈 栈的链接存储结构及实现 栈顶 栈底 链栈 栈的链接存储结构 两种示意图在内存中对应同一种状态 启示 栈顶 栈底 4 2栈 voidPush Node top DataTypex s Node malloc sizeof Node s data x s next top top s an an 1 a1 链栈的实现 插入 操作接口 voidPush DataTypex 为什么没有判断栈满 4 2栈 DataTypePop Node top if top NULL printf 下溢 exit 1 x top data p top top top next free p returnx 链栈的实现 插入 操作接口 DataTypePop an an 1 a1 top 可以吗 4 2栈 顺序栈和链栈的比较 时间性能 相同 都是常数时间O 1 空间性能 顺序栈 有元素个数的限制和空间浪费的问题 链栈 没有栈满的问题 只有当内存没有可用空间时才会出现栈满 但是每个元素都需要一个指针域 从而产生了结构性开销 总之 当栈的使用过程中元素个数变化较大时 用链栈是适宜的 反之 应该采用顺序栈 4 2栈 队列的逻辑结构 队列 只允许在一端进行插入操作 而另一端进行删除操作的线性表 允许插入 也称入队 进队 的一端称为队尾 允许删除 也称出队 的一端称为队头 空队列 不含任何数据元素的队列 a1 a2 an 4 3队列 队列的操作特性 先进先出 a1 a2 a3 入队 队尾 队头 出队 队头 队列的逻辑结构 4 3队列 队列的抽象数据类型定义 ADTQueueData队列中元素具有相同类型及先进先出特性 相邻元素具有前驱和后继关系OperationInitQueue前置条件 队列不存在输入 无功能 初始化队列输出 无后置条件 创建一个空队列 4 3队列 DestroyQueue前置条件 队列已存在输入 无功能 销毁队列输出 无后置条件 释放队列所占用的存储空间EnQueue前置条件 队列已存在输入 元素值x功能 在队尾插入一个元素输出 如果插入不成功 抛出异常后置条件 如果插入成功 队尾增加了一个元素 队列的抽象数据类型定义 4 3队列 DeQueue前置条件 队列已存在输入 无功能 删除队头元素输出 如果删除成功 返回被删元素值后置条件 如果删除成功 队头减少了一个元素GetQueue前置条件 队列已存在输入 无功能 读取队头元素输出 若队列不空 返回队头元素后置条件 队列不变 队列的抽象数据类型定义 4 3队列 Empty前置条件 队列已存在输入 无功能 判断队列是否为空输出 如果队列为空 返回1 否则 返回0后置条件 队列不变endADT 队列的抽象数据类型定义 4 3队列 队列的顺序存储结构及实现 顺序队列 队列的顺序存储结构 如何改造数组实现队列的顺序存储 例 a1a2a3a4依次入队 a1 a2 a3 a4 入队操作时间性能为O 1 4 3队列 如何改造数组实现队列的顺序存储 例 a1a2依次出队 队列的顺序存储结构及实现 a1 a2 a3 a4 4 3队列 如何改造数组实现队列的顺序存储 例 a1a2依次出队 队列的顺序存储结构及实现 a2 a3 a4 4 3队列 如何改造数组实现队列的顺序存储 例 a1a2依次出队 队列的顺序存储结构及实现 a3 a4 出队操作时间性能为O n 4 3队列 队列的顺序存储结构及实现 如何改进出队的时间性能 4 3队列 队列的顺序存储结构及实现 例 a1a2a3a4依次入队 a1 a2 a3 a4 入队操作时间性能仍为O 1 约定 队头指针front指向队头元素的前一个位置 队尾指针rear指向队尾元素 4 3队列 例 a1a2依次出队 队列的顺序存储结构及实现 a1 a2 a3 a4 出队操作时间性能提高为O 1 4 3队列 例 a1a2依次出队 队列的顺序存储结构及实现 a3 a4 队列的移动有什么特点 4 3队列 例 a1a2依次出队 队列的顺序存储结构及实现 a3 a4 4 3队列 假溢出 当元素被插入到数组中下标最大的位置上之后 队列的空间就用尽了 尽管此时数组的低端还有空闲空间 这种现象叫做假溢出 队列的顺序存储结构及实现 继续入队会出现什么情况 a3 a4 a5 4 3队列 循环队列 将存储队列的数组头尾相接 队列的顺序存储结构及实现 如何解决假溢出 01234 入队 出队 a3 a4 a5 a6 4 3队列 不存在物理的循环结构 用软件方法实现 求模 4 1 mod5 0 队列的顺序存储结构及实现 如何实现循环队列 01234 入队 出队 a3 a4 a6 4 3队列 如何判断循环队列队空 队空的临界状态 队列的顺序存储结构及实现 01234 入队 出队 a3 4 3队列 如何判断循环队列队空 执行出队操作 队空 front rear 队列的顺序存储结构及实现 01234 入队 出队 a3 4 3队列 如何判断循环队列队满 队满的临界状态 队列的顺序存储结构及实现 01234 入队 出队 a3 a4 a5 a6 4 3队列 如何判断循环队列队满 执行入队操作 队满 front rear 队列的顺序存储结构及实现 01234 入队 出队 a3 a4 a5 a6 a7 4 3队列 方法一 附设一个存储队列中元素个数的变量num 当num 0时队空 当num QueueSize时为队满 方法二 修改队满条件 浪费一个元素空间 队满时数组中只有一个空闲单元 方法三 设置标志flag 当front rear且flag 0时为队空 当front rear且flag 1时为队满 如何确定不同的队空 队满的判定条件 为什么要将队空和队满的判定条件分开 队列的顺序存储结构及实现 4 3队列 队满的条件 rear 1 modQueueSize front 队列的顺序存储结构及实现 4 3队列 循环队列的存储结构定义 constintQueueSize 10 定义数组的最大长度typedefintDataType DataType为队列元素的数据类型typedefstruct DataTypedata QueueSize 存放队列元素的数组intfront rear 队头和队尾指针 CirQueue 4 3队列 voidEnQueue CirQueue 循环队列的实现 入队 a3 a4 a5 4 3队列 01234 入队 a4 a5 a6 出队 DataTypeDeQueue CirQueue 循环队列的实现 出队 a3 4 3队列 DataTypeGetFront CirQueue 循环队列的实现 读队头元素 01234 入队 a4 a5 a6 出队 a3 4 3队列 队列的链接存储结构及实现 链队列 队列的链接存储结构 队头指针即为链表的头指针 如何改造单链表实现队列的链接存储 4 3队列 队列的链接存储结构及实现 非空链队列 front rear 空链队列 front rear 4 3队列 链队列的存储结构定义 typedefintDataType DataType为队列元素的数据类型typedefstructNode 定义链队列的结点结构 DataTypedata Node next Node typedefstruct 定义链队列 Node front rear LinkQueue 4 3队列 操作接口 LinkQueue 算法描述 voidInitQueue LinkQueue 链队列的实现 队列的初始化 4 3队列 链队列的实现 入队 操作接口 voidEnQueue DataTypex front front 算法描述 s next NULL rear next s rear s 如何没有头结点会怎样 4 3队列 链队列的实现 入队 操作接口 voidEnQueue DataTypex front 算法描述 s next NULL rear next s rear s 如何没有头结点会怎样 4 3队列 链队列的实现 入队 操作接口 voidEnQueue DataTypex front rear NULL 算法描述 s next NULL rear s front s 如何没有头结点会怎样 算法描述 s next NULL rear next s rear s 4 3队列 链队列的实现 入队 voidEnQueue LinkQueue 4 3队列 链队列的实现 出队 front rear 算法描述 p