深入理解栈和队列（一）：栈

2024-04-19 09:03:25

个人主页：17_Kevin-****博客

专栏：《数据结构》

一、栈的概念

栈（Stack）是一种特殊的线性表，它遵循后进先出（Last-In-First-Out，LIFO）的原则。栈可以被看作是一个只能在一端进行操作的线性表，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底它的基本操作包括入栈（Push）和出栈（Pop）。

栈可以想象成一个垂直放置的木板，上面有一些盘子。栈的特点是最后放入的盘子会被放在最上面，而要取出盘子时，只能从最上面开始取。这就是后进先出的原则，也就是说，最后放入栈的元素会首先被取出。

二、栈的结构

栈的大致结构如上，只能从固定的端口（栈顶）压栈和出栈。

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

三、栈的代码实现

以C语言作为语言基础，数组作为储存结构实现栈的压栈，出栈等操作

为什么使用数组实现栈？

原因如下：

随机访问：数组可以通过索引快速地访问任何元素，而链表需要遍历才能找到指定的元素。在栈的操作中，我们通常只关心栈顶元素，因此数组的随机访问特性可以提供更好的性能。

内存效率：数组在内存中是连续存储的，而链表中的每个节点都需要额外的指针空间。对于栈来说，数组的内存效率更高，因为它不需要额外的指针来维护栈的结构。

常数时间操作：数组的入栈和出栈操作可以在常数时间内完成，因为它们只需要修改栈顶指针。而链表的入栈和出栈操作需要遍历链表，因此时间复杂度为 O(n)。

栈的创建

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

栈的初始化

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

栈的销毁

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

压栈和出栈

压栈

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	// 如果空间不够，扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

我们用数组来实现栈，用指针指向的区域扩容来表示数组，往进存结构体。当 ps->top == ps->capacity 的时候说明数组内的空间满了，不足以进行压栈，所以进行if内的扩容处理。

在数组容量足够的时候直接在对应的top位置上进行赋值，实现压栈，最终用top++来实现数据的同步刷新。

出栈

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

出栈的处理简单粗暴。

我们将 top-- 后其实就无法修改和读取之前top - 1位置的值了，而在压栈的时候他是对top位置的空间直接赋值，所以不用担心之前的该位置存的值是多少。

读取栈顶

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

栈内数据数量

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

四、栈的应用

栈在编程中有很多应用，例如：

函数调用：在函数调用中，栈用于保存函数的参数、局部变量和返回地址。

表达式求值：在表达式求值中，栈用于按照运算符的优先级和结合性对表达式进行求值。

括号匹配：在处理括号嵌套的代码时，栈可以用于检查括号是否匹配。

递归：在递归算法中，栈用于保存函数的调用信息和返回地址。

五、总结

栈是一种重要的数据结构，它遵循后进先出的原则。栈的基本操作包括入栈、出栈、查看栈顶元素和检查栈是否为空。栈可以使用数组或链表来实现，并且在编程中有很多应用。希望这篇博客对你理解栈有所帮助！

码农公寓