人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列
第3章花和队列 本章主要介绍以下内容: 栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用举例 请单鼠标左键换页! 退出
第3章 栈和队列 本章主要介绍以下内容: ⚫ 栈的概念、存储结构及其基本操作 ⚫ 队列的概念、存储结构及其基本操作 ⚫ 栈与队列的应用举例 退出
3.1栈 3.1.1栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入 和删除数据元素的操作只能在线性表的一端进行。如 下所示: 插入和删除端 进行插入和删除的一端是浮动端,通常被称为栈 顶,并用一个“栈顶指针”指示;而另一端是固定端, 通常被称为栈底。我们经常将栈用下图3-的形式描述: 请单鼠标左键换页!
3.1 栈 3.1.1 栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入 和删除数据元素的操作只能在线性表的一端进行。如 下所示: 进行插入和删除的一端是浮动端,通常被称为栈 顶,并用一个“栈顶指针”指示;而另一端是固定端, 通常被称为栈底。我们经常将栈用下图3-1的形式描述: a1 , a2 , a3 , ..., an 插入和删除端
结论:后进先出( Last in first out),简称为 LIFO线性表。 举例1:家里吃饭的碗,通常在洗干净后一个一个 地落在一起存放,在使用时,若一个一个地拿,一定 最先拿走最上面的那只碗,而最后拿出最下面的那只 碗。 举例2:在建筑工地上,使用的砖块从底往上一层 层地码放,在使用时,将从最上面一层一层地拿取。 下面我们先给出栈结构的基本操作: (1)初始化栈 Initstack(S) (2)入栈Push(Stem) (3)出栈Pop(S,tem) (4)获取栈顶元素内容 GetTop(S,item) (5)判断栈是否为空 StackEmpty(S) 请单赤鼠标左键换页!
结论:后进先出(Last In First Out),简称为 LIFO线性表。 举例1:家里吃饭的碗,通常在洗干净后一个一个 地落在一起存放,在使用时,若一个一个地拿,一定 最先拿走最上面的那只碗,而最后拿出最下面的那只 碗。 举例2:在建筑工地上,使用的砖块从底往上一层 一层地码放,在使用时,将从最上面一层一层地拿取。 下面我们先给出栈结构的基本操作: (1)初始化栈 InitStack(S) (2)入栈 Push(S,item) (3)出栈 Pop(S,item) (4)获取栈顶元素内容 GetTop(S,item) (5)判断栈是否为空StackEmpty(S)
3.1.2栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次 存放栈中的每个数据元素,并用起始端作为栈底。 类型定义如下所示: #define max stack 1o 栈的最大数据元素数目 typedef struct stack( StackEntry item MAX STaCK; 放栈中数据元素的存储单元 int top ∥栈顶指针 STACK: 请单赤鼠标左键换页!
3.1.2 栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次 存放栈中的每个数据元素,并用起始端作为栈底。 类型定义如下所示: #define MAX_STACK 10 //栈的最大数据元素数目 typedef struct stack{ StackEntry item[MAX_STACK]; //存放栈中数据元素的存储单元 int top; //栈顶指针 }STACK;
基本操作算法: 1.初始化栈S void InItStack(STACK*S) {s->top=-1;} 2.入栈 void Push(stacK*'S, Stack Entry item) f(S->top= MAX STACK-1)exit(“ Stack is fu”); else s->item[++S->top]=item; 请单赤鼠标左键换页!
基本操作算法: 1. 初始化栈S void InItStack(STACK *S) { s->top=-1; } 2. 入栈 void Push(STACK *S,StackEntry item) { if (S->top==MAX_STACK-1) exit(“Stack is full”); else S->item[++S->top]=item; }
3.出栈 void Pop(stacK s, StackEntry *item) if( StackEmpty(S)exit(“ Stack is empt!y”); else *item=S->item(S->top-; 4.获取栈顶元素内容 void GetTop(stack s, stack Entry *item) if( StackEmpty(S) exit(“ Stack is empty”); else *itel m=S item(S top; 请单赤鼠标左键换页!
3. 出栈 void Pop(STACK *S,StackEntry *item) { if (StackEmpty(*S)) exit(“Stack is empty”); else *item=S->item[S->top--]; } 4. 获取栈顶元素内容 void GetTop(STACK S,StackEntry *item) { if (StackEmpty(S)) exit(“Stack is empty”); else *item=S.item[S.top]; }
5.判断栈S是否为空 int StackEmpty(sTACK S) if(S top==-D)return TRUE else false 结论:由于栈的插入和删除操作具有它的特殊性, 所以用顺序存储结构表示的栈并不存在插入删除数据 元素时需要移动的问题,但栈容量难以扩充的弱点仍 就没有摆脱。 请单赤鼠标左键换页!
5. 判断栈S是否为空 int StackEmpty(STACK S) { if (S.top==-1) return TRUE; else FALSE; } 结论:由于栈的插入和删除操作具有它的特殊性, 所以用顺序存储结构表示的栈并不存在插入删除数据 元素时需要移动的问题,但栈容量难以扩充的弱点仍 就没有摆脱
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第一章 数据结构基础概论.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第9章 数组.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第8章 函数.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第7章 循环结构程序设计.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第6章 选择结构程序设计.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第5章 顺序结构程序设计.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第4章 数据类型及表达式.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第3章 C语言概述.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第2章 程序设计基础知识.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第15章 编译预处理.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第13章 中断和位运算.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第12章 文件.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第11章 结构体、联合体与枚举类型.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第10章 指针.ppt
- 人民邮电出版社:高等学校教材《C程序设计》课程教学资源(PPT课件)第1章 计算机基础知识.ppt
- 湖南科学技术出版社:高等教育21世纪课程《大学计算机基础》课程教学资源(教材PPT)第十章 信息系统安全与社会责任.ppt
- 湖南科学技术出版社:高等教育21世纪课程《大学计算机基础》课程教学资源(教材PPT)第九章 软件开发与信息处理技术.ppt
- 湖南科学技术出版社:高等教育21世纪课程《大学计算机基础》课程教学资源(教材PPT)第八章 Internet与Intranet.ppt
- 湖南科学技术出版社:高等教育21世纪课程《大学计算机基础》课程教学资源(教材PPT)第七章 计算机网络基础.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第四章 串和数组.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第五章 树和二叉树.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第六章 图.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第七章 查找.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第八章 排序.ppt
- 人民邮电出版社:高职高专现代信息技术系列教材《数据结构》课程电子教案(PPT课件讲稿)第九章 文件.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第五章 C++程序的结构.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第六章 数组、指针与字符串.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第七章 继承与派生.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第八章 多态性.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第九章 群体类和群体数据的组织.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第十章 C++标准模板库.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第十一章 流类库与输入/输出.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第十二章 异常处理.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)课程简介(李莉).ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第一章 绪论.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第二章 C++简单程序设计.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第三章 函数.ppt
- 清华大学:《C++语言程序设计》课程教学资源(PPT课件)第四章 类与对象.ppt
- 天津大学:《数据结构 Data Structures》课程教学资源(PPT课件讲稿)第二章 线性表.ppt