数组栈的实现（c语言）

什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端

称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

图像解释：

栈的实现

栈的实现有两种方式一种是数组栈一种是链式栈，相比较而言使用数组去实现栈更优一些，因为栈的特点就是在栈顶增加和删除元素，而栈顶说白了也就是在数据的尾部增加和删除，如果使用链表来实现栈的话我们就要先去找尾在增加，而且如果要删除数据那么对于单向链表的话更加麻烦，所以这里我们使用数组去实现栈

使用数组实现栈

首先我们要明确栈的操作有哪些以及一个栈的结构。下面我就写出一个栈的头文件

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

_top选择的不同意义

这里我要重点讲解一下栈顶也就是_top的选择，_top的选择有两种一种是在栈中没有数据时_top选择为0，那么这个时候_top指向的并不是栈顶元素而是栈顶元素的下一个，这里我们可以这么理解如果你把_top初始值设为0但是你认为_top指向的是栈顶元素，那么不要忘了这里我们使用的是数组去实现的栈那么当下标为0时这时候的栈顶应该指向一个元素但是，我们假设的条件却是这时候的栈中没有任何一个元素。所以如果你要_top代表的是栈顶元素那么你在栈中没有元素的时候你要将_top设为-1。

下面我使用的是_top代表栈顶元素的下一个

函数接口1：初始化栈

初始化栈很明显就是要将创建的结构体里面的值给初始化，这里有两种初始化的方式，一种是在初始化的时候你就创建一些空间给与数组，而另一种方式就是你在初始化的时候不给数组空间，这里我选择的是后者。

void StackInit(Stack* ps)
{
	assert(ps);//断言防止传入空指针，因为ps是一个结构体指针那么外部在使用的时候一定会存在一个结构体
	//所以这里可以断言
	ps->_a = NULL;//在初始化的这里你可以选择一开始就开辟一些初始空间给这个数组但这里我就直接初始化为NULL了
	ps->_capacity = 0;//容量自然也是0
	ps->_top = 0;//这里有两种选择一种选择是0一种选择为-1，要解决为什么要使用0或-1我们就要理解top这里代表的含义
	//如果你想要top指向的就是栈顶的话你就要使用-1，如果你偏要使用0来代表栈顶，那么一开始的时候栈中没有元素，但是你的栈顶却指向了0，这明显不对
	//所以当栈中没有元素的时候我们就要使用-1来作为初始的栈顶元素指向
	//那么如果这里的top表示的是栈顶的下一个元素呢？那么这里的top初始值就可以写为0，因为如果一开始栈顶为无元素的下一个栈顶自然是0元素
}

函数接口2：入栈

入栈换句话来说就是我们要按照规则给栈增加数据。那么按照你选择的_top的值不同增加数据的方式也不同。

方式1：_top选择的是-1,那么这个时候你的_top指向的就是栈顶元素，即你要先将top++在将数据增加进栈中。

方式2：_top选择的是0，那么这个时候你的_top指向的是栈顶元素的下一个，即你要先将值赋给_top再让t_top++。

我这里选择的是方式二实现入栈

// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//首先我们要判断容量是否足够
	if (ps->_capacity == ps->_top)//我这里top的含义是栈顶的下一个元素，
  //所以当top等于容量等于top时就要扩容了，
		//如果这里你的top代表的时栈顶元素那么如果栈顶元素+1等于容量一样要扩容
	{
		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);//realloc函数当我们要扩容的指针指向的是NULL时，这时的realloc的功能相当于malloc
		if (tmp == NULL)//判断空间创建是否成功
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;//为空间赋值
		ps->_capacity = newcapacity;//更新容量
	}//因为在栈的操作里面只有这里一个地方需要判断容量，所以这里并没有将判断容量写成一个新函数
	//下面我们就要让元素进栈
	ps->_a[ps->_top] = data;//我们就以一开始为例子当栈中没有元素的时候我们放入的元素自然是栈顶的元素将其直接放入即可
	ps->_top++;//再让top++指向新栈顶的下一个元素
}

函数接口三，四：出栈和判断栈是否为空

我们要记住栈的特点就是后进的先出，所以我们出元素也只能将栈顶的元素出掉，然后我们还需要考虑的就是如果栈中没有元素了，我们还能出栈吗？很明显不能所以还需要判断栈中是否没有元素了，如果没有元素了那么就绝对不能出元素。这里不管你的-top初始值是什么，直接让_top减去1即可。

那么栈是否为空也很简单了，如果你的_top等于你设定的初始值那么这个栈就是空的。

