初阶数据结构之栈的实现（五）

---

😏专栏导读

👻作者简介：M malloc，致力于成为嵌入式大牛的男人
👻专栏简介：本文收录于 初阶数据结构，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。
👻相关专栏推荐：LeetCode刷题集，C语言每日一题。

---

🤖文章导读

本章我将详细的讲解关于栈的知识点

🙀什么是栈？

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

栈的两种概念：
1、压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
2、出栈：栈的删除操作叫做出栈。出数据也在栈顶

🙀画图描述

如下图所示，就是出栈入栈全过程啦！关于栈有一个特点就是后进先出不要忘记啦！

😳栈的代码实现及其各类讲解

😳栈的初始化代码实现及其讲解

首先我们要清晰栈是如何实现的
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
所以这里我们选择用数组来实现顺序栈！

如图所示：假设用数组实现的话，就像有限制条件的顺序表，尾插就相对的方便一些。

如果用链式栈实现的话，就相对的消耗会更大一些

😳栈的初始化

这里我们采用的是动态开辟版的顺序栈，所以首先我们先定义一个结构体类型

#include
#include
#include
#include
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;
1
2
3
4
5
6
7
8
9
10
11

这是类型的定义。
初始化函数代码如下：

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
1
2
3
4
5
6
7

那么我们为什么要这样初始化呢？为什么我们的top初始化要赋值为0呢？这里就是方便于我们正常的理解啦，因为正常的来说，我们数组的下标一般都是从0开始的！但是如果这样考虑的话，

我们就应该清楚top所处于的位置了，当a1插入数据时，我们的top就应该是在下一个位置了，而不是相对应的位置。

😳栈的销毁代码实现及其讲解

代码如下：

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
1
2
3
4
5
6
7

由于我们用的是顺序栈，它是一块连续的地址，所以我们只需要free掉首结点，它那一块连续的空间都会被销毁，并且我们再把对应的容量和栈顶指向的位置都归回原位就行啦！

😳栈的入栈代码的实现及其讲解

栈的入栈实现其实是有限制条件的，就是要从栈顶入数据，然后还从栈顶出数据，其实就是根据我们的top位置去插入元素，下面我们进入画图讲解！

最初的栈是空的图：

然后我们开始入栈元素，此时的元素是从栈顶开始入栈，此时的数据已经入进去了，我们发现此时的top也向前移动了一个位置，此时也就是当数据成功入栈时，我们的top会自动的进行++

下面是代码实现

在实现代码的过程中，我们发现有一个if然后一大串的看不懂的一堆代码对不对。

这一段的代码主要的作用就是当我们的入栈满了的时候，我们可以进行动态扩容，那么这个realloc的作用是啥呢？我们可以登录cplusplus查看一下，网址时这个噢！这就是cplusplus网站点我就好啦

我们可以发现这里面有两个参数一个是指针，一个是大小，我就直接告诉大家啦，这里的指针是指向我们要扩容的地址处，然后大小是指我们要在这块需要扩容的地方开辟多少大小。

void STPush(ST* pst, STDatatype x)
{
	if (pst->capacity == pst->top)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, newCapacity * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("mallo fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

😳栈的出栈(也称弹栈)的代码实现及其讲解

顺序站的出栈，其实就和顺序表的尾删很像，就直接把栈顶的top–就行啦，但是我们得确定一件事，就是当这个顺序栈是空的时候，我们就应该停止删除了，所以这里我选择用assert直接暴力一点。

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
1
2
3
4
5
6

😳栈的判空函数的代码实现

我们在写一个判空的接口函数吧！根据下图我们可以发现，当top==0时，此时的栈就是空的。

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
1
2
3
4
5

😳栈的栈顶结点的取得

首先我们得确定我们的栈不能是一个空栈，其次我们会发现去栈顶元素其实就是去栈顶结点的位置的数，但是我们得注意了，我们的思维其实时偏向于数组的，所以我们取栈顶数据时，应该让top-1，就跟我们正常思考一样。

STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
1
2
3
4
5
6

😳栈的整体代码的实现

stack.c

#pragma once
#include
#include
#include
#include
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);

STDatatype STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

stack.h

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDatatype x)
{
	if (pst->capacity == pst->top)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, newCapacity * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("mallo fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

---

总结

今天的代码讲解就到这里啦，如果你们觉得还可以的话可以一键三连！！
下一期我们讲的时队列的实现噢！！