目录
一.栈的概念和结构
二.接口实现
A.初始化 Stackinit 销毁 Stackdestroy
1.Stackinit
2.Stackdestroy
B.插入 Stackpush 删除 Stackpop
1.Stackpush
2.Stackpop
C.出栈 Stacktop
D. 栈的有效元素 Stacksize 判空 Stackempty
1.Stacksize
2.Stackempty
三.源码
Stack.h
Stack.c
test.c
一.栈的概念和结构
1.一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作;
2.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底;
3.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则;
压栈:向栈中插入数据;
出栈:从栈中取出数据;
图示:
其实用链表和数组都可以实现栈,但栈底就相当于链表的头,数组的第一个元素,栈顶就相当与链表的尾,数组的最后一个元素,当我们进行压栈或是出栈操作时,链表就需要找到尾,所以时间复杂度为O(N),而数组则是O(1),所以这里选择用数组实现栈比较好。
用数组实现的话,就和前面的顺序表类似了。
顺序表
二.接口实现
A.初始化 Stackinit 销毁 Stackdestroy
1.Stackinit
1.这里数组的初始化就和顺序表那里是一样的了,需要用到动态内存管理的函数,如果不懂的话,建议去补一下这一块的知识哦;
2.这个top用来记录实时数据的数量,和顺序表那里的 sz 是一样的,但注意:
如果初始化成0,那么这个 top 就指的是栈顶的下一个位置;
如果初始化成-1,那么这个 top 就指的是栈顶的位置;
3.初始化容量,这由你自己决定。
void Stackinit(Stack* ps){assert(ps);ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);if (ps->arr == NULL){perror("malloc fail");exit(-1);}ps->top = 0; //表示的是栈顶的下一个位置ps->capacity = MR_CAP; //默认容量}
2.Stackdestroy
这个非常简单,直接看代码吧。
void Stackdestroy(Stack* ps){assert(ps);free(ps->arr);ps->arr = NULL;ps->top = 0;ps->capacity = 0;}
B.插入 Stackpush 删除 Stackpop
1.Stackpush
在插入前,我们需要判断容量是否已满,若已满,则需要扩容。
void Stackpush(Stack* ps, STdatatype x){assert(ps);if (ps->top == ps->capacity) //判断是否已满{STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity *= 2;}ps->arr[ps->top] = x;ps->top++; //数据入栈后,实时数据数量加1}
2.Stackpop
删除前要注意栈是否为空,若为空则不能进行删除操作;
删除就是使 top 减1。
void Stackpop(Stack* ps){assert(ps);assert(ps->top); //判断栈是否为空ps->top--; //删除数据}
C.出栈 Stacktop
出栈前需要判断栈是否为空,为空则无数据可出栈;
因为前面初始化的 top 是0,所以栈顶数据的下标是 top-1 ,如果初始化的 top 是-1,那么栈顶数据的下标则是 top 。
STdatatype Stacktop(Stack* ps){assert(ps);assert(ps->top); //判断栈是否为空return ps->arr[ps->top - 1]; //栈顶数据的下标是 top-1}
D. 栈的有效元素 Stacksize 判空 Stackempty
1.Stacksize
1.若初始化的 top 是0,则 top 就是栈的有效元素个数;
2.若初始化的 top 是-1,则 top+1 为栈的有效元素个数。
int Stacksize(Stack* ps){assert(ps);return ps->top;}
2.Stackempty
1.如果 top 是0,则为空,返回 true;
2.如果 top 不是0,则不为空,返回 false 。
bool Stackempty(Stack* ps){assert(ps);return ps->top == 0; //如果 top ==0 ,则这句代码为真,返回 true;反之,返回 false}
三.源码
Stack.h
#include #include #include #include #define MR_CAP 5typedef int STdatatype;typedef struct Stack{STdatatype* arr;int top;int capacity;}Stack;void Stackinit(Stack* ps);void Stackpush(Stack* ps,STdatatype x);void Stackpop(Stack* ps);STdatatype Stacktop(Stack* ps);int Stacksize(Stack* ps);bool Stackempty(Stack* ps);void Stackdestroy(Stack* ps);
Stack.c
#include "Stack.h"void Stackinit(Stack* ps){assert(ps);ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);if (ps->arr == NULL){perror("malloc fail");exit(-1);}ps->top = 0;ps->capacity = MR_CAP;}void Stackpush(Stack* ps, STdatatype x){assert(ps);if (ps->top == ps->capacity){STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity *= 2;}ps->arr[ps->top] = x;ps->top++;}void Stackpop(Stack* ps){assert(ps);assert(ps->top);ps->top--;}STdatatype Stacktop(Stack* ps){assert(ps);assert(ps->top);return ps->arr[ps->top - 1];}int Stacksize(Stack* ps){assert(ps);return ps->top;}bool Stackempty(Stack* ps){assert(ps);return ps->top == 0;}void Stackdestroy(Stack* ps){assert(ps);free(ps->arr);ps->arr = NULL;ps->top = 0;ps->capacity = 0;}
test.c
#include "Stack.h"void testStack(){Stack st;Stackinit(&st);int i = 0;for (i = 1; i <= 8; i++){Stackpush(&st, i);}printf("%d\n ", Stacksize(&st));/*while (!Stackempty(&st)){printf("%d ", Stacktop(&st));Stackpop(&st);}*/printf("\n");Stackdestroy(&st);}int main(){testStack();return 0;}
关于栈的讲解就到这里了,若有错误或是建议欢迎小伙伴们指出。
希望小伙伴们可以多多支持博主哦。
谢谢你的阅读。