栈的基本实现（更新中）

• 2019 年 12 月 17 日
• 筆記

栈的基本实现（更新中）

参考着严蔚敏的《数据结构（C语言版）》，用自己拿渣的可怜的C语言做了一下午的实现。。。也没能写出来几个。。。就很菜（气哭）。。。

/*-------------------栈的结构体定义---------------------*/  #define STACK_INIT_SIZE 100       // 存储空间初始分配量  #define STACKINCREMENT 10         // 存储空间分配增量    typedef char SElemType; /*SElemType 类型根据实际情况而定，这里假设为int */  typedef struct{      SElemType *top;      SElemType *base;      int stacksize;          /* 栈的最大容量 */  }SqStack;    /*-----------------------------------------------------*/    /*初始化栈，并分配空间*/  Status InitStack(SqStack *S){      //构造一个空栈S      S = (SqStack *)malloc(sizeof(SqStack));      S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));      if(!S->base)exit(OVERFLOW);     //存储分配失败      S->top = S->base;      S->stacksize = STACK_INIT_SIZE;      return OK;  }   // InitStack    /*若栈存在，则销毁它*/  Status DestroyStack(SqStack *S){      free(S);      if(!S)return ERROR;      return OK;  }    /*将栈清空*/  Status ClearStack(SqStack *S){    }    /*若栈为空，返回true,否则返回false*/  Status StackEmpty(SqStack S){    }    /*若栈存在且非空，用e返回S的栈顶元素*/  Status GetTop(SqStack S, SElemType *e){      //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR      if(S.top == S.base)         return ERROR;    //空栈判断      e = S.top - 1;      return OK;  }   //GetTop    Status Push(SqStack *S, SElemType e){      //插入元素e 为新的栈顶元素      if(S->top - S->base >= S->stacksize){   // 栈满，增加存储空间          S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));          if(!S->base)exit(OVERFLOW);         // 内存已满，存储空间分配失败          S->top = S->base + S->stacksize;          S->stacksize += STACKINCREMENT;     // 最大存储空间增长      }      S->top ++;      S->top = e;      return OK;  }    Status Pop(SqStack *S, SElemType *e){      //若栈不空，则删除S的栈顶元素，用e返回其值，变返回oK;否则返回ERROR      if(S->top == S->base)return ERROR;      e = * -- S->top;      return OK;  }   //pop