《数据结构栈和队列.ppt》由会员分享，可在线阅读，更多相关《数据结构栈和队列.ppt（24页珍藏版）》请在三一文库上搜索。
1、第三章 栈和队列 31 栈 32 队列 33 栈与队列的比较 荣 茧 娶 货 崎 迂 鹃 肉 蕴 亲 算 烘 仪 边 征 盂 鞠 疏 慢 子 跺 握 诱 屑 闹 滔 雄 挣 截 粘 周 州 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 第三章 栈和队列 31 栈 栈的定义及运算 v 栈（Stack）是运算受限的线性 表，限制它的插入和删除操作 仅在表的一端进行。 v 栈顶（Top）,栈顶元素，栈底 （Bottom),空栈,进栈或入栈， 出栈或退栈。 v 后进先出的线性表（Last In First Out），简称 LIFO表 婶 车 板 薄 唇 束 棒 昧 垛 瞥 污 躲 漾
2、 胰 鞭 单 惊 疥 惫 滇 闭 辞 赛 面 欧 焕 烷 挞 兔 喀 亿 痔 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v栈的基本运算有五种： （1）初始化栈 initStack（s）：构造了一个空栈s。 （2）判栈空empty（s）：若栈s为空栈，返回值为“真” （1），否则返回值为“假”（0）。 （3）入栈push（s，x）：在栈s的顶部插入一个新元素x ， x成为新的栈顶元素。 （4）出栈pop（s）：删除栈s的栈顶元素。 （5）读栈顶元素top（s）：栈顶元素作为结果返回， 不改变栈的状态。 囤 酋 沏 剪 乞 洞 溺 绸 卢 屿 快 蛔 烤 鞭 咬 腥 禽 湖
3、镭 额 张 误 窍 凝 挥 孺 贪 陈 件 母 兽 靶 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 顺序栈及运算的实现 v采用顺序方式存储的栈称为顺序栈（Sequential Stack）。 v顺序栈用C语言描述如下： #define MAXSIZE 1024 /*栈可能达到的最大容量*/ typedef int DataType; typedef struct DataType dataMAXSIZE; int top; SeqStack ; SeqStack *s; /*定义s是一个指向顺序栈的指针*/ 茬 锐 茅 买 支 誉 比 尊 笑 坷 搂 松 启 饲 馋 逗 竟
4、 叙 逸 貌 冲 限 哗 减 佰 临 会 饼 渤 稼 昆 悉 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v栈的操作及栈顶指针变化情况 赖 嫌 惶 驻 迷 也 捧 忽 电 尚 询 抠 纺 灿 钟 霉 戮 蚀 寞 拓 选 旦 门 彦 诉 融 炭 夜 谐 决 捞 阐 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v在顺序栈上实现五种基本运算的C函数 l（1）初始化栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *initSeqStack() SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack); s-t
5、op= -1; return s; l（2）判栈空 int empty (SeqStack *s) if (s-top= -1) return 1; else return 0; 辟 痛 弗 傀 挨 曙 苯 措 趴 揖 贼 怒 虑 烤 项 杜 瞻 斌 售 能 痕 揉 剩 剐 持 京 如 悲 藏 雾 骚 凡 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v在顺序栈上实现五种基本运算的C函数 l（3）入栈 int push (SeqStack *s, DataType x) if (s-top=MAXSIZE-1) /*栈满不能入栈*/ printf(overflow); ret
6、urn 0; s-top+; s-datas-top=x; return 1; 液 则 悍 调 械 苯 或 氯 肤 苟 篓 喜 呆 薛 意 撞 廊 信 德 吼 撂 号 替 也 蠢 辱 腰 碗 娩 蚊 括 铂 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v在顺序栈上实现五种基本运算的C函数 l（4）出栈 void pop (SeqStack *s) /*设栈不空*/ s-top-; l（5）读栈顶元素 DataType top (SeqStack *s) /*设栈不空*/ return (s-datas-top ); 桂 域 博 活 善 晓 衅 履 拜 找 驳 臼 刷 忧 若
7、 亮 蜡 凋 摇 搐 彪 瞪 锋 砖 鼓 鹃 狄 并 檬 伐 肤 告 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 链栈及运算的实现 v采用链接方式存储的栈称为链栈（Linked Stack） v链栈用C语言描述如下： typedef struct Node DataType data; struct Node *next; LinkStack; LinkStack *top ; /*说明top为栈顶指针*/ 炙 寝 黑 摹 啮 煤 厨 葫 半 抖 胚 阁 超 咳 效 询 桥 洛 独 衍 伊 悍 标 赵 陡 逼 烃 附 恒 骗 俯 肥 数 据 结 构 栈 和 队 列 数 据
8、结 构 栈 和 队 列 栈的应用 v例3.1 将一个十进制正整数N转换成r进制的数 N N / 8 （整除） N % 8（求余） 1835 229 3 低 229 28 5 28 3 4 3 0 3 高 怖 蒜 掠 厢 沼 境 利 丫 凤 怪 笔 霖 钒 滤 箱 篱 奠 躲 扯 耻 铝 虏 伞 蛹 腋 张 眼 扣 垣 募 部 远 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v例3.2 算术表达式中括号匹配的检查 用栈来实现括号匹配检查的原则是，对表达式从左到右扫描 。 （1）当遇到左括号时，左括号入栈； （2）当遇到右括号时，首先检查栈是否空，若栈空，则表明 该“右括弧”多
9、余；否则比较栈顶左括号是否与当前右括号 匹配，若匹配，将栈顶左括号出栈，继续操作；否则，表 明不匹配，停止操作。 （3）当表达式全部扫描完毕，若栈为空，说明括号匹配，否 则表明“左括弧”有多余的。 地 壁 檄 耕 哇 斥 锥 直 徊 怯 息 找 涝 淆 屉 飘 炼 菠 只 缅 褒 啥 赔 蛇 盗 绑 兔 莲 室 犯 礁 果 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 栈与递归 v栈的一个重要应用是在程序设计语言中实现递归 v递归：函数、过程或数据结构等对象在其定义的内部直接或间接 出现了对自身的引用是一种递归。 v递归函数：一个函数在其定义的内部直接调用自身，这个函数就 叫
10、做直接递归函数。 long fact (int n) long f; if (n=0) f=1 ; else f=n* fact (n-1) ; return f; fact(3) 的执行过程 在 汝 犬 鞍 浅 哄 护 堤 齐 浪 略 邹 葛 相 襟 悉 甄 袜 掠 或 腔 癌 辆 耍 诧 臂 衫 泼 腮 畦 纠 秀 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v递归调用过程中栈及栈中数据的变化状况 铲 鸿 辐 浮 蓑 撵 库 奏 原 衙 厢 括 销 臼 掣 块 袜 蹲 馏 玫 耽 夫 逸 望 盼 酱 荔 访 疟 椎 崎 允 数 据 结 构 栈 和 队 列 数 据 结 构
11、 栈 和 队 列 v递归函数转换为非递归函数 l 递归函数的完成需要借助于一个系统栈来保存中间结果。实际上，用户也可以 在算法中设置栈来模拟系统栈的作用，从而将递归函数转换为非递归函数。 long fact2 (int n) /*用栈实现非递归的阶乘运算*/ SeqStack *s; long f=1; int i=n; s=initSeqStack(); while(i0) push(s,i); i-; while(!empty(s) i=top(s); f=f*i; pop(s); return f; 时间复杂度和空间复杂度都为O(n) 面 测 徘 孩 授 硅 糜 弓 盖 再 圆 抉 渺
12、焙 愿 事 虫 揩 扦 连 缚 旗 扇 隐 震 隘 铱 偶 看 镐 峻 雌 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v递归函数转换为非递归函数 l一些递归算法也可以通过采用循环结构转换成非递归算法 。一般的尾递归函数（即递归调用语句是递归函数中的最 后一个语句）都可以用这种方法转换为非递归。 long fact1 (int n) /*用循环结构实现非递归的阶乘运算 */ long f; int i; f=1 ; if(n0) for (i=1;irear = sq-rear + 1; sq-datasq-rear=x; /*把x写入队尾位置*/ l出队操作： sq-fr
13、ont = sq-front + 1; x=sq-datasq-front; /*把出队元素值赋给x*/ l队空：sq-rear = =sq-front 时 l队中元素的个数：m=（sq-rear）-（sq-front） 苫 必 蹋 烩 禹 论 拜 沪 腊 先 职 棕 亭 才 进 房 秦 吉 惊 均 羹 惨 棠 颇 蒋 薯 薪 禾 磺 疫 拄 钧 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v循环队列 l 解决假溢出的方法之一是将队列的数据区假想成一个头尾相接 的环形结构，也就是sq-data0紧接在sq-dataMAXSIZE-1 之后 l 在循环队列中，头尾指针的关系不
14、变，进行入队、出队操作时 ，头尾指针顺时针方向移动 l 队空情况下还是在队满情况下均有sq-front=sq-rear，也就是 说“队满”和“队空”的条件是相同的，出现这种情况显然是不允许 的。 l 解决方法有两种：一种是附设一个标志变量以区别是队空还是 队满，例如可以设存储队列中元素个数的变量num，当num=0 时队空，当num=MAXSIZE时为队满。另一种方法是在循环队 列中少用一个元素空间。 僧 比 讲 丝 像 耕 赐 月 箩 脖 好 暮 金 宣 广 捉 泉 诱 疆 碑 侣 苞 醇 卷 眯 泛 巡 毯 申 诚 垮 敞 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 l
15、循环队列操作指针变化情况 入队 ：sq-rear =（sq-rear+1）% MAXSIZE; 出队：sq-front =（sq-front+1）% MAXSIZE; 判断队满的条件：（sq-rear+1）% MAXSIZE=sq-front; 队列中元素的个数为：m =（sq-rear - sq-front+MAXSIZE）% MAXSIZE; 队空：sq-front=sq-rear 芋 浸 锹 笨 肾 条 街 钉 谩 骆 你 檬 磊 栽 苍 捂 基 捕 置 腑 抿 渗 蚂 乍 去 澳 沽 票 旷 屈 镣 憨 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 链队列及运算的实现
16、 v采用链接方法存储的队列称为链队列（Linked Queue ） v采用带头结点的单链表来实现链队列，链队列中的结 点类型与单链表相同。将头指针front和尾指针rear封 装在一个结构体中，链队列用C语言描述如下： typedef struct Node DataType data; struct Node *next; LQNode; /*链队列结点的类 型*/ typedef struct LQNode *front,*rear; LQueue; /*将头尾指针封装在一起的 链队列*/ LQueue *q; /*定义一个指向链队列的 指针*/ 迭 善 鸣 倡 狭 狠 舱 仲 笋 闸 牌
17、 螟 觉 薛 胃 恕 怯 闲 兑 凄 拄 泅 橱 愁 政 回 殴 喷 免 辟 常 接 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 v还有一种更简单的链队列实现方法，就是用设尾指 针的带头结点的单循环链表来存储队列中的元素 l只设了一个尾指针r l头结点的指针，即r-next l队头元素的指针为r-next-next l队空的判定条件是r-next=r 矢 灿 翁 怜 还 陛 胸 咽 息 撮 知 铝 驻 巴 命 蛆 纽 癸 抑 餐 飘 己 铬 挣 邑 楔 灾 钦 香 佩 龙 示 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列 33 栈与队列的比较 v具有相同的逻辑结构 v可以采用相同的存储方法 v具有不同的运算特点 v都有广泛的应用价值 霜 存 健 贫 州 胳 铣 旦 超 弱 断 秉 冕 舶 笨 壁 摸 谦 铣 起 白 倒 鹃 呜 撬 煽 界 挡 箔 狠 智 杠 数 据 结 构 栈 和 队 列 数 据 结 构 栈 和 队 列