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

目录 

🚗一.栈的概念及结构

🚒二.栈的基本操作 

🍗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;
}