习题3.1

1.将编号为0和1的两个栈存放于一个数组空间V[m]中,栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空;当第1号栈的栈顶指针 top[1]等于m时，该栈为空。两个栈均从两端向中间增长（见图3.2)。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下:

算法思路:

两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向增长，栈顶指针指向栈顶元素。左栈是通常意义下的栈，在进栈操作时，其栈顶指针右移(加1)，出栈时，栈顶指针左移(减1)。而右栈进栈操作时，其栈顶指针左移(减1)，出栈时,栈顶指针右移(加1)。

完整函数：

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100


typedef struct
{
    int top[2],bot[2];
    int *V;     
    int m;      
}LNode,Stack;

Status InitStack(Stack &S,int m)
{
    S.V=new int[m];
    S.bot[0]=-1;
    S.bot[1]=m;
    S.top[0]=-1;
    S.top[1]=m;
    return OK;
}

Status Push(Stack &S,int i,int x)
{
    if(S.top[1]-S.top[0]==1) {cout<<"栈满"<<endl;return ERROR;}
    if(i==0)
    S.V[++S.top[0]]=x;
    else
    S.V[--S.top[1]]=x;
    return OK;
}

Status Pop(Stack &S,int i,int &x)
{
    if(S.top[i]==S.bot[i])
    {
        cout<<"栈空"<<endl;
        return ERROR;
    }
    if(i==0)
    x=S.V[S.top[0]--];
    else
    x=S.V[S.top[1]++];
    return OK;
}

int IsEmpty(Stack S,int i)
{
    if(S.top[i]==S.bot[i])
    {
        cout<<"栈空"<<endl;
    return 1;
    }
    else return 0;
}

int IsFull(Stack S)
{
    if(S.top[0]+1==S.top[1])
    {
        cout<<"栈满"<<endl;
    return 1;
    }
    else
    return 0;
}

Status printStack(Stack S,int i)
{
    if(S.top[i]==S.bot[i]) return ERROR;
    int e=0;
    if(i==0)
    {
        while(1)
        {   if(S.top[i]==S.bot[i]) break;
            e=S.V[S.top[0]];
            S.top[0]--;
            cout<<e<<" ";
                    
        }
    }
    else
     {
        while(1)
        {   if(S.top[i]==S.bot[i]) break;
            e=S.V[S.top[1]];
            S.top[1]++;
            cout<<e<<" ";
        
        }
    }
    cout<<endl;
 return OK;
}

int main()
{
    int m;
    int sum;
    Stack S;
    cout<<"输入m"<<endl;
    cin>>m;
    InitStack(S,m);
    cout<<"初始化栈0"<<endl;
    Push(S,0,1);
    Push(S,0,2);
    Push(S,0,3);
    cout<<"初始化栈1"<<endl;
    Push(S,1,1);
    Push(S,1,2);
    Push(S,1,3);
    printStack(S,0);
    printStack(S,1);
Push(S,0,1);
Push(S,0,1);
cout<<"测试删除功能："<<endl;
cout<<"删除:";
Pop(S,1,sum);
cout<<sum<<endl;
cout<<"删除:";
Pop(S,1,sum);
cout<<sum<<endl;
cout<<"删除:";
Pop(S,1,sum);
cout<<sum<<endl;
printStack(S,1);
cout<<"测试指定栈1判空功能："<<endl;
IsEmpty(S,1);
cout<<"初始化栈1"<<endl;
    Push(S,1,1);
    Push(S,1,2);
    Push(S,1,3);
cout<<"测试判满功能"<<endl;
IsFull(S);
    return 0;
}