数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列
44页1、栈和队列,栈的定义和基本运算/ 顺序栈/ 链栈/ 队列的定义和基本运算/顺序队列/链式队列/实训,唐懿芳,数据结构与算法,目录,CONTENTS,栈的定义和基本运算,1、栈的定义 2、栈的基本运算,01,数据结构与算法,第一节:栈的定义和基本运算,数据结构与运算,生活中的栈与队列 栈和队列是特殊的线性表 栈与队列的特征 LIFO(Last In First Out) FIFO(First In First Out),栈的定义,堆栈简称为栈,是限定只能在表的一端进行插入和删除操作的线性表。 在表中,允许插入和删除的一端称作“栈顶”,另一端称作“栈底”。通常将元素插入栈顶的操称作为“入栈”(进栈或压栈),称删除栈顶元素的操作为“出栈”,栈底,栈顶,入栈,出栈,图3.1 堆栈,a1,a2,an,第一节:栈的定义和基本运算,栈的基本运算,堆栈的基本运算如下。 (1) StackInit()初始化堆栈。 (2) StackEmpty(s) 判定栈s是否为空。 (3) StackLength(s) 求堆栈s的长度。 (4) GetTop(s) 获取栈顶元素的值。 (5) Push(s, e) 将元
2、素e进栈。 (6) Pop(s),出栈(删除栈顶元素)。,数据结构与运算,第一节:栈的定义和基本运算,栈的存储结构,两种存储结构: (1) 顺序栈采用顺序结构存储 (2) 链栈采用链式结构存储,数据结构与运算,顺序栈,1、顺序栈的存储结构 3、顺序栈的案例 2、顺序栈的基本运算,02,数据结构与算法,第二节:顺序栈,顺序栈的存储结构,MaxSize-1,#define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top; /*栈顶位置*/ SeqStack;,栈底,栈顶,a0,a1,an-1,备 用 空 间,栈满和栈空的条件是什么?,栈满:top=Maxsize-1 栈空:top=-1,数据结构与运算,SeqStack StackInit() SeqStack s; s.top=-1; return(s); ,顺序栈的基本运算,初始化堆栈 StackInit(),int StackEmpty(SeqStack s) return(s.top=-1); ,判定栈s是否为空StackEmpty(s),int
3、 StackLength(SeqStack s) return(s.top+1); ,求堆栈s的长度StackLength(s),ElementType GetTop(SeqStack s) if (StackEmpty(s) /*空栈*/ return(nil); return(s.elems.top); ,获取栈顶元素的值GetTop(s),void Push(SeqStack *s, ElementType e) if (s-top= MaxSize-1) /*栈满*/ printf(“Full”); else s-top+; s-elems-top=e ; ,进栈Push(s, e),ElementType Pop(SeqStack *s) if (s-top= -1) /*栈空*/ return(nil); /* 返回空值*/ else e=s-elems-top; s-top-; return (e); ,出栈Pop(s),第二节:顺序栈,数据结构与运算,顺序栈案例1,【例1】假设有两个栈共享一个一维数组空间0,MaxSize1,其中一个栈用数组的第0单元(元素)作为栈底,
4、另一栈用数组的第MaxSize1号单元(元素)作为栈底(即两个堆栈从两端向中间延伸),其对应的类型描述如下: #define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top1, top2; /*栈顶位置*/ ShareStack;,第二节:顺序栈,数据结构与运算,顺序栈案例2,则栈1的栈顶表示为:s-top1,栈2的栈顶表示为:s-top2; 栈1的进栈操作使得栈顶1右(后)移,即s-top1+,栈2进 栈操作使得栈顶2左(前)移,即s-top1-; 栈满时两个栈顶相邻,即s-top1+1s-top2。,图3.2 共享堆栈,栈1,栈顶2,a1,an,b1,bm,栈2,栈底1,栈底2,0,MaxSize-1,栈顶1,第二节:顺序栈,数据结构与运算,顺序栈案例3 进栈,void Push(ShareStack *s, ElementType e, int i) /*将元素e压入栈i(i=1,2)*/ if (s-top1+1=s-top2) /*栈满*/ printf(“Full”); else if
《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列》由会员E****分享,可在线阅读,更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页