数据结构实现共享栈及其基本操作

共享栈是指两个栈共享同一片内存空间，它们在内存空间的两端分别向中间生长。共享栈的实现可以采用两个指针top1和top2分别指向两个栈顶元素的位置，初始时，top1指向栈1的栈底位置，top2指向栈2的栈底位置。

下面是共享栈的基本操作：

1. 初始化共享栈

#define MAXSIZE 100 //共享栈的最大长度
typedef struct
{
    int data[MAXSIZE]; //共享栈的元素
    int top1; //栈1的栈顶指针
    int top2; //栈2的栈顶指针
}SharedStack;
void InitStack(SharedStack *S)
{
    S->top1 = -1; //栈1的栈顶指针初始化为-1
    S->top2 = MAXSIZE; //栈2的栈顶指针初始化为MAXSIZE
}

2. 共享栈的入栈操作

bool Push(SharedStack *S, int x, int stackNumber)
{
    if (S->top1 + 1 == S->top2) //栈已满
        return false;
    if (stackNumber == 1) //入栈到栈1
        S->data[++S->top1] = x;
    else if (stackNumber == 2) //入栈到栈2
        S->data[--S->top2] = x;
    return true;
}

3. 共享栈的出栈操作

bool Pop(SharedStack *S, int *x, int stackNumber)
{
    if (stackNumber == 1) //从栈1中出栈
    {
        if (S->top1 == -1) //栈1为空
            return false;
        *x = S->data[S->top1--];
    }
    else if (stackNumber == 2) //从栈2中出栈
    {
        if (S->top2 == MAXSIZE) //栈2为空
            return false;
        *x = S->data[S->top2++];
    }
    return true;
}

4. 共享栈的取栈顶元素操作

bool GetTop(SharedStack *S, int *x, int stackNumber)
{
    if (stackNumber == 1) //取栈1的栈顶元素
    {
        if (S->top1 == -1) //栈1为空
            return false;
        *x = S->data[S->top1];
    }
    else if (stackNumber == 2) //取栈2的栈顶元素
    {
        if (S->top2 == MAXSIZE) //栈2为空
            return false;
        *x = S->data[S->top2];
    }
    return true;
}

共享栈的其他操作与普通栈类似，比如判断栈是否为空、清空栈等。