【数据结构】C语言实现共享栈

导言

大家好，很高兴又和大家见面啦！！！
在上一篇内容中，我们介绍了如何通过C语言实现顺序栈，并且在介绍顺序栈的进栈操作时有提到过我们可以通过选择数组的首元素或者尾元素作为栈底，来进行栈的创建，以及栈的另一种形式——链栈。

根据前面的介绍，我们知道了顺序栈是通过静态数组进行实现的，既然是静态数组，那么它对应的空间大小就是不可被改变的。由于顺序栈的空间限制，当我们入栈的元素个数超过顺序栈的空间大小时，就会造成栈溢出的问题，我们为了避免出现栈溢出的情况，我们可以通过两种方式来进行栈的创建：

1. 可以选择在申请空间时申请一个足够大的空间；
2. 可以创建一个动态的链栈；

在今天的内容中我们将来详细介绍一下应该如何通过C语言来实现共享栈；

一、共享栈

为了解决栈溢出的问题，当我们选择通过申请一个足够大的空间时，势必就会造成内容空间的浪费，为了合理的解决这个问题，我们则可以根据栈在创建时的栈底选择不同，在同一个空间上创建两个栈，这个空间就被称为共享栈，如下图所示：

从图中可以看到在共享栈中，一个栈的栈底选择的是数组的首元素，一个栈的栈底选择的是数组的尾元素，它们对应的下标一个是0，一个是MaxSize-1。

1.1 共享栈的初始化

根据共享栈的结构，我们在初始化时，可以分别初始化为-1和MaxSize，也可以初始化为0和MaxSize-1，如下所示：

//共享栈的数据类型
#define MaxSize 10//定义空间存储的最大元素
typedef struct SqStack {
	int data[MaxSize];//存储数据的静态数组
	int top_a;//栈a的栈顶指针
	int top_b;//栈b的栈顶指针
}SqStack;
//初始化共享栈
void InitStack(SqStack* S) {
	assert(S);//通过断言来对指针进行判空
	S->top_a = -1;//将栈a的栈顶指针初始化为-1
	S->top_b = MaxSize;//将栈b的栈顶指针初始化为MaxSize
}

这里为了方便演示，我是定义的一个整型共享栈，站内能存储的是整型数据类型的数据元素。在初始化阶段，我这里是将其初始化为-1和MaxSize，当然也可以初始化为0和MaxSize-1，这里我就不演示了，大家可以自行下去尝试一下。

1.2 共享栈的判空

完成初始化后，我们要对其进行判空操作的话则是同时判断两个栈顶指针的值，如下所示：

//共享栈的判空
bool EmptyStack(SqStack S) {
	if (S.top_a == -1 && S.top_b == MaxSize)
		return true;
	return false;
}

在初始化阶段我们是通过assert来进行问题反馈，因此可以对函数的返回类型设置为void，在进行判空操作时，我们是通过函数的返回值来进行判断，所以这里通过分支语句来对不同的返回值做出对应的提示；

1.3 共享栈的入栈

当我要对共享栈进行入栈操作时，可以有多种实现方式：

1. 对两个栈同时进行入栈操作；
2. 对两个栈依次进行入栈操作；

这里我给大家演示一下对两个栈依次进行入栈操作应该如何实现，如下所示：

//共享栈的入栈操作
int Push(SqStack* S, int x, char flag) {
	if (!S)
		return 3;
	if(S->top_a + 1 == S->top_b)
		return 0;
	if (flag == 'a') {
		S->data[++S->top_a] = x;
	}
	else if (flag == 'b') {
		S->data[--S->top_b] = x;
	}
	else
		return 2;
	return 1;
}

为了更加直观的收到函数的反馈，这里我们可以通过将函数的返回值以0,1,2,3这三个值来进行反馈，主函数中通过分支语句来判断返回值，以此给出不同的反馈，下面我们就来介绍一下这些返回值的作用；

1.3.1 空指针

在进行编码时，对于空指针的问题我们一定要注意，在入栈操作中，我们是要对共享栈进行修改，所以此时的传参为传址传参，正常情况下，我们都是会将栈的起始地址传过去，但是为了避免出现问题，我们则需要对指针进行判空，如果此时的指针为空指针时，那说明我们并没有将需要修改的栈传给函数，此时就可以通过返回值来提醒使用者，如下所示：

可以看到，当我们传入的指针为空指针时，此时函数就会返回3，在switc语句中，3并不属于0,1,2这三者中的任意一种情况，因此，语句会执行default语句，此时我们就可以根据对应的提示来进行代码的检测，并对问题进行修改；

1.3.2 满栈

相比于单个的顺序栈，共享栈在进行入栈前对满栈的判断则是两个栈顶元素相邻，如下所示：

从图中可以看到，当共享栈的两个栈顶元素相邻时，它们对应的栈顶指针也相邻，因此指针之间的差值为1，也就是说当两个栈顶指针相差1时，此时我们是无法继续进行入栈操作的，这时我们可以通过返回0值来告诉使用者此时已经满栈了，并通过返回值结束入栈操作；

1.3.3 入栈空间错误

