栈（C语言版）

一.栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。 栈中的数据元素遵守 后进先出 LIFO （ Last In First Out ）的原则。（可以看成子弹与弹夹的关系）

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

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

二.栈的对比

栈的实现数组和链表都可以，下面我们来对比下各种实现：

1.数组实现：

相当于之前顺序表的尾插尾插用尾去做了栈顶，非常合适。唯一缺陷就是:空间不够，需要增容

2.单链表实现：

如果要用单链表实现，那么就 用头去做栈顶更好，这样可以避免找不到前面的，入栈和出栈效率都是 0(1)，缺点：每一次都要开辟空间，而且空间消耗远比数组大。

3.双链表实现：

此时可以用尾做栈顶，双向链表效率也为0（1),但是双链表缺点更大：不但每次都要开辟空间，而且空间消耗比单链表还要严重。

因此，我们用数组其实更好，增容也不是每次都增的，总体较为合适！

下面我们开始用数组实现栈：（放心，绝对比链表简单）

三.栈的实现

第一步：实现结构体

//定义结构体
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;//数据
	int top;//栈顶
	int capacity;//容量
}SS;

第二步：实现基本接口

// 初始化栈定义
void StackInit(SS* ps)
{
	//检查
	assert(ps);
	//开辟空间
	ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);//注意：开辟的空间为STDataType类型
	ps->top = 0;//此时栈顶为0
	ps->capacity = 4;//容量为开辟的4个STDataType空间大小
}

// 入栈定义
void StackPush(SS* ps, STDataType x)
{
	//检查栈空间是否存足
	if (ps->top == ps->capacity)
	{
		//空间不够，扩容
		STDataType* tmp = (STDataType*)realloc(ps->arr, ps->capacity * sizeof(STDataType) * 2);
		if (tmp == NULL)
		{
			exit(-1);
		}
		else
		{
			ps->arr = tmp;
			ps->capacity *= 2;
		}
	}
	//开始入栈操作
	ps->arr[ps->top] = x;
	ps->top++;
}

// 出栈定义
void StackPop(SS* ps)
{
	//判断
	assert(ps);
	//栈不能为空
	assert(ps->top > 0);
	ps->top--;
}

// 获取栈顶元素定义
STDataType StackTop(SS* ps)
{
	//判断
	assert(ps);
	//栈不能为空
	assert(ps->top > 0);
	return ps->arr[ps->top-1];
}

// 获取栈中有效元素个数定义
int StackSize(SS* ps)
{
	assert(ps);
	return ps->top;
}

// 检测栈是否为空，如果为空返回false，如果不为空返回true
bool StackEmpty(SS* ps)
{
	assert(ps);
	return ps->top == 0;
}

// 销毁栈定义
void StackDestory(SS* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

这边建议大家还是边实现边检查，不然出问题了不好找。

由于我这写一个检查一个太耗时间，所以我就写完了统一检查：

#include "Stack.h"
void test1()
{
	SS s1;
	StackInit(&s1);
	StackPush(&s1, 1);
	StackPush(&s1, 2);
	StackPush(&s1, 3);
	StackPush(&s1, 4);
	StackPush(&s1, 5);
	StackPush(&s1, 6);
	StackPush(&s1, 7);
	StackPush(&s1, 8);
	StackPush(&s1, 9);
	StackPush(&s1, 10);
	while (!StackEmpty(&s1))
	{
		printf("%d ",StackTop(&s1));
		StackPop(&s1);
	}
	printf("\n");
	StackDestory(&s1);
}
int main()
{
	test1();
	return 0;
}

结果如下：