optrstack.h

按照清华大学的那本数据结构的表达式求值改进

//顺序栈头文件.h 
//栈(stack): 限定仅在表的一端进行插入和删除操作的线性表. 
//           栈又称为后进先出(Last In First Out)的线性表(简称LIFO结构)
//栈顶(top): 允许插入和删除的一端称为栈顶.
//栈底(base):不许插入和删除的一端称为栈底.
//栈的顺序存储表示
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT  10  //存储空间分配增量
typedef struct 
{OPTRElemType *base; //栈底指针,在栈构造之前和销毁之后,base的值为NULL
 OPTRElemType *top;  //栈顶指针
 int stacksize;   //当前已分配的存储空间,以元素为单位
}OPTRSqStack;

Status InitOPTRStack(OPTRSqStack &S)
{//构造一个空栈S
 S.base=(OPTRElemType *)malloc(STACK_INIT_SIZE*sizeof(OPTRElemType));
 if (!S.base) return ERROR;
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
 return OK;
}

Status GetTop(OPTRSqStack S,OPTRElemType &e)
{//若栈S不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
 if (S.top==S.base) return ERROR;
 e=*(S.top-1);
 return OK;
}
OPTRElemType GetTop(OPTRSqStack S)  //函数重载
{//若栈S不空,则返回S的栈顶元素,否则退回操作系统
 if (S.top==S.base) exit(OVERFLOW);
 return *(S.top-1);
}
Status Push(OPTRSqStack &S,OPTRElemType e)
{//插入元素e为新的栈顶元素
 if (S.top-S.base>=S.stacksize)
 {S.base=(OPTRElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(OPTRElemType));
  if (!S.base) return ERROR;
  S.top=S.base+S.stacksize;
  S.stacksize+=STACKINCREMENT;
 }
 *S.top++=e;
 return OK;
}
Status Pop(OPTRSqStack &S,OPTRElemType &e)
{//若栈S不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
 if (S.top==S.base) return ERROR;
 e=*--(S.top);
 return OK;
}