共享栈

共享栈是一种特殊的栈结构，它允许两个栈共享同一段物理内存区域。共享栈有两个栈顶指针，分别称为top 1和top 2，它们分别指向两个栈的栈顶元素。在共享栈中，两个栈可以分别从两端向中间生长，当它们的栈顶指针相遇时，表示共享栈已满。

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

1. 初始化（Init）：创建一个空的共享栈，并初始化top 1和top 2指针为-1，表示两个栈为空。
2. 入栈（Push）：
   • 当要插入元素到栈1时，先检查top 1是否小于top 2-1，如果是，则将元素插入top 1位置，top 1加1。
   • 当要插入元素到栈2时，先检查top 1是否小于top 2-1，如果是，则将元素插入top 2位置，top 2减1。
3. 出栈（Pop）：
   • 当要从栈1中出栈时，首先检查top 1是否不等于-1，如果是，则将top 1位置的元素弹出，并将top 1减1。
   • 当要从栈2中出栈时，首先检查top 2是否不等于-1，如果是，则将top 2位置的元素弹出，并将top 2加1。
4. 判空（Is Empty）：检查top 1和top 2是否都为-1，如果是，则共享栈为空。
5. 判满（Is Full）：检查top 1和top 2是否相差为1，如果是，则共享栈已满。
6. 获取栈顶元素（Top）：
   • 当要获取栈1的栈顶元素时，首先检查top 1是否不等于-1，如果是，则返回top 1位置的元素。
   • 当要获取栈2的栈顶元素时，首先检查top 2是否不等于-1，如果是，则返回top 2位置的元素。

以下是共享栈的伪代码实现，包括初始化、入栈、出栈和获取栈顶元素等操作。

#define MAX_SIZE 100

typedef struct {
    ElemType data[MAX_SIZE];
    int top1;  // 第一个栈的栈顶指针
    int top2;  // 第二个栈的栈顶指针
} SharedStack;
//栈满条件：top1 + 1 = top2

// 初始化共享栈
void initSharedStack(SharedStack &S) 
{
    S.top1 = -1;
    S.top2 = MAX_SIZE;
}

// 第一个栈的入栈
bool pushStack1(SharedStack &S, ElemType x) 
{
    if (S.top1 + 1 < S.top2) 
    {//指针先加1，再入栈
        S.top1++;
        S.data[S.top1] = x;
        return true;
    }
    else 
    {
        printf("栈已满，无法进行入栈操作\n");
        return false;
    }
}

// 第一个栈的出栈
bool popStack1(SharedStack &S, ElemType &x) 
{
    if (S.top1 >= 0) 
    {//先出栈，指针再减1
        x = S.data[S.top1];
        S.top1--;
        return true;
    } 
    else 
    {
        return false; // 表示栈为空
    }
}

// 第二个栈的入栈
bool pushStack2(SharedStack &S, ElemType x) 
{
    if (S.top2 - 1 > S.top1) 
    {//指针先减1，再入栈
        S.top2--;
        S.data[S.top2] = x;
        return true;
    } 
    else 
    {
        printf("栈已满，无法进行入栈操作\n");
        return false;
    }
}

// 第二个栈的出栈
bool popStack2(SharedStack &S, ElemType &x) 
{
    if (S.top2 < MAX_SIZE) 
    {//先入栈，指针再加1
        x = S.data[S.top2];
        S.top2++;
        return true;
    }
    else 
    {
        printf("栈已空，无法进行出栈操作\n");
        return false; // 表示栈为空
    }
}

// 获取栈顶元素
void getTopElement(SharedStack S, ElemType &x) 
{
    if (S.top1 >= 0) 
    {
       return S.data[S.top1];
    } 
    else if (S.top2 < MAX_SIZE) 
    {
        return S.data[S.top2];
    } 
    else 
    {
        printf("栈已空，无栈顶元素\n");
        return false; // 表示栈为空
    }
}