第4周栈和队列第1讲-栈的定义和顺序栈.pdf
《第4周栈和队列第1讲-栈的定义和顺序栈.pdf》由会员分享,可在线阅读,更多相关《第4周栈和队列第1讲-栈的定义和顺序栈.pdf(22页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 栈栈是一种只能在一端进行插入或删除操作的线性表。是一种只能在一端进行插入或删除操作的线性表。 3.1.1 栈栈的定义的定义 端点端点1端点端点2 栈栈只能选取同一只能选取同一个端点进行个端点进行插入和删除插入和删除操作操作 线线 性性 表表 允许允许进行插入、删除操作的一端称为进行插入、删除操作的一端称为栈栈顶顶。 表表的另一端称为的另一端称为栈底栈底。 当当栈中没有数据元素时栈中没有数据元素时,称为称为空栈空栈。 栈栈的插入操作通常称为的插入操作通常称为进栈进栈或或入入栈栈。 栈栈的删除操作通常称为的删除操作通常称为退栈退栈或或出栈出栈。 栈顶栈顶 栈底栈底 栈示意图栈示意图 进栈进栈出栈
2、出栈 栈的几个概念栈的几个概念 栈的主要特点是“后进先出”,即后进栈的元素先出栈。栈栈的主要特点是“后进先出”,即后进栈的元素先出栈。栈 也称为也称为后进先出后进先出表。表。 走进死胡同的走进死胡同的5人人要要 按按相反次序退出相反次序退出 假设死胡同的宽度恰假设死胡同的宽度恰 好只够正一个人好只够正一个人 死胡同就是一个栈!死胡同就是一个栈! 例如:例如: 【例例3- -1】设一个栈的输入序列为设一个栈的输入序列为a,b,c,d,则借助一个栈所得则借助一个栈所得 到的输出序列不可能是到的输出序列不可能是。 A. c,d,b,aB. d,c,b,a C. a,c,d,bD. d,a,b,c a
3、bcd 选项选项D是是不可能不可能的的? 栈栈 下一步不可能出栈下一步不可能出栈a 【例例3- -2】一个栈的入栈序列为一个栈的入栈序列为1,2,3,n ,其出栈序列是,其出栈序列是p1, p2,p3, , pn。若若p1=3,则则p2可能可能取值的个数是取值的个数是。 A.n- -3 B.n- -2C.n- -1 D. 无法确定无法确定 栈栈 1 2 3? n 4 不可能是不可能是1和和3 共有共有n- -2可能可能 1、2、3进栈,进栈, 3出栈的时刻:出栈的时刻: 栈的几种基本运算如下栈的几种基本运算如下: 栈抽象数据类型逻辑结构基本运算(运算描述)栈抽象数据类型逻辑结构基本运算(运算描
4、述) 栈中元素逻辑关系与线性表的相同,栈可以采用与线性表相栈中元素逻辑关系与线性表的相同,栈可以采用与线性表相 同的存储结构。同的存储结构。 栈栈 顺序栈顺序栈链栈链栈 逻辑结构逻辑结构 存储结构存储结构 3.1.2 栈栈的顺序存储结构及其基本运算实现的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数假设栈的元素个数最大不超过正整数MaxSize,所有的元素都,所有的元素都 具有同一数据类型具有同一数据类型ElemType,则可用下列方式来,则可用下列方式来定义定义顺序栈顺序栈类型类型 SqStack: typedef struct ElemType dataMaxSize; i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 森林经营规划
限制150内