为了能更加精准的将元素存入对应的栈空间内，这里我们是通过一个标志变量来执行，当标志为’a’时，说明我们此时要存入的是栈a，当标志为’b’时，说明我们此时要存入的是栈b，但是当标志为其它内容时，我们需要给用户提示，说明输入空间有误，如下所示：

从测试结果中我们可以看到，当我们输入’c’时，此时的标志既不是’a’也不是’b’，所以函数返回值为2，回到主函数后，会执行返回值为2的对应语句，这时程序会提示我们入栈空间输入错误，请重新输入，通过提示，我们就能知道应该如何正确输入了；

1.3.4 正常入栈

当我们传参正确、栈未满且空间都正确时，此时函数返回值为1，这样我们可以一直进行输入，知道满栈为止，如下所示：

从测试结果中我们可以看到，正常情况下栈是只能存储10个元素的，也就是当栈a入栈4个元素后，栈b只能入栈6个元素，这里当我们对栈b已经入栈了6个元素后，还想入栈第7个元素时，此时程序就会提示，已经满栈，并退出循环；

1.3.5 小结

对于共享栈的入栈操作我们就介绍完了，通过这里演示的代码我们可以看到，此时咱们算法是有很强的健壮性的，可以根据不同的问题给出不同的反馈。
当然，在实际操作中肯定不会像我这样去进行编写代码，我们需要根据具体的情况来对代码进行相应的调整，这里我们只要保证操作的逻辑没有发生改变就行。

1.4 共享栈的查找

对于共享栈而言，我们要查找栈顶指针的话也是需要指明查找的对象，因此，我们可以依然可以通过标志变量进行指定，如下所示：

//共享栈的栈顶查找
int GetTop(SqStack S, char flag,int* x) {
	assert(x);
	if (flag == 'a') {
		if (S.top_a != -1)
			*x = S.data[S.top_a];
		return S.top_a;
	}
	else if (flag == 'b') {
		if (S.top_b != MaxSize)
			*x = S.data[S.top_b];
		return S.top_b;
	}
	else
		return MaxSize + 1;
}

由于查找栈顶后，我们还需要将栈顶元素带回到主函数中，因此存储数据的变量我们选择的是通过传址的方式进行传参，并通过指针接收，这里我们可以直接通过assert断言来对指针x进行判空操作；

相比于正常的顺序栈而言，共享栈在进行栈顶查找时，我们通过标志变量来判断查找的对象，并通过判断查找对象的栈顶指针的位置来决定是否将该位置存储的值带回；

对应的主函数中，我们则可以根据函数对应的返回值来给出对应的反馈，如下所示：

	printf("请输入要查询的栈空间<a/b>:>");
	scanf("%c", &flag);
	int top = GetTop(S, flag, &x);
	switch (top) {
	case -1:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize + 1:
		printf("共享栈中没有栈%c\n", flag);
		break;
	default:
		printf("栈%c的栈顶为%d，栈顶元素为%d\n", flag, top, x);
		break;
	}

在共享栈中栈a的栈顶指针的取值范围是-1～MaxSize-1，栈b的栈顶指针的取值范围是MaxSize～0，因此返回值为-1与返回值为MaxSize以及返回值为MaxSize+1这三种情况都是唯一的，所以我们在switch语句中只需要将这三者单独罗列出来即可，对其它的情况我们只需要正常打印就行；

1.5 共享栈的出栈

共享栈的出栈操作与入栈操作同理，都是需要根据指定出栈对象来完成出栈操作，因此，我们在出栈操作中同样需要增设一个标志变量来制定出栈的对象，如下所示：

//共享栈的出栈
int Pop(SqStack* S, char flag, int* x) {
	assert(S && x);
	if (flag == 'a') {
		if (S->top_a != -1)
			*x = S->data[S->top_a--];
		return S->top_a;
	}
	else if (flag == 'b') {
		if (S->top_b != MaxSize)
			*x = S->data[S->top_b++];
		return S->top_b;
	}
	else
		return MaxSize + 1;
}

这里我是通过仿照查找栈顶指针的操作编写的代码，根据函数的返回值，我们在主函数中就可以编写以下代码：

	printf("请输入需要出栈的栈空间<a/b>:>");
	scanf("%c", &flag);
	top = Pop(&S, flag, &x);
	switch (top) {
	case -1:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize + 1:
		printf("共享栈中没有栈%c\n", flag);
		break;
	default:
		printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
		break;
	}

可以看到，此时我们只是对代码进行了一些小改动，反馈逻辑与栈顶指针的查找的反馈逻辑是一致的；

1.6 共享栈的销毁

共享栈的销毁我们则是通过在出栈的基础上加上一个循环，将所有的元素全部进行出栈即可，对应的代码如下所示：

	int des = 2;
	while (des) {
		printf("请输入需要出栈的栈空间<a/b>:>");
		scanf("%c", &flag);
		top = Pop(&S, flag, &x);
		switch (top) {
		case -1:
			printf("栈%c为空栈\n", flag);
			des--;
			break;
		case MaxSize:
			printf("栈%c为空栈\n", flag);
			des--;
			break;
		case MaxSize + 1:
			printf("共享栈中没有栈%c\n", flag);
			break;
		default:
			printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
			break;
		}
		getchar();
	}
	printf("共享栈S已完成销毁\n");

