首页 > 知识点讲解
       栈
知识路径: > 计算机科学基础 > 常用数据结构 > 队列、栈 > 
被考次数:30次     被考频率:高频率     总体答错率:42%     知识难度系数:     
考试要求:掌握      相关知识点:17个      
               栈的定义
               栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶,相反,栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素,不含任何数据元素的栈称为空栈。栈的特点为后进先出(Last In First Out, LIFO)。
               下图是一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。
               
               栈的出入示意图
               栈的基本操作
               栈的基本操作主要有以下6种。
               .InitStack(&S):初始化操作,构造一个空栈S。
               .StackEmpty(S):若栈S为空栈,返回1,否则返回0。
               .Push(&S, e):插入元素e为新的栈顶元素。
               .Pop(&S,&e):删除S的栈顶元素,并用e返回其值。
               .GetTop(S,&e):用e返回S的栈顶元素。
               .ClearStack(&S):将S清为空栈。
               栈的顺序存储结构
               栈的顺序存储用向量作为栈的存储结构,向量S表示栈,m表示栈的大小,用指针top指向栈顶位置,S[top]表示栈顶元素,当在栈中进行插入、删除操作时,都要移动栈指针;而当top=m-1时,则栈满,当top=-1时,表示栈空。同时为了避免浪费空间可以采用双栈机制,即向量的两端为栈底。
               栈的顺序存储结构的C语言描述如下:
               
               栈的说明如下。
               .由于C语言的数组下标的范围从0至StackSize-1,初始化设置sq.top=-1。
               .栈空条件为sq.top=-1,栈满条件为sq.top=StackSize-1。
               .栈顶元素为sq.data[sq.top]。
               .元素压栈的规则为:在栈不满时,先改变栈顶指针(top=top+1),再压栈。出栈时,在桟非空时,先取栈顶元素的值,再修改栈顶指针(top=top-1)。
               .栈中元素的个数为当前栈顶指针加1。
               在顺序栈上实现基本操作的有关函数如下。
               1)初始化InitStack(SqStack *S)
               
               2)判空StackEmpty(SqStack S)
               
               3)压栈Push(SqStack *S, ElemType e)
               
               4)出栈Pop(SqStack *S, ElemType *e)
               
               5)取栈顶GetTop(SqStack *S, ElemType*e)
               
               6)清栈ClearStack(SqStack *S)
               
               栈的链式存储结构
               栈的链式存储也叫链栈,我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链栈操作比较方便。
               链栈的节点类型定义如下:
               
               链栈的约定与说明如下。
               .栈以链表的形式出现,链表(不带头节点)首指针为S,即栈顶为S,链表尾节点为栈底。
               .初始化时,S=NULL(不带头节点);S=(LStack *),malloc(sizeof(LStack)),S→next=NULL(带头节点)。
               .栈顶指针的引用为S(不带头节点)或S→next(带头节点),栈顶元素的引用为S→data(不带头节点)或S→next→data(带头节点)。
               .栈空条件为S==NULL(不带头节点)或S→next=NULL(带头节点)。
               .进栈操作和出栈操作与单链表在开始节点的插入和删除操作一致。
               对不带头节点的链栈,其基本操作函数如下。
               1)初始化initstack(LStack *S)
               
               2)压栈(入栈)push(LStack *S, ElemType x)
               
               3)退栈(出栈)pop(LStack *S, ElemType *x)
               
               4)读栈顶元素gettop(LStack *S, ElemType *x)
               
               5)判栈空isempty(LStack *S)
               
               栈的应用
               栈具有广泛的应用,例如,求表达式的值及递归到非递归等。
               1)表达式求值
               在源程序编译中,若要把一个含有表达式的赋值语句翻译成正确求值的机器语言,首先应正确地解释表达式。例如,对赋值语句X=4+8×2-3;,其正确的计算结果应该是17,但若在编译程序中简单地按自左向右扫描的原则进行计算,则为:X=12×2-3=24-3=21。这个结果显然是错误的。因此,为了使编译程序能够正确地求值,必须事先规定求值的顺序和规则。通常采用运算符优先法。
               2)递归到非递归
               将一个递归算法转换为功能等价的非递归算法有很多方法,可以使用栈保存中间结果。其一般形式如下:
               
               例如,求n!的递归函数如下:
               
               使用转换成等价的非递归算法如下:
               
               其中,st[top][0]用于存放n值,st[top][1]用于存放n!值,在初始时,设置st[top][1]为0,表不n!尚未求出。
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2019年下半年
   程序员
   上午试卷 综合知识
第36题
选择题
数据结构中的(36)常用来对函数调用和返回处理的控制进行支持。

43%
   2019年上半年
   程序员
   上午试卷 综合知识
第36题
选择题
令序列X、Y、Z的每个元素按顺序进栈,且每个元素进栈、出栈各一次,则不可能得到出栈序列( )。

36%
>>  更多  本知识点历年真题
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2019 All Rights Reserved 软考在线版权所有