2つのスタックが記憶空間を共有する(1つの配列で2つのスタックを格納する)
2837 ワード
思想:まず1つの連続的な記憶空間(1つの配列)を開拓する.2つのスタックのトップは、それぞれ配列の両端を指し、2つのスタックのトップがpush操作に従って配列の内側に移動する.2スタックのスタックトップはpop操作と共に配列の外側に移動した.
#include
#include
// ,
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef int ElemType;
// ;
typedef struct{
ElemType data[MAXSIZE];
int top1;// 1
int top2;// 2
}DoubleStack;
//1.
Status InitDS(DoubleStack *DS){
memset(DS->data,'\0',sizeof(ElemType)*MAXSIZE);/* memset , , */
DS->top1=-1;
DS->top2=MAXSIZE;
return OK;
}
//2. push , , 1 2
Status DoublePush(DoubleStack *DS,ElemType e,int s_number){
if(DS->top1+1==DS->top2){
// ,
return ERROR;
}
if(s_number==1){
// 1
++(DS->top1);
DS->data[DS->top1]=e;
}else if(s_number==2){
--(DS->top2);
DS->data[DS->top2]=e;
}
return OK;
}
// pop
Status DoublePop(DoubleStack *DS,ElemType *e,int s_number){
if(DS->top1==-1 && DS->top2==MAXSIZE){
printf(" !, !");
return ERROR;
}else if(DS->top1==-1){
// 1 , 2
if(s_number!=2){
printf(" 1 , 2!
");
return ERROR;
}
}else if(DS->top2==MAXSIZE){
if(s_number!=1){
printf(" 2 , 1!
");
return ERROR;
}
}
if(1==s_number){
*e=DS->data[DS->top1];
--DS->top1;
}else if(2==s_number){
*e=DS->data[DS->top2];
++DS->top2;
}else{
printf(" , 1 2
");
return ERROR;
}
return OK;
}
int main()
{
DoubleStack DS;
if(OK==InitDS(&DS)){
printf(" !");
}
int e,s_number;
printf("
");
while(2==scanf("%d,%d",&e,&s_number)){
if(OK==DoublePush(&DS,e,s_number)){
int i,j;
i=0;
j=MAXSIZE-1;
printf(" 1 :");
while(i<=DS.top1){
printf("%d\t",DS.data[i++]);
}
printf("
2 :");
while(j>=DS.top2){
printf("%d\t",DS.data[j--]);
}
}
}
printf("
");
while(1==scanf("%d",&s_number)){
printf(" :");
if(OK==DoublePop(&DS,&e,s_number))
printf("%d\t",e);
}
return 0;
}