【数据结构】实现栈
大家好,我是苏貝,本篇博客带大家了解栈,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️
目录
- 一 .栈的概念及结构
- 二 .栈的实现
- 栈的结构体
- 初始化
- 销毁
- 栈顶插入
- 栈顶删除
- 显示栈顶元素
- 是否为空
- 栈的大小
- 三. 模块化代码实现
- Stack.h
- Stack.c
- Test.c
- 结果演示
一 .栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
二 .栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些,因为数组在尾上插入数据的代价比较小(数组的尾插、尾删很方便)。所以下面我们用数组来实现
1
栈的结构体
typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int top; // 栈顶 }ST;
上面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈
typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity;//容量 }ST;
2
初始化
因为我们要对ST类型的变量进行初始化,所以实参要传ST类型变量的地址,用一级指针来接收。因为实参(ST类型变量的地址)不可能为NULL,所以对它断言(下面的接口同理)。
注意:我们这里的top指的是栈顶元素的下一个,而非栈顶元素,所以将它初始化为0
void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; pst->top = 0;//指向栈顶元素的下一个 }
3
销毁
注意:在这里我们使用的是动态开辟内存,所以要在销毁时释放掉动态开辟的内存,也就是pst->a指向的那个数组
void STDestroy(ST* pst) { assert(pst); if (pst->a != NULL) { free(pst->a); pst->a = NULL; pst->capacity = 0; pst->top = 0; } }
4
栈顶插入
再插入元素之前我们要先判断是否要增容,因为在初始化时我们将pst->capacity初始化为0,所以在增容时要特别注意将pst->capacity==0的情况。还要注意对realloc的结果进行判断,防止realloc失败返回NULL,又直接将NULL赋值给pst->a,这样就再找不到开辟的数组了。
最后不要忘记pst->top++
void STPush(ST* pst, STDataType x) { assert(pst); //判断是否需要增容 if (pst->top == pst->capacity) { int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity; ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入数据 pst->a[pst->top] = x; pst->top++; }
5
栈顶删除
删除时我们必须保证栈内有元素,所以要对pst->top>0断言,如果top==0,表示栈内已无元素,返回错误信息,下面的显示栈顶元素同理
void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; }
6
显示栈顶元素
STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; }
7
是否为空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }
8
栈的大小
int STSize(ST* pst) { assert(pst); return pst->top; }
三. 模块化代码实现
Stack.h
#include #include #include 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
#include"Stack.h" //初始化 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->capacity = 0; pst->top = 0;//指向栈顶元素的下一个 } //销毁 void STDestroy(ST* pst) { assert(pst); if (pst->a != NULL) { free(pst->a); pst->a = NULL; pst->capacity = 0; pst->top = 0; } } //栈顶插入 void STPush(ST* pst, STDataType x) { assert(pst); //判断是否需要增容 if (pst->top == pst->capacity) { int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity; ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST)); 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(pst->top > 0); pst->top--; } //显示栈顶元素 STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); 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
#include"Stack.h" int main() { ST s; STInit(&s); STPush(&s, 1); STPush(&s, 2); STPush(&s, 3); STPush(&s, 4); STPush(&s, 5); while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } printf("\n"); return 0; }
结果演示
好了,那么本篇博客就到此结束了,如果你觉得本篇博客对你有些帮助,可以给个大大的赞👍吗,感谢看到这里,我们下篇博客见❤️