栈的原理与应用.ppt

《栈的原理与应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§2.2栈的原理与应用栈的基本概念1.什么是栈栈（stack）是一种运算受限的线性表，它限定只能在表的一端进行插入和删除等操作。（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除02栈的基本概念允许进行插入和删除操作的一端称为栈顶（top）另一端称为栈底（bottom）不含元素的栈称为空栈出栈Pop进栈Push栈顶栈底top空栈topbottoman...a2a12.栈的逻辑结构bottom03栈的基本概念3.进栈与出栈栈的特点：先进后出（FILO）或后进先出（LIFO）bottomtopbottomtopAABCDEABA进栈BCDE进栈EDC出栈CD

2、Etoptoptoptopbottomtopbottomtoptoptop图2.1进栈与出栈操作0405栈的应用举例（a）车轨设置（b）驶入（c）驶出图2.2火车调度模型火车头1火车头2火车头2火车头1火车调度装置的功能与栈的功能类同思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA06栈的问题实例07栈的基本操作（1）构造栈。（2）判栈空。（3）判栈满。（4）进栈。（5）出栈。（6）取栈顶元素。08栈的顺序存储结构1.顺序栈的类型定义#defineStackSize100//顺序栈存储空间的总分配量ty

3、pedefstruct//顺序栈存储类型{DataTypedata[StackSize];//存放顺序栈的数组inttop;//记录栈顶元素位置的变量}SeqStack;顺序栈被定义为一个结构体类型，其中DataType为栈元素的数据类型，可以根据需要而指定某种具体的类型。data为一个一维数组，用于存储栈中的数据元素，top为int类型，用于记录栈顶元素所在的位置。当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？？顺序栈的图示topStackSize-1nn-1n-210anan-1a2a1栈空：top=-1栈满：top=StackSize-1约

4、定栈顶指针指向栈顶元素的位置。栈的顺序存储结构0910顺序栈的基本操作实现首先创建一个空栈，并将栈顶下标top初始化为-1voidInitStack(SeqStack*S){S->top=-1;//初始化的顺序栈为空}（1）初始化栈操作11顺序栈的基本操作实现（2）判断栈空操作判断是否是空栈（即S->top==-1），若栈S为空，则返回1；否则返回0。#defineTRUE1#defineFALSE0intStackEmpty(SeqStack*S){if(S->top==-1)//栈为空returnTRUE;elsereturnFALSE;}（3）判栈满操作判断是否是

5、满栈（即S->top==StackSize-1），若栈S为满栈，则返回1；否则返回0。intStackFull(SeqStack*S){if(S->top==StackSize-1)returnTRUE;elsereturnFALSE;}顺序栈的基本操作实现12anan-1a2a1x进栈前toptopxanan-1a2a1anan-1a2a1栈顶指针增加1topx进栈后（4）进栈操作图2.3进栈操作过程图StackSize-1nn-1n-210StackSize-1nn-1n-210StackSize-1nn-1n-210顺序栈的基本操作实现13（4）进栈操作intPu

6、sh(SeqStack*S,DataTypex){if(StackFull(S)){//栈为满printf("栈满!");returnFALSE;}//栈满不能进栈else{//栈不为满S->top++;S->data[S->top]=x;returnTRUE;}}顺序栈的基本操作实现14anan-1a2a1an出栈前toptopan-1a2a1anan-1a2a1将栈顶元素赋给*xtopan出栈后（5）出栈操作图2.4出栈操作过程图StackSize-1nn-1n-210StackSize-1nn-1n-210StackSize-1nn-1n-210顺序栈的基本操作实

7、现15顺序栈的基本操作实现intPop(SeqStack*S,DataType*x){if(StackEmpty(S)){//判断栈是否为空printf("栈空!");returnFALSE;//栈空不能出栈}else{//栈不为空*x=S->data[S->top];S->top--;returnTRUE;}}（5）出栈操作16顺序栈的基本操作实现intStackTop(SeqStack*S,DataType*x){if(StackEmpty(S)){//判断栈是否为空printf("栈空!");returnFALSE;}else{//