栈的概念|动态顺序栈的详细解析|静态顺序栈&链式栈的代码参考_鏍圖ehengzfangx

前言

今天我们将学习数据结构中的栈，它是一种特殊的线性表。why——在前面我们学习顺序表、链表它们都属于线性表，它们可以在任意位置进行插入和删除数据；但是今天我们学习栈，它只能在一端进行插入和删除。下面我们就来学习并实现栈吧！

一、栈的概念及结构

1、栈的概念

1) 栈的定义

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

②压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

③出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2)栈的理解

①首先理解栈是一种线性表，逻辑一定相邻物理不一定相邻。

②其次理解栈是一种特殊的线性表：即只允许在一端进行插入和删除，并且还要遵守后进先出、先进后出的原则。

③实例理解——我们生活中就有许多栈这种后进先出的实例，如：弹夹式手枪、网页的前进后退等等。

3)进栈和出栈变化形式

最先进栈的元素，就一定在最后出栈吗？

答案是：不一定，要看具体情况。栈只是对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，可以边进边出，只要保证是栈顶元素出栈即可。

如现在有1、2、3三个整数依次进栈，会有那些出栈次序呢？

• 第一种：1、2、3进，3、2、1出。出栈次序为321。
• 第二种：1进，1出，2进，2出，3进，3出。出栈次序为123。
• 第三种：1进，2进，2出，1出，3进，3出。出栈次序为213。
• 第四种：1进，1出，2进，3进，3出，2出。出栈次序为132。
• 第五种：1进，2进，2出，3进，3出，1出。出栈次序为231。
  
  想一下有没有312的出栈次序呢？——答案是：没有的，因为先3出栈了，说明1和2已经进栈了，这个时候的栈顶元素就是2，那么出栈次序就是321，不可能是312，否则不满足123依次进栈的顺序。

二、栈的实现

1、顺序栈和链式栈

栈是一种顺序表，即可通过顺序存储结构（数组）和链式存储结构（链表）来实现。

使用顺序存储结构，简称为顺序栈。使用链式存储结构，简称为链式栈。

对于栈这种只能在一端进行插入和删除的线性表，顺序栈&链式栈哪一端作为栈顶比较好呢？

①顺序栈：使用顺序存储结构，即使用数组实现。数组的头插头删的时间复杂度为O(N)，尾插尾删的时间复杂度为O(1)。所以我们选择数组尾作为栈顶。



②链式栈：使用链式存储结构，即使用链表实现。链表的种类这么多，我们选择哪一种链表呢——双向链表比单向链表多一个指针域，为了发扬中国人的节省我们选择单向链表。单向链表的头插头删时间复杂度为O(1)，尾插尾删时间复杂度为O(N)。所以我们选择链表的头作为栈顶。（由于链表的头有头指针，而栈顶指针也是必须，为什么将其合二为一呢，这个时候栈顶指针指向链表的头，哨兵位就没有意义了，所以对于链式栈来说，是不需要哨兵位的。）

我们可以通过这两种方式实现栈，但是哪种好一点呢？

答案是：（作者的观点，仅供参考）相对而言顺序栈更好一点。插入和删除顺序栈&链式栈的算法效率是差不多的，这个时候考虑到CPU缓存命中率的情况，顺序栈就比链式栈好一些了。

2、顺序栈的实现

顺序栈使用数组实现，又分为两种结构完成：

①静态的顺序栈：使用定长数组实现，在事先就确定了栈的大小。

②动态的顺序栈：在堆区malloc动态开辟一个数组，栈的空间不够了，就扩容realloc。

③静态栈和动态栈的应用：如果事先就能确定栈的大小，那么选择静态栈。不能事先确定，就选择动态栈。但是实际中往往不能事先预料，所以动态栈的应用更多。

总结：栈的实现有3种——静态的顺序栈、动态的顺序栈、链式栈，作者这里将详细讲解动态的顺序栈实现，静态的顺序栈和链式栈实现仅提供代码参考，因为思想大致相似。

1)动态栈

0X00动态栈的结构定义

解读：
①动态栈由3个部分组成——指针a指向在堆区开辟的数组（即栈的空间）；top表示栈顶位置；capacity表示栈的容量。

②多个数据组成的复杂类型一般使用结构体将其封装起来。

③代码实现：

//重定义栈储存数据类型(优点：①后期一改全改；②见名知意)
typedef int STDataType;

