前言
顺序存储(数组)(含详细图解)：（创建，初始化，入栈，出栈，获取栈中数据个数，获取栈顶数据，注销栈）
栈
一.栈的基本概念
1.1栈的基本概念
栈，也被称为堆栈，是一种特殊的线性表，其特点是只允许在一端（称为栈顶Top）进行插入和删除操作，而另一端（称为栈底Bottom）则是固定的，不允许进行插入和删除。这一特性使得栈具有"后进先出"（LIFO, Last In First Out）的操作原则，也就是说最后一个进入栈的元素会被首先删除。
栈的基本操作有两种：进栈（或压栈）和出栈（或退栈）。进栈是将新元素放到栈顶元素的上面，使之成为新的栈顶元素；而出栈则是将栈顶元素删除，使其相邻的元素成为新的栈顶元素。
1.2基本图
线性表和栈都是数据结构的种类，它们之间存在着一定的关联性。线性表是一种数据存储结构，它是一组元素的有限序列，这些元素在逻辑上是线性排列的。而栈则是一种受限的线性表，它只允许在表的一端（称为栈顶Top）进行插入和删除操作，另一端（称为栈底Bottom）则是固定的，不允许进行插入和删除。
尽管栈是一种特殊的线性表，但它们之间存在一些明显的区别。首先，线性表的插入和删除操作可以在任意位置进行(数组)，这不会改变元素之间的相对位置；而栈的插入和删除操作只能在栈顶进行，这会改变栈中元素的相对位置。其次，线性表支持全序操作，即可以通过比较元素的大小来确定其相对位置；而栈则不支持全序操作，因为栈的元素进出顺序是按照"后进先出"的原则进行的。
二.构建一个结构体
2.1创建结构体代码
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
2.2创建结构体图解
三.栈初始化
3.1初始化代码
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
3.2栈初始化图解
四. 入栈
4.1入栈代码
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
4.2入栈图解1
4.2入栈细节图解2
五.出栈
5.1出栈代码
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断是否非空
ps->top--;
}
5.2出栈细节图解
六.获取栈内的个数
6.1获取栈内个数代码
//获取数据个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
6.2栈内个数图解
七.获取栈顶数据
7.1获取栈顶数据代码
//获取栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
7.2获取栈顶数据图解
八.注销栈
8.1注销栈代码
//注销栈
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
8.2注销栈图解
九.检查栈是否为空
9.1检查栈是否为空代码
//返回1是空，返回0是非空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
9.2检查栈是否为空图解
十.全部代码
10.1全部代码
#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
//初始化
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//注销栈
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断是否非空
ps->top--;
}
//获取栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判断是否非空
return ps->a[ps->top - 1];
}
//获取数据个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//返回1是空，返回0是非空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
void PrintfStack(ST* ps)
{
for (int i = 0; i < ps->top; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
TestStack()
{
ST st;//创建结构体
StackInit(&st);//初始化
StackPush(&st, 3);//插入数据
StackPush(&st, 8);
StackPush(&st, 9);
StackPush(&st, 11);
StackPush(&st, 34);
StackPush(&st, 67);
printf("堆中的数据为：\n");
PrintfStack(&st);
printf("\n");
printf("栈顶的数据为:%d \n", StackTop(&st));
printf("\n");
printf("出栈2次,现在的堆顶数据为：");
StackPop(&st);
StackPop(&st);
printf("%d \n", StackTop(&st));
printf("\n");
printf("堆中的数据为：\n");
PrintfStack(&st);
printf("\n");
printf("现在堆中的元素个数：%d \n", StackSize(&st));
printf("\n");
printf("全部出栈：");
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
printf("\n");
printf("现在堆中的元素个数：%d \n", StackSize(&st));
//注销栈
StackDestroy(&st);
}
int main()
{
TestStack();
return 0;
}
10.2运行结果
以上就是本期内容，欢迎参考指正，如有不懂，欢迎评论或私信出下期！！！