数据结构课件第3章

《数据结构课件第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈、队列第三章栈、队列3.1栈3.2栈的应用举例3.3栈与递归3.4队列3.1栈3.1.1栈的概念3.1.2栈的顺序存储和实现3.1.3栈的链式存储和实现3.1栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除3.1.1栈的概念一   什么是栈?3.1栈将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。栈3.1

2、栈栈的示意图出栈进栈栈的特点后进先出第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素栈顶栈底ana2a13.1栈栈的基本操作数据元素：可以是任意类型的数据，但必属于同一个数据对象。关系：栈中数据元素之间是线性关系。1） 构造一个空栈S；2）进栈操作Push3）出栈操作Pop4)取栈顶元素top3.1栈topbasebasetopbasetopbasetopAABCDEAB栈操作图示空栈A进栈BCDE进栈EDC出栈3.1栈3.1.2栈的顺序存储和实现如何存储栈?进栈、出栈等操作如何实现？？#d

3、efineMAX50intstack[MAX];inttop=0;3.1栈约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等操作如何实现？？顺序栈的图示topMAX-1nn-1n-210anan-1a2a13.1栈1)进栈操作主要语句if(top>=MAX)printf(“overflow”);else{stack[top]=x;top++;}MAX-1nn-1n-210anan-1a2a1x进栈前topx进栈后MAX-1nn-1n-210xanan-1a2a1top3.1栈2）出栈操作主要语句if(top=

4、=0){printf(“underflow”);return(NULL);}top--;return(stack[top]);出栈操作前出栈操作后MAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210anan-1a2a1toptop教材中顺序栈的数据类型定义：typedefstructSqStack{SelemType*base;//栈底指针SelemType*top;//栈顶指针intstacksize；//当前已分配的存储空间}SqStack;基本操作P47共享栈技术（最常用的是两个栈的共享）：主要利用栈“栈底位置

5、不变，栈顶位置动态变化”的特性。为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，形成互补，使得每个栈可用的最大空间与实际使用的需求有关。两栈共享比两个栈分别申请M/2的空间利用率高。设两个栈共享的数据结构定义如下：＃defineM100typedefstructDqStack{SElemTypeStack［M］;inttop［2］;//top［0］和top［1］分别为两个栈顶指示器}DqStack;共享栈初始化操作?初始化操作。voidInitStack(DqSta

6、ck*S){S.top［0］=0;S.top［1］=M-1;}进栈操作算法?intPush(DqStack*S,SElemTypex,inti)//把数据元素x压入i号栈(2)进栈操作算法。intPush(DqStack*S,StackElementTypex,inti){//把数据元素x压入i号栈if(S.top［0］+1==S.top［1］)//栈已满return(FALSE);switch(i){case0:S.Stack［S.top［0］］=x;S.top［0］++;break;case1:S.Stack［S.t

7、op［1］］=x;S.top［1］--;break;default://i参数错误return(FALSE)}return(TRUE);}出栈操作算法?intPop(DqStack*S,SElemType*x,inti)//从i号栈中弹出栈顶元素并送到x中(3)出栈操作算法。intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S.top［0］==0)return(FALSE);S.top［0］--;*x=S.Stack［S.top［0］］;break;

8、case1:if(S.top［1］==M-1)return(FALSE);S.top［1］++;*x=