设计顺序栈有关入栈和出栈的操作算法

问题描述：

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

问题解答：

两个栈共享向量空间，将两个栈的栈底设在向量两端，初始时，s1栈顶指针为-1，s2 栈顶指针为maxsize。两个栈顶指针相邻时为栈满。两个栈顶相向、迎面增长，栈顶指针指向栈顶元素。

#define maxsize  // 两个栈共享顺序存储空间所能达到的最多元素数
#define elemtp int  //假设元素类型为整型
typedef struct{
    elemtp stack[maxsize];  //栈空间
    int top [2];  //top为两个栈顶指针
}stk;
stk s;  //s是如上定义的结构类型变量，为全局变量

本题的关键在于，两个入栈和退栈时的栈顶指针的计算。s1栈是通常意义下的栈；而 s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。

此外，对于所有栈的操作，都要注意“入栈判满、出栈判空”的检查。

1) 入栈操作

int push(int i, int x){
    //入栈操作。i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素
    //入栈成功返回1，否则返回0
    if(i<0 || i>1){
        printf ("栈号输入不对");
        exit(0);
    }
    if(s.top[1]-s.top[0]==1){
        printf ("栈已满\n");
        return 0;
    }
    switch(i){
        case 0: s.stack[++s.top[0]] = x; return 1; break;
        case 1: s.stack[--s.top[1]] = x; return 1;
    }
}

2) 退栈操作

elemtp pop(int i) {
    //退栈算法。i代表栈号，i=0时为s1栈，i=l时为s2栈
    //退栈成功返回退栈元素，否则返回-1
    if(i<0||i>1){
        printf ("栈号输入错误\1n");
        exit(0);
    }
    switch(i) {
        case 0:
            if (s.top[0]==-1) {
                printf ("栈空\n");
                return -1;
            }else
                return s.stack[s.top[0]--];
        case 1:
            if(s.top[1]==maxsize){
                printf ("栈空\n");
                return -1;
            }else
                return s.stack[s.top[1]++];
    }//switch
}