数据结构入门 — 栈

本文属于数据结构专栏文章，适合数据结构入门者学习，涵盖数据结构基础的知识和内容体系，文章在介绍数据结构时会配合上动图演示，方便初学者在学习数据结构时理解和学习，了解数据结构系列专栏点击下方链接。

---

• 博客主页：Duck Bro 博客主页

• 系列专栏：数据结构专栏

• 关注博主，后期持续更新系列文章

• 如果有错误请大家批评指出，博主会及时修改

• 感谢大家点赞👍收藏⭐评论✍

---

数据结构入门 — 栈

本文关键字：栈、概念及结构、动图、接口实现

---

一、 栈的概念及结构

1. 栈的概念

栈（Stack）是一种特殊的线性数据结构，它的特点是仅允许在一端进行插入和删除操作。这一端被称为栈顶（Top），另一端称为栈底（Bottom）。栈的操作模式为后进先出（Last In First Out，LIFO），是一种简单的“先进后出”的顺序结构。

栈通常可以用数组或链表实现，常用的操作包括入栈（Push）和出栈（Pop）。入栈操作是将新的元素插入到栈顶，出栈操作是将栈顶的元素删除并返回。此外，栈还有一些其他的操作，如获取栈顶元素（Top）、判断栈是否为空（IsEmpty）等。往栈中插入元素的操作叫做push，从栈中删除元素的操作叫做pop，查看栈顶元素的操作叫做top。

2. 栈的结构

栈结构可以用数组或链表实现

1. 数组实现栈：栈底用数组下标为0的位置，栈顶用数组下标为n-1的位置（n为数组长度）。入栈操作就是将元素插入到数组末尾，出栈操作就是将数组末尾元素删除并返回。由于数组有固定的大小，因此当栈满时就无法再插入元素，这种情况称为栈溢出。

2. 链表实现栈：链表中的每个节点保存一个元素和一个指向下一个节点的指针。栈顶指针指向链表的头部，入栈操作就是将新元素插入到链表头部，出栈操作就是将链表头部元素删除并返回。由于链表的大小能够动态地调整，因此它即使在没有预留额外空间的情况下也能灵活地添加或删除元素。

在实现栈时，还需要考虑一些细节问题，比如空栈的情况，如何判断栈满或栈空等。

二、栈的实现

1. 动态增长栈结构

使用动态增长的结构，top为栈内元素个数、capacity表示栈内的容量

typedef int STDatatype;

typedef struct StackList
{
	STDatatype* a;
	int top;
	int capacity;
}STL;
1
2
3
4
5
6
7
8

2. 初始化栈

初始化先将指针a置为空，top、capacity置为0

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

3. 入栈

这里使用realloc函数的特性，当指针为空时，跟malloc函数的效果相同，入栈即尾插

void STPush(STL* pc, STDatatype x)
{
	assert(pc);
	if (pc->capacity == pc->top)
	{
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		STDatatype* temp = (STDatatype*)realloc(pc->a, sizeof(STDatatype) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pc->a = temp;
		pc->capacity = newcapacity;
		
	}
	pc->a[pc->top] = x;
	pc->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4. 出栈

这里的出栈，即尾删

void STPop(STL* pc)
{
	assert(pc);
	assert(pc->top > 0);

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

5. 获取栈顶元素

top指向栈顶的后一个，获取栈顶元素时要将top减1

STDatatype STTop(STL* pc)
{
	assert(pc);
	assert(pc->top > 0);

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

6. 获取栈中有效元素个数

top中记录了栈内的元素个数，直接返回top即可

int STSize(STL* pc)
{
	assert(pc);

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

7. 检测栈是否为空

如果栈内为空，则top为0就是栈是空的

bool STEmpty(STL* pc)
{
	assert(pc);

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

8. 销毁栈

释放a内的内存。将top\capacity置为0

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

---