sqstack.h

本文件是实现栈结构的头文件

/* 此文件为实现栈的头文件 */
#define STACK_INIT_SIZE 100;  /*存储空间初始分配量*/
#define STACKINCREMENT 10;  /*存储空间分配增量*/
#define MaxStackSize 100
#define OVERFLOW -1
#define ERROR -2
#define OK 1
#define NULL 0
typedef int SStatus;
typedef char SElemType;
typedef struct  {
    SElemType *base;  /*在栈构造之前和销毁之后，base的值为NULL*/
    SElemType *top;    /*栈顶指针*/
    int stacksize; /*当前已分配的存储空间，以元素为单位*/
    }SqStack;


/*基本操作函数原型说明*/
/*Status InitStack(SqStack &S);  构造一个空栈 */
/*Status DestroyStack(SqStack &S); 销毁栈s，s不再存在 */
/*Status ClearStack(SqStack &S); 把s设置为空栈 */
/*Status StackEmpty(SqStack S); 若栈s为空，则返回true，否则返回false */
/*Status StackLength(SqStack S); 返回元素的个数，即栈的长度 */
/*Status GetTop(SqStack S,int &e); 若栈不为空，则用e返回栈顶元素，并返回ok，否则返回error */
/*Status Push(SqStack &S,int e); 插入元素e为新的栈顶元素 */
/*Status Pop(SqStack &S,int &e); 若栈不为空，则删除s色栈顶元素，用e返回其值，并返回ok，否则返回error */
/*Status StackTraverse(SqStack S,int(*visit)()); 从栈底到栈顶依次对栈中的每个元素调用函数visit（），一旦visit（）失败，操作失败 */

/* 基本操作的算法描述 */
SStatus InitStack(SqStack *S)
{
    S->base=(SElemType *)malloc(100 * sizeof(SElemType));
    if(!S->base)exit(OVERFLOW); /* 存储分配失败 */
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}
SStatus GetTop(SqStack *S,SElemType *e)
{
    if(S->top==S->base) return ERROR;
    *e=*(S->top-1);
    return OK;
}
SStatus Push(SqStack *S,SElemType e)
{
    if(S->top-S->base>=S->stacksize)  /* 栈满，追加存储空间 */
    {
        S->base=(SElemType *)realloc(S->base,(S->stacksize+10)*sizeof(SElemType));
        if(!S->base) exit(OVERFLOW);  /* 存储分配失败 */
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
     }
     *S->top++=e;
     return OK;
}
SStatus Pop(SqStack *S,SElemType *e)
{
    if(S->top==S->base) return ERROR;
    *e=*--S->top;
    return OK;
}
SStatus StackEmpty(SqStack *S)
{
    if(S->top==S->base)
    return OK;
    else
    return  NULL;
}