数据结构之栈

---

前言

今天这篇文章继续介绍数据结构中的线性表，今天的主角是——栈。
听到栈这个名词，想必大家会想起来之前所讲的操作系统的内存区域划分中的栈，但是要注意今天要讲到的栈和操作系统中的栈是两个概念（毕竟是两个学科的），可不能傻傻分不清哦。

一、栈

数据结构中的栈，是一种特殊的线性表，它只允许在栈的一端进行数据的插入和删除操作，进行插入和删除操作的一端称为栈顶，另一端称为栈底。
因为栈的这个特性，所以栈中的元素遵循后进先出（LIFO）原则。

对栈的操作有以下两种：
压栈：向栈中插入元素（也叫入栈、进栈），在栈顶插入
出栈：删除栈中的元素，在栈顶删除

二、栈应该如何实现

1.顺序表or链表

我们根据之前的知识可以知道要实现栈可以使用数组或者链表，但是究竟哪个更好呢？还是得综合分析一下它们基于栈的特性哪个更有优势。

因为栈的插入和删除都是在栈顶，正好符合顺序表尾删和尾插效率高这一特性，同时也结合顺序表的其他优点，对比可以看出使用顺序表更优。所以我们就用数组结构来实现栈。

2.静态or动态

让我们先看看，静态栈的定义：

#define N 10
typedef int StackNodeType;
typedef struct Stack
{
	StackNodeType a[N];//栈存储数据的数组
	int top;//栈顶的下标
}Stack;
1
2
3
4
5
6
7

在实际应用中我们往往无法预料究竟会有多少个数据需要被处理（即，不确定N定义为多少合适，定义多了，会浪费空间；定义少了，又可能放不下数据），所以动态的栈更好，因此我们本次实现的是动态的栈。

三、栈的实现

1.栈的声明

typedef int StackNodeType;
typedef struct Stack//栈的定义
{
	StackNodeType* s;//栈存储数据所用的数组
	int top;//栈顶
	int capacity;//容量
}Stack;
1
2
3
4
5
6
7

2.接口（声明）

//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);
//入栈
void StackPush(Stack* ps, StackNodeType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
StackNodeType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测栈是否为空（如果为空返回1，如果不为空返回0）
bool StackEmpty(Stack* ps);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.接口的实现

初始化栈

void StackInit(Stack* ps)
{
	ps->s = NULL;
	ps->top = ps->capacity = 0;//初始化栈顶和容量(按照这个写法，则top是栈顶元素的下一个位置)，如果要改为第二种情况，则应该是ps->top = -1 ；ps->capacity = 0;
}
1
2
3
4
5

为什么说top是栈顶元素的下一个位置呢？

想必通过上面的分析图大家就能够理解了，至于具体实现时，到底使用哪种情况，大家可以根据个人爱好来选择，（注意：不同的情况会对其他接口的实现有一些影响，之后具体位置我也会说明的）本次实现是选择情况2。

销毁栈

void StackDestory(Stack* ps)//使用完栈要将它销毁，否则会产生内存泄漏问题
{
	assert(ps);
	free(ps->s);
	ps->s = NULL;
	ps->capacity = ps->top = 0;//情况1改为ps->capacity = 0 ; ps->top = -1;
}
1
2
3
4
5
6
7

获取栈顶元素

StackNodeType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->s[ps->top-1];//情况1改为return ps->s[ps->top];
}
1
2
3
4
5
6

获取栈中有效元素个数

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5

入栈

void StackPush(Stack* ps, StackNodeType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0) ? 4 : (2 * (ps->capacity));
		StackNodeType* temp = (StackNodeType*)realloc(ps->s, newcapacity*sizeof(StackNodeType));
		if (temp)
		{
			ps->s = temp;
			ps->capacity = newcapacity;
		}
	}
	ps->s[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//判断栈是否为空(栈为空继续出栈就要报错了)
	ps->top--;
}
1
2
3
4
5
6

检测栈是否为空

（如果为空返回true，如果不为空返回false）

bool StackEmpty(Stack* ps)
{
	return ps->top == 0;//如果之前选择情况1，此处相应改为return ps->top == -1;即可。
}
1
2
3
4

注意：使用某些库函数时要记得包含它对应的头文件，我也给大家整理了本次所需要的头文件。

#include                  //printf
#include                //bool
#include                 //realloc
#include                 //assert
1
2
3
4

4.主函数（测试）

测试栈的相应功能，以下是我使用的主函数，大家也可以根据需要进行修改，测试其他的测试用例。

void test()//测试栈
{
	Stack ps;
	StackInit(&ps);//初始化
	StackPush(&ps, 1);//入栈
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	StackPush(&ps, 6);
	StackPop(&ps);//出栈
	StackPop(&ps);
	StackPop(&ps);
	//打印栈中元素（实际上遍历一遍栈中的元素就是出栈，将栈顶元素出栈)
	while (!StackEmpty(&ps))
	{
		printf("%d ", StackTop(&ps));
		StackPop(&ps);
	}
	printf("\n");
	StackDestory(&ps);//销毁栈
}
int main()
{
	test();
	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

总结

以上就是今天要讲的内容，本文介绍了数据结构中的栈，对栈的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路（注释）自行实现栈。
本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！