数据结构算法之---共享栈算法

分析： 栈是一种只允许在一端进行插入和删除的线性表，具有”后进先出“的特点，有顺序存储和链式存储两种存储方式。而栈的顺序存储结构又可分为顺序栈和共享栈；栈的链式存储为链栈。此题考察对共享栈的理解。首先理解”栈顶相向，迎面而增“的意思，该句话指的是两个栈s1、s2的栈底分别是0和maxsize-1，然后栈中进入元素时，依次向共享栈的中间靠拢。图示如下：
分析： 首先，当元素入栈时，需要判满，判满操作为s.top[1]-s.top[0]=1（注：top[0]表示栈1指针，top[1]表示栈2指针）;当元素出栈时，需要判空，判空操作为s.top[0]==-1和s.top[1]=maxsize;代码如下:

#define maxsize 100
#define elemtype int
typedef struct stk
{
    elemtype stack[maxsize];
    int top[2];//其中top[0]和top[1]分别表示两个栈顶指针
}stk;
stk s;//声明一个栈s
void initStack(stk &s)//初始化函数
{
    s.top[0]=-1;//栈1的栈顶指针初始化
    s.top[1]=maxsize;//栈2的栈顶指针初始化
}

int push(int i,elemtype x)//入栈
{
    if(i<0 || i>1)
    {
        cout<<"输入错误,栈号应为0或1";
        return;
    }
    if(s.top[1]-s.top[0]==1)//判满
    {
        cout<<"栈已满";
        return 0;
    }
    switch(i)
    {
        case 0: s.stack[++s.top[0]]=x;//栈1栈顶指针向右移动
                return 1;
                break;
        case 1: s.stack[--s.top[1]]=x;//栈2栈顶指针向左移动
                return 1;
    }
}
elemtype pop(int i)//出栈
{
    if(i<0 || i>1)
    {
        cout<<"输入错误,栈号应为0或1";
        return;
    }
    switch(i)
    {
        case 0:
        if(s.top[0]==-1)//判空
        {
            cout<<"栈空";
            return 0;
        }
        else
        {
            return s.stack[s.top[0]--];//栈1栈顶指针向左移动
        }
            break;
        case 1:
        if(s.top[1]==maxsize)//判空
        {
            cout<<"栈空";
            return 0;
        }
        else
        {
            return s.stack[s.top[1]++];//栈1栈顶指针向右移动
        }
    }
}