数据结构与算法分析 3.21 — 一个数组实现两个栈

问题：仅仅使用一个数组实现两个栈的例程；除非数组每个单元都被使用，否则不能出现溢出声明。

思路：

          假设存在两个栈P与Q，栈P以数组首地址为栈头，其从数组头向数组尾部增长；

          栈Q以数组尾部为栈尾，其从数组尾部向头部增长。

代码：

struct Node;
typedef Node *ComStack;
struct Node
{
    int capacity;
    int topL;
    int topR;
    ElementType *array;
};

ComStack CreatComStack(int maxElements);
int IsEmpty_L(ComStack S);
int IsEmpty_R(ComStack S);
int IsFull(ComStack S);
void MakeEmpty(ComStack S);
void Push_L(ElementType X, ComStack S);
void Push_R(ElementType X, ComStack S);
ElementType Pop_L(ComStack S);
ElementType Pop_R(ComStack S);
void DisposeComStack(ComStack S);

ComStack CreatComStack(int maxElements)
{
    ComStack S;

    S = (ComStack)malloc(sizeof(struct Node));
    if (S == NULL)
    {
        printf("Out of space");
        return NULL;
    }
    S->array = (ElementType *)malloc(sizeof(ElementType) * maxElements);
    if (S->array == NULL)
    {
        printf("Out of space");
        return NULL;
    }
    S->capacity = maxElements;
    MakeEmpty(S);
    return S;
}

int IsEmpty_L(ComStack S)
{
    if (S->topL == -1)
        return true;
    else
        return false;
}

int IsEmpty_R(ComStack S)
{
    if (S->topR == S->capacity)
        return true;
    else
        return false;
}

int IsFull(ComStack S)
{
    if (S->topL + 1 == S->topR)
        return true;
    else
        return false;
}

void MakeEmpty(ComStack S)
{
    /* Capacity在数组界外 */
    S->topL = -1;
    S->topR = S->capacity;
}

void Push_L(ElementType X, ComStack S)
{
    if (IsFull(S))
        printf("Stack is full");
    else
    {
        S->topL++;
        S->array[S->topL] = X;
    }
}

void Push_R(ElementType X, ComStack S)
{
    if (IsFull(S))
        printf("Stack is full");
    else
    {
        S->topR--;
        S->array[S->topR] = X;
    }
}

ElementType Pop_L(ComStack S)
{
    ElementType TmpCell;

    if (IsEmpty_L(S))
        printf("Left Stack is empty");
    else
    {
        TmpCell = S->array[S->topL];
        S->topL--;
    }
    return TmpCell;
}

ElementType Pop_R(ComStack S)
{
    ElementType TmpCell;

    if (IsEmpty_R(S))
        printf("Right stack is empty");
    else
    {
        TmpCell = S->array[S->topR];
        S->topR++;
    }
    return TmpCell;
}

void DisposeComStack(ComStack S)
{
    if (S != NULL)
    {
        free(S->array);
        free(S);
    }
}