第四章-栈和队列.ppt

4.1栈4.1.1栈的定义栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把对栈进行运算的一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。4.1栈4.1.2栈的运算概述(1)初始化栈S，即把它置为空voidInitStack(S);(2)新元素x进栈，即把x值插入到栈顶voidPush(S,ElemTypex);(3)删除栈顶元素并返回之ElemTypePop(S);(4)返回栈顶元素的值，不会改变栈的状态ElemTypePeek(S);(5)判断栈S是否为空，若是则返回1表示真，否则返回0表示假intEmptyStack(S);(6)清除栈S中的所有元素，使之成为一个空栈voidClearStack(S);4.2栈的顺序存储和操作实现栈的顺序存储结构需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。假定栈数组用stack[MaxSize]表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储结构可定义为：ElemTypestack[MaxSize];inttop;其中，MaxSize为一个整型全局常量，需事先定义，由它确定顺序栈（即顺序存储的栈）的最大长度，又称为深度，即栈空间最多能够存储的元素个数；由于top用来指示栈顶元素的位置，所以把它称为栈顶指针。4.2栈的顺序存储和操作实现栈的顺序存储结构所使用的栈数组和栈顶指针定义在一个记录类型中，假定该记录类型用StackSq表示，则定义为：structStackSq{ElemTypestack[MaxSize];inttop;};若要对存储栈的数组空间采用动态分配，则structStackSq结构类型可定义为：structStackSq{ ElemType*stack;/*存栈元素的数组指针*/inttop;/*存栈顶元素的下标位置*/ intMaxSize;/*存stack数组长度*/};4.2栈的顺序存储和操作实现4.2栈的顺序存储和操作实现1.初始化栈S为空此操作可以包括两种情况，一种是置空并隐含分配固定大小的动态存储空间，另一种是置空并分配由参数指定大小的动态存储空间。首先给出第一种置空的算法。voidInitStack(structStackSq*S){/*置栈空间初始最大长度为10*/ S-MaxSize=10; /*动态存储空间分配*/ S-stack=malloc(10*sizeof(ElemType));/*置栈为空*/ S-top=-1;}4.2栈的顺序存储和操作实现1.初始化栈S为空第二种置空栈的算法。voidInitStack(structStackSq*S,intms){ /*检查ms是否有效，若无效则退出运行*/ if(ms=0){printf(ms的值非法!\n);exit(1);} /*置栈空间大小为ms*/ S-MaxSize=ms; /*动态存储空间分配，若分配失败则退出运行*/ S-stack=malloc(ms*sizeof(ElemType)); if(!S-stack){ printf(动态存储分配失败!\n); exit(1); }/*初始置栈为空*/ S-top=-1;}4.2栈的顺序存储和操作实现