栈（使用顺序表构建）

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

1、栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
通俗一点的理解就是，栈就像是一个羽毛球筒一样，先放进去的羽毛球，最后才能拿出来，反而后放进去的可以先拿出来，也就是我们上面提到的LIFO：Last In First Out。

在这里插入图片描述

而栈我们可以通过顺序表来构建，也可以通过链表来构建，本文讲述的是顺序表构建内容。

下面进入正文。

2、栈的数组构建方法

2.1 前言

构建栈的需求有三个文件，包括Stact.c（用来书写逻辑的内容）、Stact.h（用来书写逻辑的声明）、test.c（用来测试我们所书写的代码）。

2.2 正文

我们先将我们的逻辑申明书写完成，这样后面的内容我们就可以按照逻辑声明的顺序一步一步完成。
首先我们需要有一个顺序表如下，在书写的时候我们就直接将它重命名，以便我们后面代码的书写。

typedef struct Stact
{
	int* a;
	int top;
	int capacity;
}ST,*pST;//分别为结构体类型名，和结构体指针

书写完会发现，我们结构体中的数组类型已经被定死了，如果我们以后想要往栈中存储不同类型的数据，需要一个一个在代码中查找 int 然后修改，十分麻烦，不如直接将类型重命名为一个新的名字，之后的代码中如果需要修改，则直接修改重命名的内容即可。

typedef int STDataType;
typedef struct Stact
{
	STDataType* a;
	int top;
	int capacity;
}ST,*pST;//分别为结构体类型名，和结构体指针

在此之后，我们则需要在书写几个函数来执行我们的初始化，压栈，出栈，等操作。
代码如下：

//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);

下面我们对应其顺序一步一步书写

2.2.1 栈的初始化

对于栈的初始化，代码如下：

void STInit(pST pst)
{
	assert(pst);
	pst->a = NULL;

	//让栈顶指向下一个位置
	pst->top = 0;

	//让栈顶指向当前位置
	//pst->top = -1;

	pst->capacity = 0;
}

我们可以看到代码块中书写了两种方法，一种是让栈顶指向下一个位置，一种是让栈顶指向当前位置，两者皆可，本文采用的是令栈顶指向下一个位置的方法。

2.2.2 栈的销毁

对于栈的销毁，代码如下：

void STDestroy(pST pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

2.2.3 压栈

对于数据的压栈，我们在开头就需要判断一下数组的空间是否足够，或者数组空间是否为NULL，如果不足或为NULL，我们需要对其进行空间开辟，使用 realloc 函数进行，其中我们知道本文采用的方法是将 top 指向下一个位置所处的下表，故代码如下：

void STPush(pST pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("STPush:realloc");
			return;
		}
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

2.2.4 出栈

对于出栈，就十分容易了，我们每一次压栈时使用的都是 top 来定位栈顶的位置，这里我们可以直接进行 top-- 操作，此时不用对栈顶的内容改变，下一次入栈时便会直接覆盖此时需要删除的内容。
代码如下

void STPop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

2.2.5 取栈顶数据

取栈顶的数据代码如下：

STDataType STTop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

2.2.6 对栈内数组判断是否为空

判空代码如下：

bool STEmpty(pST pst)
{
	assert(pst);
	return pst->top == 0;
}

2.2.7 栈内数据的数量

查看栈内数据的数量的代码如下：

int STSize(pST pst)
{
	assert(pst);
	return pst->top;
}

3、完整代码展示

Stact.h:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>


typedef int STDataType;

typedef struct Stact
{
	STDataType* a;
	int top;
	int capacity;
}ST,*pST;

//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);

Stact.c:

#include "Stact.h"

//初始化
void STInit(pST pst)
{
	assert(pst);
	pst->a = NULL;

	//让栈顶指向下一个位置
	pst->top = 0;

	//让栈顶指向当前位置
	//pst->top = -1;

	pst->capacity = 0;
}


//顺序表的销毁
void STDestroy(pST pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

//压栈
void STPush(pST pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("STPush:realloc");
			return;
		}
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

//出栈
void STPop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//取栈顶数据
STDataType STTop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

//栈判空
bool STEmpty(pST pst)
{
	assert(pst);
	return pst->top == 0;
}

//栈的大小
int STSize(pST pst)
{
	assert(pst);
	return pst->top;
}

test.c:

#include "Stact.h"

int main()
{
	// 入栈：1 2 3 4
	// 出栈：4 3 2 1  /  2 4 3 1
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);

	printf("%d ", STTop(&s));
	STPop(&s);

	STPush(&s, 3);
	STPush(&s, 4);

	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}

	STDestroy(&s);
}