第3章 栈(new).ppt

《第3章 栈(new).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用数据结构基础第3章栈第3章栈知识点栈的定义和特点栈的典型应用难点后缀表达式的算法数制的换算要求掌握栈的特点熟悉栈的各种实际应用3-1栈的定义和运算3-1-1栈（Stack）的定义1.栈的定义栈是限制在表尾进行插入和删除的线性表。a1a2a3进栈出栈图3-1栈的示意图2.栈的特性（1）栈的主要特点是“后进先出”（2）允许插入、删除的这一端称为栈顶（Top），另一端称为栈底（Bottom）。3.应用实例（1）分币筒；（2）铁路调度站。3-1-2栈的运算1．进栈：Push（&s，x）初始条件：栈s已存在且非满。操作结果：在栈顶插入一个元素x，栈中多了一个元素。2

2、．出栈：Pop（&s）初始条件：栈s存在且非空。操作结果：删除栈顶元素，栈中少了一个元素。3．读栈顶元素：ReadTop（s，&e）初始条件：栈s已存在且非空。操作结果：输出栈顶元素，但栈中元素不变。4.判栈空：SEmpty（s）初始条件：栈s已存在。操作结果：若栈空则返回为0，否则返回为1。5.判栈满：SFull（s）初始条件：栈s已存在。操作结果：若栈满则返回为0，否则返回为1。6.显示栈元素：ShowStack(s)初始条件：栈s已存在 ，且非空。操作结果：显示栈中所有元素。3-2栈的存储和实现3-2-1顺序栈1．顺序栈的实现（1）用一维数组实现顺序栈设

3、栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#defineMAXLEN10//分配最大的栈空间chars[MAXLEN]；//数据类型为字符型inttop；//定义栈顶指针（2）用结构体数组实现顺序栈顺序栈的结构体描述：#defineMAXLEN10//分配最大的栈空间typedefstruct//定义结构体{datatypedata[MAXLEN];//datatype可根据用需要定义类型inttop；//定义栈顶指针}SeqStack；再定义一

4、个指向顺序栈的指针：SeqStack*S；//定义S为结构体类型的指针变量（3）栈操作的示意图如图3-3所示。AFEDCBAFEDCBAJIHGFEDCBAtop=-1top=0top=5top=3top=9(a)(b)(c)(d)(e)当top=-1时，表示栈空，如图3-3（a）；当top=0时，表示栈中有一个元素，如图3-3（b）表示栈中已输入一个元素A；入栈时，栈顶指针上移，指针top加1，如图3-3（c）是6个元素入栈后的状况；出栈时，栈顶指针下移，指针top减1，如图3-3（d）是在F、E相继出栈后的情况。此时栈中还有A、B、C、D4个元素，top=

5、3，指针已经指向了新的栈顶。但是出栈的元素F、E仍然在原先的存储单元，只是不在栈中了，因为栈是只能在栈顶进行操作的线性表。当top=9时，即top=MAXLEN–1，表示栈满，如图3-3（e）。2．顺序栈运算的基本算法（1）置空栈首先建立栈空间，然后初始化栈顶指针。SeqStack*Snull（）{SeqStack*s；s=new(SeqStack)；//在C语言中用s=malloc（sizeof（SeqStack））；s->top=–1；//置栈空returns；}（2）进栈进栈运算是在栈顶位置插入一个新元素x，其算法步骤为：(a)判栈是否为满，若栈满，作溢

6、出处理，并返回0；(b)若栈未满，栈顶指针top加1；(c)将新元素x送入栈顶，并返回1。intPush(SeqStack*s，datatypex){if（s->top==MAXLEN–1）return0；//栈满不能入栈，且返回0else{s->top++；s->data[s->top]=x；//栈不满，则压入元素xreturn1；}//进栈成功，返回1}（3）出栈出栈运算是指取出栈顶元素，赋给某一个指定变量x，其算法步骤为：(a)判栈是否为空，若栈空，作下溢处理，并返回0；(b)若栈非空，将栈顶元素赋给变量x；(c)指针top减1，并返回1。intPop（

7、SeqStack*s，datatype*x）{if(SEmpty(s))return0；//若栈空不能出栈，且返回0else{*x=s->data[s->top]；//栈不空则栈顶元素存入*xs->top--；return1；}//出栈成功，返回1}（4）读栈顶元素datatypeReadTop（SeqStack*s）{if(SEmpty(s))return0；//若栈空，则返回0elsereturn(s->data[s->top])；//否则，读栈顶元素，但指针未移动}（5）判栈空intSEmpty（SeqStack*s）{if（s->top==–1）ret

8、urn1；//若栈空，则返回1else