栈的概念及顺序栈的基本操作

《栈的概念及顺序栈的基本操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3栈和队列主要内容3.1栈3.2栈的应用3.3栈和递归的实现3.4队列3.1栈一、栈(stack)的概念栈(stack)：是插入和删除操作都限制在表尾的线性表。入(压)栈出栈(弹出)栈的逻辑表示：S=(a1,a2,a3,…an)栈底栈顶a1：栈底元素an：栈顶元素空栈：不含任何元素的空表先进后出(FirstInLastOut)：FILO后进先出(LastInFirstOut)：LIFO栈的特性例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。练习：三个元素A、B、C依次入栈，入栈过程中允许

2、栈顶元素出栈。出栈的序列可能有几种？CBA例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。练习：三个元素A、B、C依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有几种？CBA例如：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。练习：三个元素A、B、C依次入栈，入栈过程中允许栈顶元素出栈。出栈的序列可能有几种？CBABACABCCBABCAACB二、基本操作InitStack(&S)初始化，构造一个空栈SDest

3、royStack(&S)销毁栈SClearStack(&S)清空栈SStackEmpty(S)判断栈S是否为空StackLength(S)栈S的长度(栈中元素个数)GetTop(&S,&e)取栈顶元素Push(&S,e)入(压)栈(即插入元素)Pop(&S,&e)出栈(弹出)(即删除元素)三、顺序栈(栈的顺序存储结构)的表示和实现顺序栈的类型定义#defineSTACK_INIT_SIZE100//栈的最大元素数目#defineSTACKINCREMENT10//存储空间分配增量typedefstructstack{SElemType*base;//栈底指针SElemType*top;//

4、栈顶指针intstacksize;//已分配存储空间数}SqStack;判空条件：S.base=S.top基本操作的算法描述1.初始化栈SvoidInItStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}2.入栈intPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//栈满S.base=

5、(SElemType*)realloc(S.base,.stacksize+STACKINCREMENT)*sizeof(SElemType));//申请扩大容量if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}S.top=e;S.top++;returnOK;}3.出栈intPop(SqStack&S,SElemType&e){if(StackEmpty(S))returnERROR;e=*(S.top-1);S.top--;returnOK;}4.获取栈顶元素内容intGetTop(

6、SqStackS,SElemType&e){if(StackEmpty(S))returnERROR;elsee=*(S.top-1);returnOK;}3.1.3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如右图所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。^topbase3.2栈的应用【例1】十进制转换成二进制使用展转相除法将一个十进制数

7、值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10=(1010110100)2，其展转相除的过程如右图所示：69234617386432110521022222222221010110100十进制转换成二进制算法voidconversion(){//对于输入的任意一个非负十进制整数,//打印输出与其等值的二进