数据结构C语言版(栈和队列).ppt

第3章栈和队列 本章主要介绍以下内容 栈的概念 存储结构及其基本操作队列的概念 存储结构及其基本操作栈与队列的应用举例 退出 3 1栈3 2队列 3 1栈 3 1 1栈的定义栈是一种特殊的线性表 其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行 如下所示 进行插入和删除的一端是浮动端 通常被称为栈顶 并用一个 栈顶指针 指示 而另一端是固定端 通常被称为栈底 我们经常将栈用下图3 1的形式描述 a1 a2 a3 an插入和删除端 图3 1 结论 后进先出 LastInFirstOut 简称为LIFO线性表 举例1 家里吃饭的碗 通常在洗干净后一个一个地落在一起存放 在使用时 若一个一个地拿 一定最先拿走最上面的那只碗 而最后拿出最下面的那只碗 举例2 在建筑工地上 使用的砖块从底往上一层一层地码放 在使用时 将从最上面一层一层地拿取 下面我们先给出栈结构的基本操作 1 初始化栈InitStack S 2 入栈Push S item 3 出栈Pop S item 4 获取栈顶元素内容GetTop S item 5 判断栈是否为空StackEmpty S 3 1 2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素 并用起始端作为栈底 类型定义如下所示 defineMAX STACK10 栈的最大数据元素数目typedefstructstack StackEntryitem MAX STACK 存放栈中数据元素的存储单元inttop 栈顶指针 STACK 基本操作算法 1 初始化栈SvoidInItStack STACK S s top 1 2 入栈voidPush STACK S StackEntryitem if S top MAX STACK 1 exit Stackisfull elseS item S top item 图3 2 3 出栈voidPop STACK S StackEntry item if StackEmpty S exit Stackisempty else item S item S top 4 获取栈顶元素内容voidGetTop STACKS StackEntry item if StackEmpty S exit Stackisempty else item S item S top 5 判断栈S是否为空intStackEmpty STACKS if S top 1 returnTRUE elseFALSE 结论 由于栈的插入和删除操作具有它的特殊性 所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题 但栈容量难以扩充的弱点仍就没有摆脱 3 1 3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目 就应该考虑使用链式存储结构 人们将用链式存储结构表示的栈称作 链栈 链栈通常用一个无头结点的单链表表示 如图3 3所示 由于栈的插入删除操作只能在一端进行 而对于单链表来说 在首端插入删除结点要比尾端相对地容易一些 所以 我们将单链表的首端作为栈顶端 即将单链表的头指针作为栈顶指针 图3 3 栈的链式存储结构在C语言中可用下列类型定义实现 typestructnode 链栈的结点结构StackEntryitem 栈的数据元素类型structnode next 指向后继结点的指针 NODE typedefstructstack NODE top STACK 下面我们将给出链栈各项基本操作的算法 1 初始化栈SvoidInitStack STACK S S top NULL 2 入栈voidPush STACK S StackEntryitem p NODE malloc sizeof NODE if p exit OVERFLOW else p item item p next S top S top p 3 出栈voidPop STACK S StackEntry item if StackEmpty S exit Stackisempty else item S top item p S top S top p next free p 4 获取栈顶元素内容voidGetTop STACKS StackEntry item if StackEmpty S exit Stackisempty else item S top item 5 判断栈S是否空intStackEmpty STACKS if S top NULL returnTRUE elseFALSE 3 1 4栈的应用举例 举例1 将从键盘输入的字符序列逆置输出比如 从键盘上输入 tsetasisihT 算法将输出 Thisisatest下面我们给出解决这个问题的完整算法 typedefcharStackEntry voidReverseRead STACKS 定义一个栈结构Scharch InitStack 初始化栈 while ch getchar n 从键盘输入字符 直到输入换行符为止Push 举例2 十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值 即用该十进制数值除以2 并保留其余数 重复此操作 直到该十进制数值为0为止 最后将所有的余数反向输出就是所对应的二进制数值 比如 692 10 1010110100 2 其展转相除的过程如图3 4所示 图3 4 下面给出解决这个问题的完整算法 voidDecimal Binary STACKS 定义栈结构SInitStack 输入十进制正整数 while data Push 举例3 检验表达式中的括号匹配情况假设在一个算术表达式中 可以包含三种括号 圆括号 和 方括号 和 和花括号 和 并且这三种括号可以按任意的次序嵌套使用 比如 现在需要设计一个算法 用来检验在输入的算术表达式中所使用括号的合法性 算术表达式中各种括号的使用规则为 出现左括号 必有相应的右括号与之匹配 并且每对括号之间可以嵌套 但不能出现交叉情况 我们可以利用一个栈结构保存每个出现的左括号 当遇到右括号时 从栈中弹出左括号 检验匹配情况 在检验过程中 若遇到以下几种情况之一 就可以得出括号不匹配的结论 1 当遇到某一个右括号时 栈已空 说明到目前为止 右括号多于左括号 2 从栈中弹出的左括号与当前检验的右括号类型不同 说明出现了括号交叉情况 3 算术表达式输入完毕 但栈中还有没有匹配的左括号 说明左括号多于右括号 下面是解决这个问题的完整算法 typedefcharStackEntry intCheck STACKS 定义栈结构Scharch InitStack if ch returnFALSE break case ch if StackEmpty S retrunFALSE else Pop 3 2队列 3 2 1队列的定义队列特殊性在于限定插入在线性表的一端进行 删除在线性表的另外一端进行 如图3 5所示 图3 5 插入端和删除端都是浮动的 通常我们将插入端称为队尾 用一个 队尾指针 指示 而删除端被称为队头 用一个 队头指针 指示 结论 先进先出 FirstInFirstOut 简称为FIFO线性表 举例1 到医院看病 首先需要到挂号处挂号 然后 按号码顺序救诊 举例2 乘坐公共汽车 应该在车站排队 车来后 按顺序上车 举例3 在Windows这类多任务的操作系统环境中 每个应用程序响应一系列的 消息 像用户点击鼠标 拖动窗口这些操作都会导致向应用程序发送消息 为此 系统将为每个应用程序创建一个队列 用来存放发送给该应用程序的所有消息 应用程序的处理过程就是不断地从队列中读取消息 并依次给予响应 下面我们给出队列结构的基本操作 1 初始化队列InitQueue Q 2 入队EnQueue Q item 3 出队DeQueue Q item 4 获取队头元素内容GetFront Q item 5 判断队列是否为空QueueEmpty Q 3 2 2队列的顺序存储队列的顺序存储结构如下图3 6所示 图3 6 问题1 当队空时 队头和队尾指针都为 1 队列将处于下图3 7所示的状态 图3 7 此时若进行入队操作 就需要让队头和队尾指针都增1 再将新数据元素放入该位置 也就是说 这样设置队头 队尾指针位置 在进行入队操作时 空队与非空队状态所需要执行的操作不完全一样 解决方法 在算法中 需要对这两种情况加以区分 这势必增加了算法的复杂性 因此 人们设想了一种解决方法 即让队头指针指向队列真正队头元素的前一个位置 如下图3 8所示 图3 8 问题2 由于顺序存储结构的存储空间属于静态分配 所以 在添加数据元素时 可能会出现没有剩余单元的情况 对于队列来说 这一点又有它的特殊性 下面我们讨论一下下图3 10所示的队列 图3 10 假溢出 现象 解决方法 将存储队列元素的一维数组首尾相接 形成一个环状 如图3 11所示 我们将这种形式表示的队列称之为循环队列 图3 11 假设为队列开辟的数组单元数目为MAX QUEUE 在C语言中 它的下标在0 MAX QUEUE 1之间 若增加队头或队尾指针 可以利用取模运算 一个整数数值整除以另一个整数数值的余数 实现 如下所示 front front 1 MAX QUEUE rear rear 1 MAX QUEUE 当front或rear为MAXQUEUE 1时 上述两个公式计算的结果就为0 这样 就使得指针自动由后面转到前面 形成循环的效果 队空和队满的标志问题 队列变为空 队头和队尾指针相等 a b 图3 12 队列变为满 队头和队尾指针也相等 rear front a6 a5 a4 a3 a1 a2 7 6 5 4 3 2 1 0 a6 a5 a4 a3 a1 a2 a8 a7 7 6 5 4 3 2 1 0 rear front a b 图3 13 解决方法 一是为队列另设一个标志 用来区分队列是 空 还是 满 二是当数组只剩下一个单元时就认为队满 此时 队尾指针只差一步追上队头指针 即 rear 1 MAX QUEUE front 类型定义 defineMAX QUEUE10 队列的最大数据元素数目typedefstructqueue 假设当数组只剩下一个单元时认为队满QueueEntryitem MAX QUEUE 存放队列中数据元素的存储单元intfront rear 队头指针 队尾指针 QUEUE 各项基本操作算法 1 初始化队列QvoidInitQueue QUEUE Q Q front 1 Q rear 1 2 入队voidEnQueue QUEUE Q QueueEntryitem if Q rear 1 MAX QUEUE Q front exit OVERFLOW else Q rear Q rear 1 MAX QUEUE Q item Q rear item 3 出队voidDeQueue QUEUE Q QueueEntry item if QueueEmpty Q exit Queueisempty else Q front Q front 1 MAX QUEUE item Q item Q front 4 获取队头元素内容voidGetFront QUEUEQ QueueEntry item if QueueEmpty Q exit Queueisempty else item Q item Q front 1 MAX QUEUE 5 判断队列Q是否为空intQueueEmpty QueueQ if Q front Q rear returnTRUE elsereturnFALSE 3 2 3队列的链式存储在用链式存储结构表示队列时 需要设置队头指针和队尾指针 以便指示队头结点和队尾结点 图3 14 入队需要执行下面三条语句 s next NULL rear next s rear s 下面是在C语言中 实现队列链式存储结构的类型定义 typestructnode 链式队列的结点结构QueueEntryEntry 队列的数据元素类型structnode next 指向后继结点的指针 NODE typedefstructqueue 链式队列NODE front 队头指针NODE rear 队尾指针 QUEUE 下面我们给出链式队列的基本操作算法 1 初始化队列QvoidInitQueue QUEUE Q Q front NODE malloc sizeof NODE if Q front NULL exit ERROR Q rear Q front 2 入队voidEnQueue QUEUE Q QueueEntryitem s NODE malloc sizeof NODE if s exit ERROR s item item s next NULL Q rear next s Q rear s 3 出队voidDeQueue QUEUE Q QueueEntry item if QueueEmpty Q exit ERROR else item Q front next item s Q front next Q front next s next free s 4 获取队头元素内容voidGetFront QUEUEQ QueueEntry item if QueueEmpty Q exit ERROR else item Q front next item 5 判断队列Q是否为空intQueueEmpty QUEUEQ if Q front Q rear returnTRUE elsereturnFALSE 4 队列的应用举例 举例1 汽车加油站 随着城市里汽车数量的急速增长 汽车加油站也渐渐多了起来 通常汽车加油站的结构基本上是 入口和出口为单行道 加油车道可能有若干条 每辆车加油都要经过三段路程 第一段是在入口处排队等候进入加油车道 第二段是在加油车道排队等候加油 第三段是进入出口处排队等候离开 实际上 这三段都是队列结构 若用算法模拟这个过程 就需要设置加油车道数加2个队列 举例2 模拟打印机缓冲区 在主机将数据输出到打印机时 会出现主机速度与打印机的打印速度不匹配的问题 这时主机就要停下来等待打印机 显然 这样会降低主机的使用效率 为此人们设想了一种办法 为打印机设置一个打印数据缓冲区 当主机需要打印数据时 先将数据依次写入这个缓冲区 写满后主机转去做其他的事情 而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印 这样做即保证了打印数据的正确性 又提高了主机的使用效率 由此可见 打印机缓冲区实际上就是一个队列结构 举例3 CPU分时系统在一个带有多个终端的计算机系统中 同时有多个用户需要使用CPU运行各自的应用程序 它们分别通过各自的终端向操作系统提出使用CPU的请求 操作系统通常按照每个请求在时间上的先后顺序 将它们排成一个队列 每次把CPU分配给当前队首的请求用户 即将该用户的应用程序投入运行 当该程序运行完毕或用完规定的时间片后 操作系统再将CPU分配给新的队首请求用户 这样即可以满足每个用户的请求 又可以使CPU正常工作