//动态栈的结构（多个类型的复杂结构，定义为结构体）
typedef struct Stack
{
	STDataType* a;//指向开辟的数组
	int top;//栈顶位置
	int capacity;//栈的容量
}ST;
1
2
3
4
5
6
7
8
9
10

0X01动态栈的初始化

解读：
①给动态栈开辟空间：malloc在堆区申请空间；

②初始化栈顶位置和栈的容量；

③top的初始化有两种，那种都是可以的。初始化top = -1，top就是栈顶元素的位置；初始化top = 0，top就是栈顶元素的下一个。图示：

④代码实现：

//动态栈的初始化
void STInit(ST* pst)
{
	//断言pst不为空
	assert(pst);
	//动态开辟一个长度为4的数组
	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	//判断是否开辟成功
	if (NULL == pst->a)
	{
		//开辟失败打印错误信息
		perror("STInit::malloc");
		exit(-1);
	}
	//初始化栈顶位置和容量
	//pst->top = -1;//top是栈顶元素的位置
	pst->top = 0;//top是栈顶元素的下一个

	pst->capacity = 4;//capacity数组的长度——表示栈的容量
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

0X02动态栈的销毁

解读：
①在堆区申请的空间，好的习惯——不用了就自己free还给操作系统，防止内存泄漏。

②free之后将指针置为NULL，因为free不会改变指针的指向，释放之后指针变成了一个经典的野指针。

③释放之后重置栈顶位置top和栈的容量。

④代码实现：

//动态栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);
	//释放动态数组
	free(pst->a);
	//free不会改变指针a的指向，防止野指针生成，置为空
	pst->a = NULL;
	//更新容量和栈顶位置
	pst->top = 0;//top是栈顶元素的下一个
	pst->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

0X03动态栈的出栈

解读：
①动态栈我们是使用数组实现，规定了数组的尾作为栈顶，所以出栈就是数组的尾删。

②注意特殊情况：栈为空时不能再出栈了。

③出栈我们只需改变top即可，图示：


④代码实现：

//动态栈的出栈
void STPop(ST* pst)
{
	assert(pst);
	//断言栈是否为空
	assert(!STEmpty(pst));
	//栈不为空出栈
	pst->top--;//出栈即改变top的位置
}

1
2
3
4
5
6
7
8
9
10

0X04动态栈的进栈

解读：
①每一次进栈前，都判断是否要扩容。

②因为我们top开始初始化是top = 0，所以top是栈顶的下一个位置。我们要注意先插入数据，最后top++。

③图示：


④代码实现：

//动态栈的进栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//1、先判断是否扩容
	if (pst->top == pst->capacity)
	{
		//1、防止扩容失败，先使用一个临时变量保存开辟空间的起始地址
		//2、扩容一般按照倍数扩，这里我们扩2倍
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		//判断是否扩容失败
		if (NULL == tmp)
		{
			perror("STPush::realloc");
			return;
		}
		//开辟成功
		pst->a = tmp;//使栈的数组指针指向这块空间
		pst->capacity *= 2;//更新栈的容量
	}
	//2、数据进栈
	pst->a[pst->top] = x;
	pst->top++;//更新top，(每一次进栈出栈都要更新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

0X05判断是否为空栈

解读：
①因为pos我们初始化为0，所以当pos == 0即为空栈。

②为什么要将其封装成一个模块呢，直接pos == 0判断不可以吗？

答案是：不封装的话，别人也不知道你的top到底指向哪里，可能会用错。所以最好还是将其封装成一个单独的模块，别人直接调用既可以了。

③代码实现：

//判断是否为空栈
bool STEmpty(ST* pst)
{
	assert(pst);
	//是空栈返回真，否则返回假
	return pst->top == 0;
}
1
2
3
4
5
6
7

0X06返回栈顶元素

解读：
①pos指向的是栈顶的下一个，所以要返回栈顶元素，top - 1即可。

②注意不要用自减操作符，因为自减操作符会带来一个副作用就是会改变top自身的值。（作者第一次就这样报错了！总结：top在每一次进栈和出栈才会改变自身。）

③代码实现：

//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	//断言是否为空栈
	assert(!STEmpty(pst));
	//不为空栈，返回栈顶元素
	return pst->a[pst->top - 1];
}
1
2
3
4
5
6
7
8
9

0X07返回栈的元素个数

解读：
①数组的下标是从0开始的，因为top是栈顶元素的下一个，所以top的值即栈的元素个数。

