一、 栈的顺序存储结构:
#define maxsize 50
typedef struct{
Elemtype *base;
int top;
}sqstack;
二、 顺序栈上的基本操作
1. 建空栈
void initstack(sqstack *s){
s->base=(Elemtype *)malloc(maxsize*sizeof(Elemtype)); if(!s->base) printf(“error!”);
s->top=0;}
2.判空栈
int empty(sqstack *s){
return (s->top==0);}
3.进栈
void push(sqstack *s,Elemtype x){
if(s->top==maxsize) printf(“error!”);
s->base[s->top]=x;
s->top++;}
4.出栈
Status pop(sqstack *s,Elemtype *y){
if(s->top==0) printf(“error!”); --s->top;
y=s->base[s->top];
return y;}
5.取栈顶
Status gettop(sqstack *s,Elemtype *y){ if(s->top==0) printf(“error!”); y=s->base[s->top-1];
return y;}
三、 具体应用
例:检验表达式的左右圆括号是否匹配 算法:
int pair(char *str){
initstack(s);
for(; *str; str++)
switch(*str){
case‟(„: push(s, *str); break; case‟)‟: if(empty(s)) return 0; else {pop(s); break;} }
if(empty(s)) return 1;
rerurn 0;}
一、 栈的顺序存储结构:
#define maxsize 50
typedef struct{
Elemtype *base;
int top;
}sqstack;
二、 顺序栈上的基本操作
1. 建空栈
void initstack(sqstack *s){
s->base=(Elemtype *)malloc(maxsize*sizeof(Elemtype)); if(!s->base) printf(“error!”);
s->top=0;}
2.判空栈
int empty(sqstack *s){
return (s->top==0);}
3.进栈
void push(sqstack *s,Elemtype x){
if(s->top==maxsize) printf(“error!”);
s->base[s->top]=x;
s->top++;}
4.出栈
Status pop(sqstack *s,Elemtype *y){
if(s->top==0) printf(“error!”); --s->top;
y=s->base[s->top];
return y;}
5.取栈顶
Status gettop(sqstack *s,Elemtype *y){ if(s->top==0) printf(“error!”); y=s->base[s->top-1];
return y;}
三、 具体应用
例:检验表达式的左右圆括号是否匹配 算法:
int pair(char *str){
initstack(s);
for(; *str; str++)
switch(*str){
case‟(„: push(s, *str); break; case‟)‟: if(empty(s)) return 0; else {pop(s); break;} }
if(empty(s)) return 1;
rerurn 0;}