【数据结构与算法】栈的实现（附源码）
目录
一.栈的概念和结构
二.接口实现
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 是一样的，但注意：
<1> 如果初始化成0，那么这个 top 就指的是栈顶的下一个位置；
<2> 如果初始化成-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 <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define MR_CAP 5
typedef 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;
}🐲👻关于栈的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖
🥰🤩希望小伙伴们可以多多支持博主哦。😍😃
😁😄谢谢你的阅读。😼😸
