数据结构（初阶）（五）----栈

栈

栈概念与结构栈的实现头文件`stack.h`实现`stack.c`初始化销毁入栈栈是否为空出栈取栈顶元素获取栈中有效元素个数 测试文件

概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出（先进后出）LIFO（Last In First Out）的原则。

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

栈的底层结构：一般使用数组或者链表，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。

栈的实现 头文件stack.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* arr; int top; //指向栈顶 int capacity; //空间大小 }ST; //初始化 void STInit(ST* ps); //销毁 void STDestory(ST* ps); //入栈 void STPush(ST* ps,STDataType x); //打印 void STPrint(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps); //出栈 void STPop(ST* ps); //取栈顶元素 STDataType STTop(ST* ps); //获取栈中有效数据个数 int STSize(ST* ps); 实现stack.c 初始化 //初始化 void STInit(ST* ps) { ps->arr = NULL; ps->top = ps->capacity = 0; } 销毁 //销毁 void STDestory(ST* ps) { if (ps->arr) free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; } 入栈 //入栈 void STPush(ST* ps, STDataType x) { assert(ps); //判断空间 if (ps->top == ps->capacity) { //增容 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("STPush()::realloc fail\n"); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } ps->arr[ps->top++] = x; } 栈是否为空 //判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } 出栈 //出栈 void STPop(ST* ps) { assert(!STEmpty(ps)); //栈不为空 --ps->top; } 取栈顶元素 //取栈顶元素 STDataType STTop(ST* ps) { assert(!STEmpty(ps)); return ps->arr[ps->top - 1]; } 获取栈中有效元素个数 //获取栈中有效数据个数 int STSize(ST* ps) { assert(ps); return ps->top; } 测试文件 #define _CRT_SECURE_NO_WARNINGS #include"stack.h" void test1() { ST st; //初始化 STInit(&st); //销毁 //STDestory(&st); //入栈 STPush(&st,1); STPush(&st,2); STPush(&st,3); STPush(&st,4); 出栈 //STPop(&st); //STPop(&st); //STPop(&st); //打印 STPrint(&st); 取栈顶元素 //while (!STEmpty(&st)) //{ // int top = STTop(&st); // printf("%d ",top); // STPop(&st); //} //获取栈中有效数据个数 int size = STSize(&st); printf("%d\n", size); } int main() { test1(); return 0; }