一、栈 1.1栈的概念及结构： 栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last ln First Out)的原则。 压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈: 栈的删除操作叫做出栈。出数据也在栈顶。 1.2实现栈的两种方式： 数组栈 链式栈 对于链式栈是不建议第一种写法的因为尾删需要找到前一个结点(单链表) 二、栈实现(数组栈) 2.1结构： #include #include #include #include typedef int STDataType; typedef struct Strack { 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); //获取size int STSize(ST* pst); 2.2初始化： 对于初始化有两种写法，可不要小看这两种，对后面的代码每种都有每种的情况所以要分情况写。 2.2.1第一种代码： void STInit(ST* pst) { assert(pst);//判空不然为空就需要传二级指针或者返回值 pst->a = NULL; pst->top = -1; pst->capacity = 0; } 2.2.2流程图： 2.2.3第二种代码： void STInit(ST* pst) { assert(pst);//判空不然为空就需要传二级指针或者返回值 pst->a = NULL; pst->top = 0; pst->capacity = 0; } 2.2.4流程图： 总结：两种的区别就在于top指向哪到底是栈顶元素还是栈顶后一个元素，我们选择第二种写法 2.3：释放内存 void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity =pst->top = 0; } 2.4：入栈 void STPush(ST* pst, STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a [pst->top ] = x; pst->top++; } 对于初始化第一种扩容要判断pst->top+1 == pst->capacity 2.5：出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--;//这里要注意top不能为空 } 2.6：访问栈顶元素 STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1];//当top为空时-1就越界了所以要判空 } 对于初始化第一种写法，返回return pst->a[pst->top ]; 2.7：判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } 2.8：获取元素个数 int STSize(ST* pst) { assert(pst); return pst->top; } 对于初始化第一种获取元素个数要返回return pst->top+1; 二、栈实现完整代码 //Stack.h #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include #include typedef int STDataType; typedef struct Strack { 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); //获取size 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; pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity =pst->top = 0; } void STPush(ST* pst, STDataType x) { if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a [pst->top ] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--;//这里要注意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 TestStack() { ST st; STInit(&st); STPush(&st, 1); STPush(&st, 2); printf("%d ", STTop(&st)); STPop(&st); STPush(&st, 3); STPush(&st, 4); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } STDestroy(&st); } int main() { TestStack(); return 0; } 总结 Ending,今天的栈和队列(上)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。