[C++知识库]c语言顺序栈初识（话痨版）

PS：注释会比较话痨，因为我是边学边记录整理的qwq

静态/简单 顺序栈

#include <stdio.h>
#include <stdlib.h> 

typedef struct{
   ElemType *elem; //代表所有可能的数据类型，如没有特殊说明，一般默认为int型
   int top; //栈顶位标，若从0开始，我理解为S.top指向S.elem[]栈顶数据的下一个位置
   int size; //存储容量
   int increment; //扩容时增加的存储容量
}SqStack;

//顺序栈的初始化

Status InitStack_Sq(Sqstack &S,int size,int inc){
  S.elem=(ElemType*)malloc(size*sizeof(ElemType)); //分配内存空间,size*sizeof(ElemType)表
                                               //示分配size个ElemType这么大的连续空间内存

  if(NULL==S.elem)return OVERFLOW; //判断有没有申请到
  S.top=0;          //置S为空栈,还有一种写法是S.top=-1,理解会有点不同，看个人习惯。
  S.size=size;      
  S.increment=inc;
  return OK;
}

//顺序栈的入栈

Status Push_Sq(SqStack &S;ElemType e){
  ElemType *newbase;
  if(S.top>=S.size){
    newbase=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));

//理解-realloc(原内存，变化后的内存大小)
//刚学时的模板，感觉应该可以不用newbase
//直接S.elem=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));

    if(NULL==newbase)return OVERFLOW;
    S.elem=newbase;
    S.size+=S.increment;
  }
  S.elem[S.top++]=e; //入栈且将S.top+1
  return OK;
}


//出栈
//注意函数里的&，我用的时候被坑过，下意识以为是取地址的意思，但实际不是（应该）
//这里的&是C++里的形参符号，在函数内部对形参的操作都等于直接操作原变量
//实际用法-Pop_Sq(S,e); 其他顺序栈函数同

Status Pop_Sq(SqStack &S,ElemType &e){
  if(S.top==0)return ERROR;
  e=S.elem[--S.top];
}

 
//判断栈是否为空

Status StackEmpty_Sq(SqStack S){
  if(S.top==0)return TRUE;
  else return FALSE;
}


//取栈顶元素

Status GetTop_Sq(SqStack &S,ElemType &e){
  if(S.top==0)return ERROR;
  e=S.elem[S.top-1];
}


//销毁栈

Status DestroyStack_Sq(SqStack S){
  free(S.elem);
  S.elem=NULL;
}

动态顺序栈

#include <stdio.h>
#include <stdlib.h>
#define Initsize 10 //定义Initsize=10，顺序栈最大的存储容量
#define Stackincrement 1 //扩容的容量

typede struct{
  ElemType *base; //栈底指针
  ElemType *top;  //栈顶指针
  int size; //栈最大容量
}SqStack;

//顺序栈的初始化
void InitStack(SqStack &S){ 
  S.base=(ElemType*)malloc(Initsize*sizeof(ElemType));
  if(NULL=S.base)return OVERFLOW; //判断有没有申请到
  S.size=Initsize;
  S.top=S.base; //栈底和栈顶指向同一位置
}

//顺序栈的入栈
Status Push_sq(SqStack &S,ElemType e){
  if(S.top-S.base>=S.size){ //当两个指针指向同一个数组时，指针相减得到的是两个地址之间元素的
    S.base=(ElemType*)realloc(S.base,(Initsize+Stackincrement)*sizeof(ElemType); //个数
    if(NULL==S.top)return OVERFLOW;
    S.top=S.base+S.size;   //因为realloc的实现有两种情况，一种是在原来的内存的基础上还能
    S.size+=Stackincrement;   //扩容获得一块比之前更大的连续内存，另一种情况是没有足够的
  }                           //空闲内存，只能另找一块内存，把原来内存的数据复制过去，这
   *S.top++=e;                //种情况的top指针就需要改变，故S.top=S.base+S.size不可省略
   return OK;
}

//出栈
Status Pop_Sq(SqStack &S,ElemType &e){
  if(S.top==S.base)return ERROR; //判空
  e=*--S.top;  //可以理解为 e=S.top[--i]
}

//取栈顶元素
Status GetTop_Sq(SqStack &S,ElemType &e){
  if(S.top==S.base)return ERROR;
  e=*(S.top-1);
}

//销毁栈
Status DestroyStack_Sq(SqStack S){
  free(S);
  S.top=S.base=NULL;
}