题目要求:设有两个栈 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
}