计算机软件技术基础

《计算机软件技术基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础教师：曾晓东电话：13679007201E_mail:zengxiaodong@263.net3.4栈一、栈的定义二、栈的运算三、栈的存储结构及算法四、栈的应用计算机软件技术基础数据结构——栈和队列一、栈的定义栈是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。设栈s=(a1,a2,...,an)，a1称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,...,an次序进栈，又按an,...,a2,a1次序退栈。因此栈的操作特点是：后进先出（LIFO）；n=0时称为空栈

2、。anan-1a1stack[n-1]top栈顶进栈stack[0]栈底出栈计算机软件技术基础数据结构——栈和队列二、栈的运算1.初始化栈INISTACK(S)将栈S置成空栈2.判空栈ISEMPTY(S)若栈S是空栈，返回“真”，否则返回“假”3.进栈PUSH(S,x)在栈S顶部插入（压入）元素x4.出栈POP(S)若栈S不空，删除顶部元素5.取栈顶GETTOP(S)取栈顶元素，并不改变栈中内容计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法1.顺序栈1)类型定义顺序栈用向量作为栈的存储结构，可用一维数组s[1:m]表示。其中m表示栈的最大容量。

3、用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空，top=m表示栈满。类型定义structSeqStack{elemtypestack[MAXSIZE];inttop;};计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法2）顺序栈初始化⑴操作:建一空栈，将栈顶位设置为-1⑵接口：入口和出口参数均为堆栈指针s⑶算法描述：令栈顶位s.top为-1⑷函数实现：voidiniStack(SeqStack&s){s.top=-1;}计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法3)进栈算法⑴操作:先将栈顶位置加一将数据放

4、入栈顶位置⑵接口：入口参数：堆栈指针s，新数据元素x出口参数:堆栈指针s函数值：成功则返回1(用true表示),失败则返回0(用false表示)计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法(3)算法描述计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法(4)函数实现intpush(SeqStack&s,elemtypex){if(s.top>=MAXSIZE-1)return(false);s.top++;s.stack[s.top]=x;return(true);}计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法4)出

5、栈算法(1)操作取栈顶位置内数据.再将栈顶位置减一(2)接口入口参数：堆栈指针s出口参数:堆栈指针s函数值：成功则返回数据元素x,失败则返回NULL计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法(3)算法描述计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法(4)函数实现elemtypepop(SeqStack&s){if(s.top<0)returnNULL;s.top--;returns.stack[s.top+1];}计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法5)双栈操作顺序栈的缺点：栈满后不能进行进栈操作，否

6、则将产生“上溢”错误同时使用同类的两个栈，充分利用剩余空间两栈共用一个存储空间，分别从两端向中间增长a1a2……an……bm……b2b101n-1出栈MAXSIZE-mMAXSIZE-2MAXSIZE-1栈1底栈1顶入栈栈2顶栈2底计算机软件技术基础数据结构——栈和队列三、栈的存储结构及算法2.链栈链栈是用链表作为栈的存储结构，top为栈顶指针，指示栈顶元素位置，若top=NULL,则表示栈空。链栈一般不会出现上溢，除非内存中已不存在可用空间。使用单链表，不设头结点插入和删除仅在表头一端栈顶top：指始结点，浮动空栈用top=NULL实现链栈结点动态分配，空

7、间无限链栈定义与单链表相同structlink*top；.a2topaia1NULL计算机软件技术基础数据结构——栈和队列四、栈的应用表达式求值1）高级语言中的表达式是用人们熟悉的公式形式书写的，编译系统要根据表达式的运算顺序将它翻译成机器指令序列。2）为解决运算顺序问题，把运算符分成若干等级，称为优先数。3）为进行表达式的翻译，需设立两个栈，分别存放操作数(NS)和运算符(OS)。计算机软件技术基础数据结构——栈和队列四、栈的应用4）首先在OS中放入表达式结束符“#”，然后自左至右扫描表达式，根据扫描的每一个符号作如下不同处理：①若为操作数，将其压入NS栈

8、②若为运算符，需看当前OS的栈顶元素：若OS栈顶运算