数据结构--栈

什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。后进先出的意思是，后进入的数据在出栈的时候最先出来就如下图所示
在这里插入图片描述
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
这里我们用数组来实现栈的创建

栈的创建

首先我们来画图看看
在这里插入图片描述
这就是我们要创建的栈的样式，首先我们要创建一个结构体来维护栈
为了方便，我们把结构体，还有数据类型重定义一下

typedef int data_type;
typedef struct stack stack;

这是我们的结构体

struct stack
{data_type* arr;int capactiy;//容量int top;//栈顶
};

有了以上的准备，我们下面要进行栈的初始化

栈的初始化

void init_stack(stack* pst)
{pst->arr = NULL;pst->top = 0;//top等于0就代表top == capactiypst->capactiy = 0;
}

这里就是常见的初始化，首先把我们的数组给初始化为空
这里的top初始化就要注意了，如果我们把top置为0，那么就代表我们的数组里面放入了数据，如下图所示
在这里插入图片描述
另一个就是把top初始化为-1，如下图所示

把top设置为0，就代表top和数据存放的个数一样，top就等于实际有效数据，如果设置成-1，就代表实际有效数据是top+1，这个会影响后面判断栈空间是否满了。

申请空间，入栈

下面是代码

void creative_space(stack* pst,data_type x)
{assert(pst);if (pst->top == pst->capactiy){int newcapcity = pst->capactiy == 0 ? 4 : 2 * pst->capactiy;data_type* temp_space = (data_type*)realloc(pst->arr,sizeof(data_type) * newcapcity);if (temp_space == NULL){perror("temp_space_fail");exit(1);}pst->arr = temp_space;pst->capactiy = newcapcity;}pst->arr[pst->top] = x;pst->top++;
}

这里我们首先要判断，传过来的栈有没有初始化，是否是合法的然后判断如果top等于capacity的化就代表空间满了需要扩容，这里使用了realloc来扩容

int newcapcity = pst->capactiy == 0 ? 4 : 2 * pst->capactiy;

这段代码我们设计的非常巧妙，如果是首次创建栈capacity初始化是0，0乘以任何数都是0，所以我们就需要给他赋一个初始值，用来扩容这里给了一个4，然后就是申请空间了，如果空间不够就以当前空间的二倍来进行扩容，扩容完成之后就是把数据放入栈，top自己++了

拿出栈顶数据

下面是代码

//拿出栈顶数据
data_type get_top_data(stack* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top-1];
}

我们在拿数据的时候也要判断当前栈是不是为空的，并且top是要大于0的，里面是必须要有数据可供拿出的，最后就返回数组下标，就成功拿出来了

删除栈顶数据

下面是代码

//删除栈顶数据
void del_top_data(stack* pst)
{assert(pst && pst->top>0);pst->top = pst->top - 1;
}

删除很简单，我们只需要把top的有效位向后移动一位，就代表删除了，同时也要断言一下栈必须存在，并且栈区里面要有数据才能进行删除。

判空

bool st_empty(stack* pst)
{assert(pst);if (pst->top == 0){return true;}else{return false;}
}

同样，这里的判空就是利用top来判断的，返回的类型是布尔类型

获取栈内存放数据的个数

int get_number(stack* pst)
{assert(pst);return pst->top;
}

源码

stack.c

# include"head.h"
void init_stack(stack* pst)
{pst->arr = NULL;pst->top = 0;//top等于0就代表top == capactiypst->capactiy = 0;
}
//删除
void del_stack(stack* pst)
{ assert(pst);free(pst->arr);pst->arr = NULL;pst->top = 0;pst->capactiy = 0;}
//申请空间,入栈
void creative_space(stack* pst,data_type x)
{assert(pst);if (pst->top == pst->capactiy){int newcapcity = pst->capactiy == 0 ? 4 : 2 * pst->capactiy;data_type* temp_space = (data_type*)realloc(pst->arr,sizeof(data_type) * newcapcity);if (temp_space == NULL){perror("temp_space_fail");exit(1);}pst->arr = temp_space;pst->capactiy = newcapcity;}pst->arr[pst->top] = x;pst->top++;
}
void print_stack(stack* pst)
{assert(pst);assert(pst->top > 0);int i = pst->top;i--;while (i >= 0){printf("%d",pst->arr[i]);i--;}
}
//拿出栈顶数据
data_type get_top_data(stack* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top-1];
}
//删除栈顶数据
void del_top_data(stack* pst)
{assert(pst && pst->top>0);pst->top = pst->top - 1;
}
//判空
bool st_empty(stack* pst)
{assert(pst);if (pst->top == 0){return true;}else{return false;}
}
int get_number(stack* pst)
{assert(pst);return pst->top;
}

test.c

# include"head.h"
void test()
{stack st;init_stack(&st);creative_space(&st, 1);creative_space(&st, 2);creative_space(&st, 3);creative_space(&st, 4);print_stack(&st);data_type b = get_top_data(&st);printf("\n%d",b);int a = get_number(&st);printf("\n%d\n", a);del_top_data(&st);print_stack(&st);int c = get_top_data(&st);printf("\n%d", c);bool n =  st_empty(&st);del_stack(&st);
}
int main()
{test();return 0;
}

stack.h

#pragma once
# include<stdio.h>
# include<stdlib.h>
# include<assert.h>
# include<stdbool.h>
typedef int data_type;
struct stack
{data_type* arr;int capactiy;int top;
};
typedef struct stack stack;void init_stack(stack* pst);
//初始化栈
void creative_space(stack* pst,data_type x);
//申请空间
data_type get_top_data(stack* pst);
//拿出栈顶数据
void print_stack(stack* pst);
//打印数据
void del_top_data(stack* pst);
//栈空没有
bool st_empty(stack* pst);
//获取数据个数
int get_number(stack* pst);