练习3.21

问题描述：

编写一个用数组实现的两个栈的例程。除非数组的每一个单元都被使用，栈例程不能有溢出声明。

思路：

用一个结构体表示两个栈，有两个头指针，一个从头开始，另一个从末尾开始。

如果两个堆栈的头指针相邻了，就说明所有空间都被占用了，即堆栈满了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn = 120;
struct Node{
    int top1;
    int top2;
    int size;
    int *array;
};
typedef struct Node* Stack;

int IsEmpty1(Stack S)
{
    return S->top1==-1;
}

int IsEmpty2(Stack S)
{
    return S->top2==S->size;
}

int IsFull(Stack S)
{
    if(S->top2-S->top1==1) return true;
    else return false;
}

int Top1(Stack S)
{
    return S->array[S->top1];
}

int Top2(Stack S)
{
    return S->array[S->top2];
}

void Push1(int x,Stack S)
{
    if(!IsFull(S)) S->array[++S->top1]=x;
}

void Pop1(Stack S)
{
    if(!IsEmpty1(S)) S->top1--;
}

void Pop2(Stack S)
{
    if(!IsEmpty2(S)) S->top2++;
}

void Push2(int x,Stack S)
{
    if(!IsFull(S)) S->array[--S->top2]=x;
}

Stack CreateStack(int maxsize)
{
    Stack S;
    S=(Stack)malloc(sizeof(struct Node));
    if(S==NULL) printf("Out of Space!!!
");
    if(maxsize>maxn) printf("too small
");
    S->size=maxsize;
    S->array=(int*)malloc(sizeof(int)*S->size);
    if(S->array==NULL) printf("Out of Space!!!
");
    S->top1=-1;
    S->top2=S->size;
    return S;
}

int main(void)
{
    int n,x,i;
    Stack S=CreateStack(maxn);
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        Push1(x,S); 
    }
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        Push2(x,S);
    }
    while(!IsEmpty1(S))
    {
        cout<<Top1(S)<<" ";
        Pop1(S);
    }
    cout<<endl;
    
    while(!IsEmpty2(S))
    {
        cout<<Top2(S)<<" ";
        Pop2(S);
    }
    cout<<endl;
    
    return 0;
}