【数据结构】栈---C语言版（详解！！！）

🐸一、栈的概念及结构

🍄1、栈的概念定义

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

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

🍄2、动图演示

🌲入栈

🌲出栈

🌲整体过程

🐸二、栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

🐸三、数组结构栈详解

🍎创建栈的结构

🥰这里先创建三个文件：
1️⃣：Stack.h文件，用于函数的声明
2️⃣：Stack.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将栈作为一个项目来进行编写，方便我们的学习与观察。

⭕接口1：定义结构体（ST）

🥰请看代码与注释👇

//自定义类型
typedef int STDataType;
//创建栈的结构
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
1
2
3
4
5
6
7
8
9

⭕接口2：初始化（STInit）

🥰请看代码与注释👇

//初始化
void STInit(ST* pst)
{
	//断言传入指针不为NULL
	assert(pst);

	pst->a = NULL;

	pst->top = -1;  //top指向栈顶数据
	pst->top = 0;   //top 指向栈顶数据的下一个位置

	pst->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

⭕接口3：销毁（STDestroy）

🥰请看代码与注释👇

//销毁
void STDestroy(ST* pst)
{
	//断言传入指针不为NULL
	assert(pst);
	//释放
	free(pst->a);

	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
1
2
3
4
5
6
7
8
9
10
11

⭕接口4：入栈（STPush）

🥰请看代码与注释👇

//入栈
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* temp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = temp;
		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
18
19
20

⭕接口5：出栈（STPop）

🥰请看代码与注释👇

//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	pst->top--;
}
1
2
3
4
5
6
7
8

⭕接口6：取栈顶数据（STTop）

🥰请看代码与注释👇

//取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->a[pst->top - 1];
}
1
2
3
4
5
6
7
8

⭕接口7：判空（STEmpty）

🥰请看代码与注释👇

//判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}
1
2
3
4
5
6
7

⭕接口8：获取栈的大小（STSize）

🥰请看代码与注释👇

//获取栈的大小
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
1
2
3
4
5
6
7

🐸四、完整代码

🥝Stack.h

#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
24
25
26
27
28
29

🥝Stack.c

#include"Stack.h"

//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;

	pst->top = -1;  //top指向栈顶数据
	pst->top = 0;   //top 指向栈顶数据的下一个位置

	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->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* temp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = temp;
		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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

🥝Test.c

#include"Stack.h"

//入栈测试

void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}

//测试
void TestStack2()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPop(&st);

	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}

int main()
{
	//TestStack1();
	//TestStack2();

	return 0;
}
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

🥰这期内容相对比较简单，希望烙铁们可以理解消化哦！

总结🥰
以上就是 【数据结构】栈—C语言版 的全部内容啦🥳🥳🥳🥳
本文章所在【数据结构与算法】专栏，感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远，也很暗，但是不要怕，不怕的人面前才有路。💕💕💕
小的会继续学习，继续努力带来更好的作品😊😊😊
创作写文不易，还多请各位大佬uu们多多支持哦🥰🥰🥰