栈（C语言版）

一.栈的概念及结构

二.栈的对比

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

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;
}