判断是否为空：

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;//这里如果top为0代表这个栈为空返回的就是true，否则返回的就是false
}

出栈：

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//下面我们要判断是否是空栈
	assert(!StackEmpty(ps));//这里我们要知道当assert里面的值为假时断言就会启动，
  //所以当这个栈为空函数返回的为真但是经过!后就变成了假，断言就会启动
  //反之则不启动
	//下面我们就要让栈顶的元素移除
	ps->_top--;//即可
}

函数接口五：获取栈中有效元素个数

这里如果你选择的_top的初始值为-1那有效元素个数就是_top+1,如果你选择的_top初始值为0那有效元素就是_top。

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	//这里有效元素的个数也就是top了
	return ps->_top;
}

函数接口六：获取栈顶元素

这个函数也需要先判断栈是否为空，为空则不能进行获取栈顶元素，反之你就可以获取栈顶元素。

当然如果你的_top初始值为-1，那直接返回_top指向的元素即可，而另外一种方式则需要你将_top减去1之后再获取元素。

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//如果这里的栈为空我们仍然访问栈顶元素就会出现越界访问的情况
	//所以这里直接assert断死
	return ps->_a[ps->_top - 1];
}

函数接口七：销毁栈

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);//因为这里的数组是我们malloc来的所以需要释放
	ps->_capacity = 0;
	ps->_top = 0;
}

测试栈

void testST()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	int top = StackTop(&ps);//获取栈顶元素
	printf("%d ", top);//打印栈顶元素
	StackPop(&ps);//再将这个栈顶元素移除
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	while (!StackEmpty(&ps))
	{
		int top = StackTop(&ps);//获取栈顶元素
		printf("%d ", top);//打印元素
		StackPop(&ps);//再将这个栈顶元素移除
	}
	StackDestroy(&ps);
}
//下面我们就来测试栈
int main()
{
	testST();
	return 0;
}

下面我就将所有的实现函数的代码放在下面：

//栈的特点是后进先出
// 这里是运用的动态数组实现的栈
// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);//断言防止传入空指针，因为ps是一个结构体指针那么外部在使用的时候一定会存在一个结构体
	//所以这里可以断言
	ps->_a = NULL;//在初始化的这里你可以选择一开始就开辟一些初始空间给这个数组但这里我就直接初始化为NULL了
	ps->_capacity = 0;//容量自然也是0
	ps->_top = 0;//这里有两种选择一种选择是0一种选择为-1，要解决为什么要使用0或-1我们就要理解top这里代表的含义
	//如果你想要top指向的就是栈顶的话你就要使用-1，如果你偏要使用0来代表栈顶，那么一开始的时候栈中没有元素，但是你的栈顶却指向了0，这明显不对
	//所以当栈中没有元素的时候我们就要使用-1来作为初始的栈顶元素指向
	//那么如果这里的top表示的是栈顶的下一个元素呢？那么这里的top初始值就可以写为0，因为如果一开始栈顶为无元素的下一个栈顶自然是0元素
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//首先我们要判断容量是否足够
	if (ps->_capacity == ps->_top)//我这里top的含义是栈顶的下一个元素，所以当top等于容量等于top时就要扩容了，
		//如果这里你的top代表的时栈顶元素那么如果栈顶元素+1等于容量一样要扩容
	{
		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);//realloc函数当我们要扩容的指针指向的是NULL时，这时的realloc的功能相当于malloc
		if (tmp == NULL)//判断空间创建是否成功
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;//为空间赋值
		ps->_capacity = newcapacity;//更新容量
	}//因为在栈的操作里面只有这里一个地方需要判断容量，所以这里并没有将判断容量写成一个新函数
	//下面我们就要让元素进栈
	ps->_a[ps->_top] = data;//我们就以一开始为例子当栈中没有元素的时候我们放入的元素自然是栈顶的元素将其直接放入即可
	ps->_top++;//再让top++指向新栈顶的下一个元素
}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//下面我们要判断是否是空栈
	assert(!StackEmpty(ps));
	//下面我们就要让栈顶的元素移除
	ps->_top--;//即可
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//如果这里的栈为空我们仍然访问栈顶元素就会出现越界访问的情况
	//所以这里直接assert断死
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	//这里有效元素的个数也就是top了
	return ps->_top;
}
// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_capacity = 0;
	ps->_top = 0;
}

希望这篇文章能对你有所帮助，如果有错误，麻烦您能指出，我一定改正。

【文章出处:香港站群多ip服务器 http://www.558idc.com/hkzq.html提供，感恩】