数据结构栈的实现-创新互联

• 栈的概念
• 栈的结构声明
• 初始化
• 数据入栈
• 出栈
• 判断栈是否为空
• 取栈顶的值
• 销毁栈

栈是一种线性表，插入数据的一端叫栈顶，另一端叫栈底。
入栈：数据从栈顶进入栈中
出栈：数据从栈顶删除
所以，栈的特点就是先进后出，也可以说后进先出。

入栈图

出栈图

根据栈先进后出的性质，我们来实现一个简单的栈。

typedef int STDataType;

struct Stack
{//存放数据的空间
	STDataType* data;
	//栈顶位置
	size_t top;
	//栈的容量
	size_t Cacpcity;
}ST;

初始化很简单，我们让data指向的空间为NULL,顶部位置从0开始，每插入一个数据就+1。

//初始化
void StackInto(ST* ST)
{ST->data = NULL;
	ST->top = 0;
	ST->Cacpcity = 0;
}

我们可以看到初始化成功了。

栈初始化好后，我们就要把数据插入栈中，因为是先进后出，所以我们直接在数组尾部插入即可。

//容量更新
void CheckCacpcity(ST* ST)
{//容量等于top时，说明数组没有空间了
	if (ST->Cacpcity == ST->top)
	{//如果空间为0，初始空间4，如果不为0，空间*2
		int NewCacpcity = ST->Cacpcity == 0 ? 4 : ST->Cacpcity * 2;
		//扩容
		STDataType* newdata = (STDataType*)realloc(ST->data,sizeof(STDataType) * NewCacpcity);
		//扩容是否成功
		if (newdata == NULL)
		{	printf("reallo fail\n");
			exit(-1);
		}
		ST->data = newdata;
		//更新容量
		ST->Cacpcity = NewCacpcity;
	}
}

//数据入栈
void StackPush(ST* ST, STDataType x)
{//断言，传进来的指针不能为空
	assert(ST);
	//容量不够自动增容
	CheckCacpcity(ST);

	//尾部数据入栈
	*(ST->data+ST->top) = x;
	ST->top++;
}

然后我们发现数据入栈。并且容量更新了。

因为栈是后进来的先出去，所以直接删除最后一个元素即可。

//数据出栈
void StackPop(ST* ST)
{assert(ST);
	//如果top等于0，说明没有元素了
	assert(ST->top >0);

	//出栈操作，就是这么简单
	ST->top--;

}

直接判断top的值是否为0即可，返回真即为空。

//栈是否为空
bool StackEmpty(ST* ST)
{assert(ST);
	return ST->top == 0;
}

同样很简单，top-1的值就是栈顶的值，但是要注意栈必须不为空。

//取栈顶的值
STDataType StackTop(ST* ST)
{assert(ST);
	assert(!StackEmpty(ST));
	return ST->data[ST->top - 1];
}

入栈的顺序是1 2 3 4 5 ，出栈的顺序是 5 4 3 2 1

这个也简单，top和capacity置为0，释放掉data，指针置为空即可。

//销毁
void StackDestroy(ST* ST)
{assert(ST);
	ST->top = ST->Cacpcity = 0;
	free(ST->data);
	ST->data = NULL;
}

销毁成功。
代码已上传至git

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