②代码实现：

//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->top;
}
1
2
3
4
5
6
7

0X08动态栈的声明模块总代码

//常用头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//动态栈的结构定义

//重定义栈储存数据类型(优点：①后期一改全改；②见名知意)
typedef int STDataType;

//动态栈的结构（多个类型的复杂结构，定义为结构体）
typedef struct Stack
{
	STDataType* a;//指向开辟的数组
	int top;//栈顶位置
	int capacity;//栈的容量
}ST;

//动态栈的初始化
void STInit(ST* pst);

//动态栈的销毁
void STDestroy(ST* pst);

//动态栈的出栈
void STPop(ST* pst);

//动态栈的进栈
void STPush(ST* pst, STDataType x);

//判断是否为空栈
bool STEmpty(ST* pst);

//返回栈顶元素
STDataType STTop(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
30
31
32
33
34
35
36
37
38
39
40

0X09动态栈的接口实现总代码

#include"Stack.h"

//动态栈的初始化
void STInit(ST* pst)
{
	//断言pst不为空
	assert(pst);
	//动态开辟一个长度为4的数组
	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	//判断是否开辟成功
	if (NULL == pst->a)
	{
		//开辟失败打印错误信息
		perror("STInit::malloc");
		exit(-1);
	}
	//初始化栈顶位置和容量
	//pst->top = -1;//top是栈顶元素的位置
	pst->top = 0;//top是栈顶元素的下一个

	pst->capacity = 4;//capacity数组的长度——表示栈的容量
}

//动态栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);
	//释放动态数组
	free(pst->a);
	//free不会改变指针a的指向，防止野指针生成，置为空
	pst->a = NULL;
	//更新容量和栈顶位置
	pst->top = 0;//top是栈顶元素的下一个
	pst->capacity = 0;
}

//动态栈的出栈
void STPop(ST* pst)
{
	assert(pst);
	//断言栈是否为空
	assert(!STEmpty(pst));
	//栈不为空出栈
	pst->top--;//出栈即改变top的位置
}

//动态栈的进栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//1、先判断是否扩容
	if (pst->top == pst->capacity)
	{
		//1、防止扩容失败，先使用一个临时变量保存开辟空间的起始地址
		//2、扩容一般按照倍数扩，这里我们扩2倍
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		//判断是否扩容失败
		if (NULL == tmp)
		{
			perror("STPush::realloc");
			return;
		}
		//开辟成功
		pst->a = tmp;//使栈的数组指针指向这块空间
		pst->capacity *= 2;//更新栈的容量
	}
	//2、数据进栈
	pst->a[pst->top] = x;
	pst->top++;//更新top，(每一次进栈出栈都要更新top)
}

//判断是否为空栈
bool STEmpty(ST* pst)
{
	assert(pst);
	//是空栈返回真，否则返回假
	return pst->top == 0;
}

//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	//断言是否为空栈
	assert(!STEmpty(pst));
	//不为空栈，返回栈顶元素
	return pst->a[pst->top - 1];
}

//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	assert(!STEmpty(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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

2)静态栈

0X00静态栈声明模块

//常用头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//静态栈的结构定义，实际中并不实用

//宏常量MAXSIZE表示栈的容量（定义为宏常量，后期方便更改）
#define MAXSIZE  4

//重定义栈储存数据类型(优点：①后期一改全改；②见名知意)
typedef int STDataType;

//静态栈的结构（多个类型的复杂结构，定义为结构体）
typedef struct Stack
{
	STDataType a[MAXSIZE];//定长数组——已经决定了栈的容量
	int top;//栈顶指针——指向栈顶元素的位置
}ST;

//静态栈的初始化
void STInit(ST* pst);

//静态栈的出栈
void STPop(ST* pst);

//静态栈的进栈
void STPush(ST* pst, STDataType x);

//判断是否为空栈
bool STEmpty(ST* pst);

//返回栈顶元素
STDataType STTop(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
30
31
32
33
34
35
36
37
38
39

0X01静态栈的接口实现模块

#include"Stack.h"

//静态栈的初始化
void STInit(ST* pst)
{
	assert(pst);
	//初始化一个空栈
	pst->top = -1;//top是栈顶元素的位置
	//pst->top = 0;//top是栈顶元素的下一个
}

//静态栈的出栈
void STPop(ST* pst)
{
	assert(pst);
	//断言是否为一个空栈
	assert(!STEmpty(pst));
	//出栈
	pst->top--;
}

//静态栈的进栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//断言栈是否满
	assert(pst->top != MAXSIZE - 1);
	//进栈
	pst->top++;
	pst->a[pst->top] = x;
}

