1.栈的概念
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。 栈中的数据元素遵守 后进先出 LIFO 的原则。压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶 。出栈:栈的删除操作叫做出栈。 出数据也在栈顶 。
2.栈的实现
2.1初始化
void STInit(ST* pst) { assert(pst); pst->a = NULL; //pst->top = -1; // top 指向栈顶数据 pst->top = 0; // top 指向栈顶数据的下一个位置 pst->capacity = 0; }
2.2销毁栈
void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; }
2.3入栈
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, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; }
2.4出栈
void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; }
2.5获得栈顶元素
STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; }
2.6获取个数
int STSize(ST* pst) { assert(pst); return pst->top; }
2.7判断是否为空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
3.完整代码
3.1 Stack.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.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);
3.2 Stack.c
#include"Stack.h" void STInit(ST* pst) { assert(pst); pst->a = NULL; //pst->top = -1; // top 指向栈顶数据 pst->top = 0; // top 指向栈顶数据的下一个位置 pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 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, newCapacity * sizeof(STDataType)); 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--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); /*if (pst->top == 0) { return true; } else { return false; }*/ return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; }
文章来源地址https://www.toymoban.com/news/detail-519454.html
文章来源:https://www.toymoban.com/news/detail-519454.html
到了这里,关于栈的实现(使用数组)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!