【数据结构】栈篇

1. 栈

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

后进先出(Last In First Out)

上图展示了栈的入栈与出栈，只有一端开口是栈的特点。

2. 栈的实现

要实现栈其实很简单，可以说栈就是功能缺失的顺序表。另外栈也分为数组栈和链栈。

链栈和数组栈也没什么特别的优劣之分，不过如果你要实现单链表的链栈，就要让链表的头为栈顶，这样插入数据的时候就不用找尾了。

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。下面我们来实现数组栈。

2.1 准备工作

为了以后用这个栈来存储各种类型的数据，所以我们定义一个标识符Datatype。
为了定位栈顶还需要一个top变量来指向栈的顶部。以及记录当前开了多少空间的capacity。

#define Datatype int //增加代码的拓展性
typedef struct stack
{
	Datatype* a;
	int top;
	int capacity;
}stack;
1
2
3
4
5
6
7

2.2 栈的初始化

在初始化中可以先malloc一些空间，不过这里我就直接初始化为NULL了，后面插入时在扩容。
关于top
如果你初始化为-1代表的意思就是栈顶元素，如果你初始化为0代表的意思就是栈顶元素的下一个元素。
无论你初始化哪个都是可以的，只是后续的实现代码有些许不同。这里我选的就是初始化为0

void InitStack(stack* ps)
{
	ps->a = NULL;//可以初始时就开辟空间，不过我选择了初始不开空间的写法
	ps->top = 0;//初始为-1或者0都可以，后面的操作根据top的初始值来操作。
	ps->capacity = 0;
}
1
2
3
4
5
6

2.3 入栈

每次入栈都要判断当前的空间是否足够，你也可以像写顺序表时那样把，判断写成一个函数，不过因为栈就只有一个插入函数，就显的没什么必要了。
扩容时要注意，因为初始化时的capacity为0不能直接X2扩容，要判断一下。
另外可能会有人有疑问，realloc不是用来扩容的吗，还可以当malloc用吗？
可以的，当没有初始空间时，realloc就可以当malloc使用。

//栈的插入/入栈
void PushStack(stack* ps,Datatype x)
{
	assert(ps);
	//判断空间是否充足
	if (ps->top == ps->capacity)
	{
		//空间不够，扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//防止0乘任何数都为0的情况
		Datatype* tmp = (stack*)realloc(ps->a,sizeof(stack) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top += 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.4 出栈

删除是唯一要注意的就是，如果栈为空可不能再删除了。

//栈的删除/出栈
void PopStack(stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈为空时不能删除
	ps->top -= 1;
}
1
2
3
4
5
6
7

2.5 判断栈是否为空

注意为空返回真，不为空返回假。
这里只要判断ps->top是否为0就可以了。

bool EmptyStack(stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5

2.6 取出栈顶元素

因为ps->top表示栈顶的下一个元素，所以返回ps->a[ps->top - 1]就可以了

//取出栈顶元素
Datatype TopStack(stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7

2.7 获取栈中有效元素个数

不知道大家有没有认为，ps->top很像顺序表的size。这里我们直接返回ps->top就可以代表有效个数了。

//获取栈中有效元素个数
int SizeStack(stack* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

2.8 销毁栈

为了防止内存泄漏，一定要记得释放空间哦~

//销毁栈
void DestoryStack(stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

1
2
3
4
5
6
7
8
9
10

效果图

3.代码整合

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

#define Datatype int //增加代码的拓展性
typedef struct stack
{
	Datatype* a;
	int top;
	int capacity;
}stack;

//栈的初始化
void InitStack(stack* ps);

//栈的插入/入栈
void PushStack(stack* ps, Datatype x);

//栈的删除/出栈
void PopStack(stack* ps);

//判断栈是否为空
bool EmptyStack(stack* ps);

//取出栈顶元素
Datatype TopStack(stack* ps);

//获取栈中有效元素个数
int SizeStack(stack* ps);

//销毁栈
void DestoryStack(stack* ps);

//stack.c
#include "stack.h"

//栈的初始化
void InitStack(stack* ps)
{
	ps->a = NULL;//可以初始时就开辟空间，不过我选择了初始不开空间的写法
	ps->top = 0;//初始为-1或者0都可以，后面的操作根据top的初始值来操作。
	ps->capacity = 0;
}

//栈的插入/入栈
void PushStack(stack* ps,Datatype x)
{
	assert(ps);
	//判断空间是否充足
	if (ps->top == ps->capacity)
	{
		//空间不够，扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//防止0乘任何数都为0的情况
		Datatype* tmp = (stack*)realloc(ps->a,sizeof(stack) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top += 1;
}


//栈的删除/出栈
void PopStack(stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//栈为空时不能删除
	ps->top -= 1;
}

//判断栈是否为空
bool EmptyStack(stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//取出栈顶元素
Datatype TopStack(stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int SizeStack(stack* ps)
{
	assert(ps);
	return ps->top;
}

//销毁栈
void DestoryStack(stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//test.c
#include "stack.h"

void test1()
{
	/*stack s;
	InitStack(&s);
	PushStack(&s, 1);
	PushStack(&s, 1);
	PushStack(&s, 2);
	PushStack(&s, 2);
	PushStack(&s, 3);
	PushStack(&s, 3);
	PushStack(&s, 4);
	PushStack(&s, 4);

	while (!EmptyStack(&s))
	{
		printf("%d ", TopStack(&s));
		PopStack(&s);
	}
	DestoryStack(&s);*/
}

int main()
{
	test1();
	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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

完