栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底栈里的元素遵循后进先出的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
栈顶的位置是变化的，不是在某一个地方，栈顶是插入数据和删除数据的位置
如果我们要实现栈，有两种方法
- 数组栈
使用数组来当作栈，栈底和栈顶的位置没有任何规定，但是我们一般是使用尾部为栈顶，头部为栈底，这样就可以减少数据的移动，空间不够就扩容，
- 链式栈
栈顶和栈底的位置随意，哪边都可以，而我们使用链表一般都是单链表
还要一个栈的出栈的顺序有多种，不会只有一种
下面我就以数组栈来写一个栈
栈的设计
栈的创建和初始化
创建
typedef int TackDataType; typedef struct SLtack { TackDataType* TData; TackDataType Top;//标识栈顶位置 int Capacity; }SLtack;
初始化
void TackInit(SLtack* pst) { assert(pst); pst->TData = NULL; pst->Top = 0;//栈顶元素的下一个 pst->Capacity = 0; }
这里的top的初始化有两种：
1.top 表示的是栈顶元素，我们要初始化为-1，
2.top表示栈顶元素的下一个 我们要初始化为0
原因：
假设我们初始化为0 且top是表示栈顶元素，就像上面这种情况，我们无法判断top为0时，栈是否还有元素，当我们表示top表示栈顶元素的下一个，top为0，栈就没有元素，或者我们top初始化为-1，top为栈顶元素，即使top为0，那栈还是有元素的
栈的释放
//释放 void TackDestroy(SLtack* pst) { assert(pst); free(pst->TData); pst->TData = NULL; pst->Top = 0; pst->Capacity = 0; }
入栈
void TackcapacityAdd(SLtack* pst) { assert(pst); //扩容 pst->Capacity = (pst->Capacity == 0 ? 4 : pst->Capacity * 2); TackDataType* tmp = realloc(pst->TData, sizeof(TackDataType) * pst->Capacity); if (tmp == NULL) { perror("realloc"); return; } pst->TData = tmp; } //插入数据 void TackPushData(SLtack* pst, TackDataType elemest) { assert(pst); //判断容量 if (pst->Capacity == pst->Top) { TackcapacityAdd(pst); printf("扩容成功\n"); } assert(pst->Capacity != pst->Top); pst->TData[pst->Top] = elemest; pst->Top++; }
出栈
//删除数据 void TackPopData(SLtack* pst) { assert(pst); if(pst->Top) pst->Top--; }
栈顶
//找出栈顶 TackDataType* TackTop(SLtack* pst) { assert(pst); return pst->TData + (pst->Top - 1); }
栈是否为空
//判断栈是否为空 bool Empty(SLtack* pst) { assert(pst); return pst->Top == 0; }
栈的长度
//栈的长度 int TackSize(SLtack* pst) { assert(pst); return pst->Top; }
第二种方法
这种是把top初始化为-1
typedef char TackDataType; typedef struct Stack { TackDataType * a; int top; //栈顶元素 int capacity; }Stack; //初始化 void TackInit(Stack *pst) { assert(pst); pst->a = NULL; pst->top = -1; pst->capacity = 0; } // 入栈 void TackPush(Stack *pst, TackDataType elemest) { assert(pst); //判断是否满了 if ((pst->top) +1 == pst->capacity) { pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2); TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity); if (tmp == NULL) { perror("realloc"); return; } pst->a = tmp; } pst->a[++(pst->top)] = elemest; } //出栈 void TackPop(Stack *pst) { assert(pst); if(pst->top != -1) pst->top--; } //长度 int TackSize(Stack *pst) { assert(pst); return (pst->top) + 1; } //是否为空 bool TackEmpty(Stack *pst) { assert(pst); return pst->top == -1; } //栈顶元素 TackDataType TackTop(Stack *pst) { assert(pst); return pst->a[pst->top]; } //释放 void TackDestroy(Stack *pst) { free(pst->a); pst->a = NULL; pst->top = -1; pst ->capacity = 0; }
总结
栈的简单设计就到这里了,如果想要设置链式栈可以动手自己设计,后续会更新相关的代码