我这里的代码执行的销毁是手动进行元素的出栈，有兴趣的朋友也可以将其改为自动进行销毁操作。

从循环的判断条件我们可以看到，此时除非两个栈都为空栈时，循环才会停止否则就会一直运行；在完成所有的元素弹出后，栈的空间回收我们只需要等待程序运行结束后自动回收即可。

二、共享栈的实现演示

为了节约时间，这里我将最大的元素个数修改为4，下面我们在来看一下具体的操作演示：

可以看到，此时我们已经成功实现了共享栈的所有操作，共享栈对应操作的代码如下所示，有需要的朋友自取：

//共享栈的数据类型
#define MaxSize 4//定义空间存储的最大元素
typedef struct SqStack {
	int data[MaxSize];//存储数据的静态数组
	int top_a;//栈a的栈顶指针
	int top_b;//栈b的栈顶指针
}SqStack;
//初始化共享栈
void InitStack(SqStack* S) {
	assert(S);//通过断言来对指针进行判空
	S->top_a = -1;//将栈a的栈顶指针初始化为-1
	S->top_b = MaxSize;//将栈b的栈顶指针初始化为MaxSize
}
//共享栈的判空
bool EmptyStack(SqStack S) {
	if (S.top_a == -1 && S.top_b == MaxSize)
		return true;
	return false;
}
//共享栈的入栈操作
int Push(SqStack* S, int x, char flag) {
	if (!S)
		return 3;
	if(S->top_a + 1 == S->top_b)
		return 0;
	if (flag == 'a') {
		S->data[++S->top_a] = x;
	}
	else if (flag == 'b') {
		S->data[--S->top_b] = x;
	}
	else
		return 2;
	return 1;
}
//共享栈的栈顶查找
int GetTop(SqStack S, char flag,int* x) {
	assert(x);
	if (flag == 'a') {
		if (S.top_a != -1)
			*x = S.data[S.top_a];
		return S.top_a;
	}
	else if (flag == 'b') {
		if (S.top_b != MaxSize)
			*x = S.data[S.top_b];
		return S.top_b;
	}
	else
		return MaxSize + 1;
}
//共享栈的出栈
int Pop(SqStack* S, char flag, int* x) {
	assert(S && x);
	if (flag == 'a') {
		if (S->top_a != -1)
			*x = S->data[S->top_a--];
		return S->top_a;
	}
	else if (flag == 'b') {
		if (S->top_b != MaxSize)
			*x = S->data[S->top_b++];
		return S->top_b;
	}
	else
		return MaxSize + 1;
}
int main() {
	SqStack S;
	InitStack(&S);//初始化共享栈
	if (EmptyStack(S))
		printf("共享栈为空栈\n");
	else
		printf("共享栈内有存入元素\n");
	char flag = 0;
	int x = 0;
	int ret = 1;
	while (ret == 1 || ret == 2) {
		printf("请输入进行入栈的空间:>");
		scanf("%c", &flag);
		printf("请输入进行入栈的数据:>");
		scanf("%d", &x);
		ret = Push(&S, x, flag);
		switch (ret)
		{
		case 0:
			printf("共享栈已满栈\n");
			break;
		case 1:
			break;
		case 2:
			printf("入栈的空间输入错误，请重新输入<a/b>\n");
			break;
		default:
			printf("指针S为空指针\n");
			break;
		}
		getchar();//读取输入缓冲区的\n避免对后面的输入造成干扰
	}
	printf("请输入要查询的栈空间<a/b>:>");
	scanf("%c", &flag);
	int top = GetTop(S, flag, &x);
	switch (top) {
	case -1:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize:
		printf("栈%c为空栈\n", flag);
		break;
	case MaxSize + 1:
		printf("共享栈中没有栈%c\n", flag);
		break;
	default:
		printf("栈%c的栈顶为%d，栈顶元素为%d\n", flag, top, x);
		break;
	}
	getchar();
	int des = 2;
	while (des) {
		printf("请输入需要出栈的栈空间<a/b>:>");
		scanf("%c", &flag);
		top = Pop(&S, flag, &x);
		switch (top) {
		case -1:
			printf("栈%c为空栈\n", flag);
			des--;
			break;
		case MaxSize:
			printf("栈%c为空栈\n", flag);
			des--;
			break;
		case MaxSize + 1:
			printf("共享栈中没有栈%c\n", flag);
			break;
		default:
			printf("栈%c的已完成栈顶元素%d的出栈，此时的栈顶为%d\n", flag, x, top);
			break;
		}
		getchar();
	}
	printf("共享栈S已完成销毁\n");
	return 0;
}

结语

咱们今天的内容到这里就全部介绍完了，希望今天的内容能够帮助大家更好的理解共享栈以及对应的操作如何通过C语言来实现，在下一个篇章中，我将继续给大家介绍链栈的相关内容，大家记得关注哦！！！
最后感谢大家的翻阅，咱们下一篇再见！！！