第四章栈和队列-Read.ppt

第4章 栈和队列;栈的定义;栈的运算 ; 栈的表示方式 ;栈的顺序存储结构;顺序栈中数据元素和栈顶指针之间的对应关系;静态数组实现栈结构 ;顺序栈的模块说明 ;判栈空操作： int empty(s) seqstack *s; { if(s-top==s-base) return true; else return false; } ;进栈操作： seqstack *Push(s,x) /* 将元素x插入顺序栈s的顶部*/ seqstack *s; datatype x; { if (s-top==maxsize) { printf(overflow); return NULL; } else { s-data[s-top]=x; s-top++; } return s; };出栈操作： Datatype Pop(s，e) /*若栈非空,删除栈顶元素，用e返回其值*/ seqstack *s;datatype e; { if (empty(s)) { printf(underflow);return NULL; /*下溢*/ } else { s-top--; e= s-data[s-top]； return(e); } } ;取栈顶操作： Datatype GetTop(s) /*取顺序栈s的栈顶*/ seqstack *s; { if (empty(s)) { printf(stack is empty);/*空栈*/ return null; } else return(s-data[--s-top]); } ;多栈共享空间 ;共享空间存储结构的定义： typedef datatype int; /*栈元素的数据类型*/ #define maxsize 64 /* 栈的最大容量*/ typedef struct { datatype data[maxsize]; int top1,top2; }dstack; 初始化操作： InitDstack（dstack *s） { s-top1=0; s-top2=maxsize-1； };进栈操作： PushDstack（dstack*s，char ch，datatype x） {/*把数据元素x压入栈s的左栈或右栈*/ if （s-top2 - s-top1==1） return 0；/*栈已满*/ if（ch==’s1’） { s-data[s-top1]=x; s-top1= s-top1+1; return 1; }/*进栈s1*/ if（ch==’s2’） { s-data[s-top2]=x; s-top2= s-top2-1; return 1; }/*进栈s2*/ };出栈操作： popdstack(dstack *s,char ch) {/*从栈S1或S2取出栈顶元素并返回其值*/ if (char=’s1’) { if(s-top1==0) return null;/*栈s1已空*/ else { s-top1= s-top1-1； return（s-data[s-top1]）; } }/*s1出栈*/;if(char=??s2’) { if(s-top2maxsize-1) return null;/*栈s2已空*/ else { s-top2= s-top2+1; return （s-data[s-top2]）; } }/*s2出栈*/ } ;栈的链式存储结构;进栈操作： Linkstack pushlinkstack(top,w)