你内心肯定有有着某种火焰，能把你和其他人区别开来。                   --库切

目录 

🚗一.栈的概念及结构

🚒二.栈的基本操作 

🍗1.栈的初始化

🥩2.入栈

🍊3.栈顶的元素

🍒4.出栈

🍓5.判断栈是否为空

🍌6.栈中的元素个数

​🌶️7.销毁栈

🚙三.栈的全部代码

🍍1.Stack.h：

🥔2.Stack.c：

🍎3.test.c：

🚗一.栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作，进行数据的插入和删除操作的一端称为栈顶。另一端称为栈底。栈中数据元素遵循后进先出LIFO(last in first out)。

栈最基本的两个操作就是压栈和出栈。
1.压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
2.出栈：栈的删除操作叫做出栈，出数据也在栈顶。 
通俗的理解其实就是我们之前学习的尾插和尾删，尾插对应的就是压栈，尾删对应的就是出栈。
但是对于尾插，尾删，我们学习了三种结构：顺序表(数组)，单链表，双链表。所以这里我们选用哪一种结构来实现栈呢？

对于单链表尾插，尾删，我们每次都需要遍历整个数组，来找到尾，再进行操作，时间复杂度是O(N)，所以我们不会使用单链表来实现栈，我们可以选择顺序表(数组)或者双链表来实现。
这里我们选择的是顺序表(数组)。
和之前一样,我们使用结构体来实现:

typedef int STDataType;
typedef struct Stack
{STDataType* a;//动态数组STDataType top;//栈顶int Capacity;//容量
}ST;

🚒二.栈的基本操作 

🍗1.栈的初始化

对于栈的初始化，我们可以先使用malloc动态的给数组开辟几个空间，容量也栈初始化几个。

//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//动态的开辟空间if (ps->a == NULL){perror("malloc\\n");return;}ps->top = 0;ps->Capacity = 4;//初始化容量为4
}

🥩2.入栈

入栈也就是尾插，这是我们之前学过的，这是非常简单的。但是还是有个小细节要注意，在入栈之前，我们需要判断一下，栈内的容量是否满了，满了就要增容。

// 入栈
void StackPush(ST* ps,STDataType x)
{assert(ps);//判断是否满了if (ps->top == ps->Capacity){STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->Capacity * 2);if (temp==NULL){perror("realloc\\n");return;}else{ps->Capacity *= 2;//每次增容尾上一次的二倍ps->a = temp;}	}else{ps->a[ps->top] = x;ps->top++;//栈内入一个数据，top就要往上面走一步}
}

🍊3.栈顶的元素

我们要打印栈顶的元素要怎么打印呢？当入栈已经结束了之后，我们先打印第一个栈顶的元素，然后再出栈一个，继续打印栈顶的元素，以此类推，直到栈为空。

STDataType StackTop(ST* ps) 
{assert(ps);assert(ps->top > 0);//这里要断言一下，如果栈为空，就不能打印了return ps->a[ps->top - 1];
}

🍒4.出栈

出栈也就是我们所说的尾删，数组的尾删只需要把top的位置往前挪一位就行了。

void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}

🍓5.判断栈是否为空

为什么要判断栈为空呢？因为当我们进行出栈的时候，栈内的元素为依次减小，如果减小到0，就不能继续出栈了。

//判断栈是否为空
bool StackEmpty(ST* ps)//这里我们使用bool来判断
{assert(ps);return ps->top == 0;//当ps->top为0的时候，式子成立，即返回真。反之，亦然。
}

我们就先往栈入 1  2  3  4四个数字，再依次出栈出来打印出来看看。

int main()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\\n");return 0;
}

很明显这很符合栈的先入后出的特点。

🍌6.栈中的元素个数

我们入了几个元素，top就是机，直接把top打印出来就是栈元素的个数了。

int StackSize(ST* ps)
{assert(ps);return ps->top;
}

🌶️7.销毁栈

当我们退出程序的时候，把栈给销毁一下。

//销毁栈
void StackDestory(ST* ps)
{free(ps->a);ps->a = NULL;ps->Capacity = 0;ps->top = 0;
}

🚙三.栈的全部代码

🍍1.Stack.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;//动态数组STDataType top;//栈顶int Capacity;//容量
}ST;//初始化栈
void StackInit(ST* ps);//入栈
void StackPush(ST* ps, STDataType x);//出栈
void StackPop(ST* ps);//栈元素的个数
int StackSize(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);//栈顶的元素是多少
STDataType StackTop(ST* ps);//销毁栈
void StackDestory(ST* ps);

🥔2.Stack.c：
 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc\\n");return;}ps->top = 0;ps->Capacity = 4;
}// 入栈
void StackPush(ST* ps,STDataType x)
{assert(ps);//判断是否满了if (ps->top == ps->Capacity){STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->Capacity * 2);if (temp==NULL){perror("realloc\\n");return;}else{ps->Capacity *= 2;ps->a = temp;}	}else{ps->a[ps->top] = x;ps->top++;}
}//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}//栈元素的个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//栈顶的元素是多少
STDataType StackTop(ST* ps) 
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}//销毁栈
void StackDestory(ST* ps)
{free(ps->a);ps->a = NULL;ps->Capacity = 0;ps->top = 0;
}//打印函数
void StackPrint(ST* ps)
{assert(ps);int i = 0;while (i < ps->top){printf("%d", ps->a[i]);i++;}
}

🍎3.test.c：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
ST st;
void Stacktest1()
{StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\\n");
}void Stacktest2()
{StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);printf("栈内元素的个数：\\n");printf( "%d\\n",StackSize(&st));}
int main()
{//Stacktest1();Stacktest2();return 0;
}