兩棧共享存儲空間（用一個數組存儲兩個棧）

思想：先開辟一段連續的存儲空間（一個數組）；兩個棧棧頂分别指向數組的兩端，随着push操作兩棧的棧頂向數組内側移動；随着pop操作兩棧的棧頂向數組外側移動。

#include <stdio.h>
#include <stdlib.h>
//棧的順序存儲結構，用一維數組實作


#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!\n");
            return ERROR;
        }
    }else if(DS->top2==MAXSIZE){
        if(s_number!=1){
            printf("此時棧2為空，棧的标号必須為1!\n");
            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\n");
        return ERROR;
    }
    return OK;
}
int main()
{
    
    DoubleStack DS;
    if(OK==InitDS(&DS)){
        printf("初始化成功！");
    }
    int e,s_number;
    printf("想要插入的值及棧号\n");
    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("\n棧2的元素為：");
                while(j>=DS.top2){
                    printf("%d\t",DS.data[j--]);
                }
            }


    }
    printf("輸入出棧的棧号\n");
    while(1==scanf("%d",&s_number)){
        printf("出棧的值為：");
        if(OK==DoublePop(&DS,&e,s_number))
            printf("%d\t",e);
    }


    return 0;
}