问题描述

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

算法思想

因为两个栈公用一个空间，假设一个栈为0#，规定其为空时top[0]==-1；另一个栈为1#规定其为空时，top[1]==MaxSize；
入栈时，先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，入栈操作和顺序栈的入栈操作并无太大不同。选定之后进行入栈操作。这里应该注意此共享栈是否已满，如果已满则不能进行入栈操作。如若入栈成功则返回0；入栈失败则返回-1；
出栈时，先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，出栈操作和顺序栈的出栈操作并无太大不同。选定之后进行出栈操作。如果出栈成功返回0；出栈失败返回-1；
综上，算法描述如下：

算法描述

//共享栈的入栈操作
int Push(SqStack*s, ElemType x, int n)
{
    if(n<0||n>1){
        printf("The stack number is false!
");
        return -1;
    }
    if(s->top[1]-s->top[0]==1){
        printf("The stack is full!
");
        return -1;
    }
    switch(n){
        case 0:s->data[++s->top[0]]=x;break;
        case 1:s->data[--s->top[1]]=x;break;
    }
    return 0;
}

//共享栈的出栈操作
int Pop(SqStack *s, ElemType* x,int n)
{
    if(n<0||n>1){
        printf("The stack number is false!
");
        return -1;
    }
    switch(n){
        case 0:
            if(s->top[0]==-1){
                printf("The stack[0] is empty!
");
            }
            *x=s->data[s->top[0]--];
            break;
        case 1:
            if(s->top[1]==MaxSize){
                printf("The stack[1] is empty!
");
            }
            *x=s->data[s->top[1]++];
            break;
    }
    return 0;
}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>
#define  MaxSize 100

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int top[2];
}SqStack;

void InitStack(SqStack*);
int Push(SqStack*,ElemType,int);
int Pop(SqStack*,ElemType*,int);

int main(int argc,char* argv[])
{
    SqStack s;
    InitStack(&s);

    ElemType x=5;
    int n=0;
    int flagPush;
    flagPush=Push(&s,x,n);
    if(flagPush){
        printf("Push false!
");
    }else{
        printf("Push %d success!
",x);
    }

    int flagPop;
    flagPop=Pop(&s,&x,n);
    if(flagPop){
        printf("Pop false!
");
    }else{
        printf("Pop %d  success!
",x);
    }
    return 0;
}
//初始化共享栈
void InitStack(SqStack *s)
{
    s->top[0]=-1;
    s->top[1]=MaxSize;
}
//入栈操作
int Push(SqStack*s, ElemType x, int n)
{
    if(n<0||n>1){
        printf("The stack number is false!
");
        return -1;
    }
    if(s->top[1]-s->top[0]==1){
        printf("The stack is full!
");
        return -1;
    }
    switch(n){
        case 0:s->data[++s->top[0]]=x;break;
        case 1:s->data[--s->top[1]]=x;break;
    }
    return 0;
}
//出栈操作
int Pop(SqStack *s, ElemType* x,int n)
{
    if(n<0||n>1){
        printf("The stack number is false!
");
        return -1;
    }
    switch(n){
        case 0:
            if(s->top[0]==-1){
                printf("The stack[0] is empty!
");
            }
            *x=s->data[s->top[0]--];
            break;
        case 1:
            if(s->top[1]==MaxSize){
                printf("The stack[1] is empty!
");
            }
            *x=s->data[s->top[1]++];
            break;
    }
    return 0;
}