68-数据结构设计——共享栈

题目要求:设有两个栈 S1,S2 都采用顺序栈方式,并且共享一个存储区[0…maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计 S1,S2有关入栈和出栈的操作算法。

1.结构体设计

#define STACK_SIZE 10
typedef struct SharedStack
{
	int elem[STACK_SIZE];
	int top1;
	int top2;
}SharedStack,*PSharedStack;

2.初始化

//初始化
void InitSharedStack(PSharedStack ps)
{
	assert(ps != NULL);
	if(ps == NULL)
		return ;

	ps->top1 = 0;//1栈的栈顶
	ps->top2 = STACK_SIZE-1;//2的栈顶
}

初始化测试

	//初始化测试
	SharedStack ps;
	InitSharedStack(&ps);
	printf("程序正常结束\n");

3.入栈

//入栈
bool Push(PSharedStack ps,int val,int no)
{
	assert(ps != NULL);
	if(ps == NULL)
		return false;

	if(IsFull(ps) || no<1 || no>2)
		return false;

	if(no==1)//往1栈入
	{
			ps->elem[ps->top1++] = val;
	}
	else//往2栈入
	{
			ps->elem[ps->top2--] = val;
	}

	return true;
}

4.出栈

//出栈
bool Pop(PSharedStack ps,int *rtval,int no)
{
	assert(ps != NULL);
	if(ps == NULL)
		return false;

	if(no==1 && !IsEmpty1(ps))//出1的栈
	{
		*rtval = ps->elem[--ps->top1];
		return true;
	}
	else if(no == 2 && !IsEmpty2(ps))//出2的栈
	{
		*rtval = ps->elem[++ps->top2];
		return true;
	}

	return false;
}

入栈出栈测试

//入栈测试
	SharedStack ps;
	InitSharedStack(&ps);
	int val;
	for(int i = 0;i<5;i++)
	{
		Push(&ps,i,1);
	}
	for(int i = 0;i<5;i++)
	{
		Pop(&ps,&val,1);
		printf("%d ",val);
	}
	for(int i = 5;i<10;i++)
	{
		Push(&ps,i,2);
	}
	for(int i = 5;i<10;i++)
	{
		Pop(&ps,&val,2);
		printf("%d ",val);
	}
	printf("\n程序正常结束\n");

5.判空1是否为空栈

//判空1是否为空栈
bool IsEmpty1(PSharedStack ps)
{
	assert(ps != NULL);
	if(ps == NULL)
		return false;

	return ps->top1 == 0;
}

判空1是否为空栈测试

	//判空1是否为空栈测试
	SharedStack ps;
	InitSharedStack(&ps);
	if(IsEmpty1(&ps))
		printf("是空栈\n");
	else
		printf("不是空栈\n");
	Push(&ps,0,1);
	if(IsEmpty1(&ps))
		printf("是空栈\n");
	else
		printf("不是空栈\n");
	printf("程序正常结束\n");

6.判端2是否为空栈

//判端2是否为空栈
bool IsEmpty2(PSharedStack ps)
{
	assert(ps != NULL);
	if(ps == NULL)
		return false;

	return ps->top2 == STACK_SIZE-1;
}

判端2是否为空栈测试

	//判空2是否为空栈测试
	SharedStack ps;
	InitSharedStack(&ps);
	if(IsEmpty2(&ps))
		printf("是空栈\n");
	else
		printf("不是空栈\n");
	Push(&ps,0,2);
	if(IsEmpty2(&ps))
		printf("是空栈\n");
	else
		printf("不是空栈\n");
	printf("程序正常结束\n");

7.判满

static bool IsFull(PSharedStack ps)
{
	assert(ps != NULL);
	if(ps == NULL)
		return false;

	return ps->top1 > ps->top2;//只要top1>top2就是满的,top1=top2的时候还剩最后一个格子,无论是谁占了这个格子,都会导致top1>top2
}
上一篇:测试平台系列(68) 解决数据驱动带来的麻烦


下一篇:Go 记录一次groutine通信与context控制