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; }