引言
数据结构之路经过链表后，就来到了栈（Stack）
栈的概念与结构
栈： 一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素 操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守 后进先出 LIFO （ Last In First Out ）的原则。
压栈： 栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
出栈： 栈的删除操作叫做出栈。 出数据也在栈顶 。
栈的实现
栈的实现 一般可以使用 数组或者链表实现 ，相对而言 数组的结构实现更优 一些。因为数组在尾上插入数据的代价比较小。
定义
这里，当前元素个数用栈顶top来表示，是栈独有的表示方法
初始化
栈的初始化，top可以为0或-1，top为0，则指向栈顶元素的下一个位置，top为-1，则指向栈顶元素的位置。这里选用top为0，因为后面写的适合方便理解
销毁
栈的销毁和顺序表一样，直接释放数组空间即可
压栈
压栈前，先判断是否需要扩容，再将元素压栈。因为这里只有压栈函数需要判断扩容，所以就不用专门再写一个扩容函数
这里realloc函数在pst为NULL时，充当malloc的作用，所以既可以为初始栈开辟空间，又可以扩容
检测栈是否为空
专门写一个函数判断，增强复用性和可读性 。如果top为0，则栈为空，返回真；反之，返回假
出栈
出栈前，先assert断言判断，栈是否为空，因为top不能减到负数
获取栈顶元素
同样，先判断栈是否为空，再返回栈顶元素。因为这里top指向的是栈顶元素的下一位，所以下标访问时top要减一
检测栈中有效元素个数
这里很多函数实现都很简单，有些操作直接外部对结构体都可以直接实现，但最后还是写成函数封装，因为top的含义有多重，防止别人使用时误解，导致使用错误
元素访问
栈中元素访问（打印），不是用函数实现。因为它的特殊结构，决定了它的元素不能从任意位置访问 ，必须符合后进先出原则才可以。所以，我们通常用循环的方式进行访问，同时每访问一个元素，就将它弹出栈，在进行下一个元素的访问。
以及变式
有人可能会疑惑，将元素访问以后就弹出栈，不进行其他操作吗？其实，在实际生产中，栈也是这样实现特定的需求的。
这样我们就实现了栈的增删等功能
源代码
stack.h
#pragma once #include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //初始化 void STInit(ST* pst); //销毁 void STDestroy(ST* pst); //压栈 void STPush(ST* pst, STDataType x); //出栈 void STPop(ST* pst); //获取栈顶元素 STDataType STTop(ST* pst); //检测栈是否为空 bool STEmpty(ST* pst); //检测栈中有效元素个数 int STSize(ST* pst);
stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"stack.h" void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//top指向栈顶元素的下一个位置 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->top = pst->capacity = 0; } void STPush(ST* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top++] = x; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"stack.h" void TestStack1() { ST st; //初始化 STInit(&st); //压栈 STPush(&st, 1); STPush(&st, 2); printf("%d\n", STTop(&st)); STPop(&st); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); //打印 while (!STEmpty(&st)) { printf("%d\n", STTop(&st)); STPop(&st); } //销毁 STDestroy(&st); } int main() { TestStack1(); return 0; }
