数据结构——栈

前言

在计算机科学中，数据结构（data structure）是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。 数据结构研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。它包含三个方面的内容：即数据的逻辑结构、数据的存储结构和数据的操作，只有这三个方面的内容完全相同，才能成为完全相同的数据结构。

数据结构是计算机四大件之一，是与计算机组成原理、操作系统、计算机网络齐名的存在，因此数据结构的重要性不言而喻。

本章将带领大家去了解栈这一重要的数据结构。

概念

栈（stack）的全名叫堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

1.栈的结构

栈是一种特殊的数据结构，它秉承着"先进后出"的原则，也就是当我们使用栈这个数据结构来存储元素时，取出元素和插入元素都是有规则的。栈的规则用通俗的语言来讲就是"吃了吐"，也就是先存储进去的元素要在最后才能出来，而最后放进的元素则可以第一个出来。在C语言中，我们用数组这一数据结构来当成栈的基础数据结构，也就是说我们通过数组来实现栈。我们来看一下具体的代码定义：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

我们还是一句一句进行剖析。

第一句已经老生常谈了，方便日后元素种类的更换。

在我们定义的Stack结构体中，第一个成员变量a就是我们存储元素的数组，第二个成员变量top用于我们来记录栈顶的位置，同时也能表示所存储元素的数量，第三个成员变量则是我们的数组a所能接纳的容量。

2.栈与顺序表

乍一看，我们可以发现，栈的结构体定义与我们顺序表的结构体定义基本上一模一样。实际上，它们确实一样，唯一的不同便是在我们的顺序表中没有top，而是单纯记录元素数量的size。顺序表和栈虽然在结构体的定义上极为相似，但它们的作用是毫不相干的。

在顺序表中，我们可以任意的进行增删查改等操作，无论从哪个位置都是可以的，但在栈中，插入数据我们只能从尾部（也就是栈顶）插入，删除也是只能从栈顶删除，而不能从栈的中间进行插入删除，进行查找也是一样，我们必须把栈顶元素取出来，才能知道下一个元素是什么。因此，栈与顺序表这两个数据结构从结构上来看十分相似，但在功能上却大相径庭，不过值得一提的是，栈与顺序表都是属于线性表的一种。关于栈的奥妙，将来在我们做题时，我们能发现关于栈更多的用处。

3.栈的实现

想要实现一个栈，我们需要有以下的函数接口：

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

因为要修改结构体内部，所以在传参上我们选择传结构体指针。

3.1栈的初始化

关于栈的初始化与顺序表类似，为数组动态开辟一块空间后将容量capacity给到开辟的大小，栈顶top赋值为0，此时栈中还没有元素，是一个空栈。

// 初始化栈 
void StackInit(Stack* ps)
{
	STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (temp == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = 4;
	ps->top = 0;
}

3.2栈的扩容

既然在栈中我们选择的存储方式是数组，那么当数组的空间用完时，就需要扩容了，由于都是对数组进行扩容，因此该代码与顺序表中的扩容代码相同。

（详情见https://mp.csdn.net/mp_blog/creation/editor/140572230）

//扩容
void StackDilatation(Stack* ps)
{
	assert(ps != NULL);
	STDataType* temp = (STDataType*)realloc(ps, sizeof(STDataType) * ps->_capacity * 2);
	if (temp == NULL)
	{
		printf("realloc fail!\n");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = ps->capacity * 2;
}

3.3入栈

对于栈的插入，我们通常称之为"入栈"。具体的代码如下：

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps != NULL);
	if (ps->capacity == ps->top)
	{
		StackDilatation(ps);
	}
	ps->a[ps->top] = data;
	ps->top++;
}

入栈时第一步就是先判断栈是否满了，若满了，则需要进行扩容。然后将元素放到栈顶，将栈顶更新，进行加一即可。

3.4出栈

对于栈的删除，我们通常称之为"出栈"。具体的代码如下：

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps != NULL);
	assert(ps->top > 0);
	ps->top--;
}

关于出栈，我们只需将栈顶减一即可，要注意的是当栈为空是就不能进行出栈操作了哦！

3.5获取栈顶元素

具体代码如下：

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps != NULL);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

当我们需要获得栈顶元素时只需将下标为"top-1"的元素返回即可，需要注意的是要注意栈为空是不可以获取栈顶元素，这会造成数组的越界访问。

3.6获取栈中元素个数

在栈的结构体中，我们定义的top不仅表示着栈顶，也代表着栈中的元素个数。因此只需返回top即可。具体的代码如下;

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps != NULL);
	return ps->top;
}

3.7判断栈是否为空

与获取栈中元素个数同理，我们只需看top是否为0即可。具体的代码实现如下：

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	if (ps->top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

3.8栈的销毁

当我们用完栈后，由于我们栈中的数组是我们用malloc函数动态开辟出来的空间，因此我们需要释放掉这一块空间。具体的代码如下：

// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->a);
	ps->a = NULL;
}

尾声

关于栈这一数据结构，我们已经了解完了。虽然它的代码实现相对来说比较简单，但是想要用好栈，用对栈还是一件难事，需要我们通过大量的练习去更加深刻的了解它。下一期，我们将要了解的是与栈刚好相反的数据结构—队列。

若有纰漏或不足之处欢迎大家在评论区留言或者私信，同时也欢迎各位一起探讨学习。感谢您的观看！