//判断是否为空栈
bool STEmpty(ST* pst)
{
	assert(pst);
	//是空栈返回真，否则返回假
	return pst->top == -1;
}

//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	//断言栈是否为空
	assert(!STEmpty(pst));
	//不为空返回栈顶元素
	return pst->a[pst->top];
}

//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	//断言栈是否为空
	assert(!STEmpty(pst));
	//不为空返回栈的元素个数
	return pst->top + 1;
	//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

3)链式栈

0X00链式栈的声明模块

//重定义栈储存数据类型(优点：①后期一改全改；②见名知意)
typedef int STDataType;

//链式栈结点的结构（多个类型的复杂结构，定义为结构体）
typedef struct StackNode
{
	STDataType data;//储存数据
	struct StackNode* next;//储存后继结点地址
}STNode;

//链式栈的结构
typedef struct Stack
{
	STNode* top;//栈顶指针——指向栈顶位置
	int size;//保存栈的元素个数
}ST;

//链式栈的初始化
void STInit(ST* pst);

//链式栈的销毁
void STDestroy(ST* pst);

//链式栈的出栈
void STPop(ST* pst);

//链式栈的进栈
void STPush(ST* pst, STDataType x);

//判断是否为空栈
bool STEmpty(ST* pst);

//返回栈顶元素
STDataType STTop(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
30
31
32
33
34
35
36
37

0X01链式栈的接口实现模块

#include"Stack.h"

//链式栈的初始化
void STInit(ST* pst)
{
	assert(pst);
	//空栈的初始化
	pst->top = NULL;
	pst->size = 0;
}

//链式栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);
	//遍历删除
	STNode* cur = pst->top;//栈顶位置
	while (cur)
	{
		STNode* next = cur->next;//保存栈顶的下一个位置
		free(cur);
		cur = next;//迭代
	}
	//防止top成为野指针
	pst->top = NULL;
}

//链式栈的出栈
void STPop(ST* pst)
{
	assert(pst);
	//断言链表不为空
	assert(!STEmpty(pst));
	//不为空，出栈——即链表的头删
	//草图：top   topnext，分析必须要一个临时变量保存栈顶的位置
	STNode* first = pst->top;//保存栈顶位置
	//注意必须修改栈顶位置，再释放
	pst->top = first->next;
	free(first);
	first = NULL;
	//记得出栈更新栈的元素个数
	pst->size--;
}

//链式栈的进栈
void STPush(ST* pst, STDataType x)
{
	//进栈即链表的头插
	assert(pst);
	//创建新节点
	STNode* newnode = (STNode*)malloc(sizeof(STNode));
	//判断是否开辟成功
	if (NULL == newnode)
	{
		perror("STPush::malloc");
		return;
	}
	//malloc不会初始化，记得自己初始化
	newnode->data = x;
	newnode->next = NULL;
	//草图：newnode   top 
	newnode->next = pst->top;
	pst->top = newnode;//不要忘修改栈顶指针
	//更新栈的元素个数
	pst->size++;
}

//判断是否为空栈
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == NULL;
}

//返回栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->top->data;
}

//栈的元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->size;//这就是我们前面将栈的元素个数设为栈成员的好处
}

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
81
82
83
84
85
86
87
88
89

4)栈的测试模块

#include"Stack.h"

//静态栈的测试
int main()
{
	//定义一个栈
	ST st;
	//初始化
	STInit(&st);
	//依次进栈1、2、3、4
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	
	//打印栈的元素个数
	printf("%d\n", STSize(&st));
	//出栈
	while (!STEmpty(&st))
	{
		//打印栈顶元素
		printf("%d ", STTop(&st));
		//迭代
		STPop(&st);
	}
	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

3、总结

①返回栈顶元素和出栈可以结合在一起的，但是为了后期我们C++学习STL我们将其分开写，即接口的功能模仿STL。

②top在出栈和进栈时都要改变。

③栈是固定在一端插入和删除的，所以顺序栈我们选择数组尾作为栈顶——即顺序栈的出栈入栈就是数组的尾删尾插；链式栈我们选择单链表的头结点作为栈顶——即链式栈的出栈入栈就是单链表的头插头删。