栈的操作算法实现.doc

《栈的操作算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一顺序栈的实现#definemaxsize6/*顺序栈的容量*/typedefstruct{ElementTypedata[maxsize];inttop;}SqStackTp;顺序栈被定义为一个结构类型，它有两个域data和top。data为一个一维数组，用于存储栈中元素，DataType为栈元素的数据类型（有待设定）。top为int型，它的取值范围为0..sqstack_maxsize-1。top=0表示栈空，top=sqstack_maxsize-1表示栈满。对于图3-2顺序栈sqstack

2、_maxsize应为6。　　下面讨论栈的基本运算在顺序栈上的实现。1.初始化:初始化运算是将栈顶初始化为0;intInitStack(SqStackTp*sq){sq->top=-1;return(1);}2.进栈:　　进栈的主要操作是：①栈顶下标加1;②将入栈元素放入到新的栈顶下标所指的位置上。算法如下：intPush(SqStackTp*sq,ElementTypex) /*若栈未满，将元素x入栈sq中；否则提示出错信息*/　{if(sq->top==maxsize-1)　{printf("栈

3、满");return(0);}　else　{sq->top++;sq->data[sq->top]=x;return(1);}　　}3.退栈:退栈先要将栈顶元素取出，由参数返回，并将栈顶减１。　　intPop(SqStackTp*sq,ElementType*x);　　{if(sq->top==-1){printf("下溢");return(0);}　　　else{*x=sq->data[sq->top];sq->top--;return(1);}　　};4.判栈空:　　intEmptyStack

4、(SqStackTp*sq)　/*若栈空返回1;否则返回0*/　　{　if(sq->top==-1)return(1)　elsereturn(0);　　}5.读栈顶元素:intGetTop(SqStackTp*sq,ElementType*x) /*取栈顶元素，栈顶元素通过参数返回*/　{if(sq->top==-1)return(0);　　else{*x=sq->data[sq->top];return(1);}　　}6.顺序栈应用举例(进栈与出栈)　#include"stdio.h"　#def

5、ineElementTypechar　#definemaxsize40　typedefstruct　{ElementTypedata[maxsize];　　inttop;　}SqStackTp;　intInitStack(SqStackTp*sq)　{sq->top=-1;return(1);}　intPush(SqStackTp*sq,ElementTypex)　{if(sq->top==maxsize-1)　{printf("栈满");return(0);}　　else　{sq->top++;

6、sq->data[sq->top]=x;return(1);}　}intPop(SqStackTp*sq,ElementType*x)　{if(sq->top==-1){printf("下溢");return(0);}　　else{*x=sq->data[sq->top];sq->top--;return(1);}　}　intEmptyStack(SqStackTp*sq)　{if(sq->top==-1)return(1);　elsereturn(0);　}/*主函数*/　voidmain()　

7、{SqStackTpsq;　　typedefchElementType;　　InitStack(&sq);　　for(ch='A';ch<='A'+12;ch++)　　{Push(&sq,ch);printf("%c",ch);}　　printf("");　　while(!EmptyStack(&sq))　　{Pop(&sq,&ch);printf("%c",ch);} 　　printf("");　}　运行结果：ABCDEFGHIJKLM　　　　　　MLKJIHGFEDCBA二链栈的实现链

8、栈类型定义如下：typedefstructnode　{ElementTypedata;　　structnode*next;　}node；node*LStackTp;　下面讨论栈的基本运算在链栈上的实现。1.初始化:栈初始化的作用是设置一个空栈。而一个空的链栈可以用栈顶指针为NULL来表示。voidInitStack(LStackTp*ls)　　{　*ls=NULL;　　}2.进栈:进栈算法的基本步骤包括：　　①申请一个新结点,并将x的值送入该结点的data域;②将该结点链入栈中使之