第四章栈和队列-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)
显示全部