两栈共享空间

1.如果有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空间。
2.所以我们可以使用一个数组来存储两个栈。
3.具体做法如下：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处
这样，两个栈如果增加元素，就是两端点向中间延伸
与上一遍顺序栈的程序不同的是，此处采用下标记录栈顶位置，而非指针，且并没有指向栈顶的下一个存储空间
如下图所示：

两栈共享空间
下面实现两栈共享空间的操作：

SqDoubleStack.h

#pragma once
#define MAXSIZE 20
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int SElemType;

typedef struct
{
    SElemType* data;
    int top1;
    int top2;
}SqDoubleStack;

//顺序栈初始化
Status InitSqDoubleStack(SqDoubleStack& S);

//判断顺序栈是否为空
bool StackEmpty(SqDoubleStack S);

//求顺序栈长度
int StackLength(SqDoubleStack S);

//清空顺序栈
Status ClearStack(SqDoubleStack& S);

//销毁顺序栈
Status DestroyStack(SqDoubleStack& S);

//顺序栈入栈
Status Push(SqDoubleStack& S, SElemType e, int stackNumber);

//顺序栈出栈
Status Pop(SqDoubleStack& S, SElemType& e, int stackNumber);

//遍历顺序栈
void StackTraverse(SqDoubleStack S);

SqDoubleStack.cpp

#include <iostream>
#include "SqDoubleStack.h"

using namespace std;

//顺序栈初始化
Status InitSqDoubleStack(SqDoubleStack& S)
{
    S.data = new SElemType[MAXSIZE];    //申请内存
    if (!S.data)                        //申请失败
    {
        cout << "初始化失败" << endl;
        exit(OVERFLOW);
    }
    S.top1 = -1;
    S.top2 = MAXSIZE;
    return OK;
}

//清空顺序栈
Status ClearStack(SqDoubleStack& S)
{
    S.top1 = -1;
    S.top2 = MAXSIZE;
    return OK;
}

//销毁顺序栈
Status DestroyStack(SqDoubleStack& S)
{
    if (S.data)             //如果栈存在
    {
        delete S.data;

        S.data = NULL;
    }
    return OK;
}

//判断顺序栈是否为空
bool StackEmpty(SqDoubleStack S)
{
    if (S.top1 == -1 && S.top2 == MAXSIZE)
    {
        return true;
    }
    return false;
}

//求顺序栈长度
int StackLength(SqDoubleStack S)
{
    return (S.top1 + 1) + (MAXSIZE - S.top2);
}

//顺序栈入栈
Status Push(SqDoubleStack& S, SElemType e, int stackNumber)
{
    if (S.top1 + 1 == S.top2)   //先判断是否栈满
    {
        cout << "栈满，入栈失败" << endl;
        return ERROR;
    }
    if (stackNumber == 1)       //如果要入栈1
    {
        S.top1++;               //下标移动
        S.data[S.top1] = e;
        return OK;
    }
    else if (stackNumber == 2)  //如果要入栈1
    {
        S.top2--;               //下表移动
        S.data[S.top2] = e;
        return OK;
    }
    else
    {
        cout << "输入有误，请输入1或2" << endl;
        return ERROR;
    }
}

//顺序栈出栈
Status Pop(SqDoubleStack& S, SElemType& e, int stackNumber)
{
    if (stackNumber == 1)           //如果要出栈1
    {
        if (S.top1 == -1)           //判断栈1是否为空
        {
            cout << "栈1为空" << endl;
            return ERROR;
        }
        e = S.data[S.top1];
        S.top1--;
        return OK;
    }
    else if (stackNumber == 2)
    {
        if (S.top2 == MAXSIZE)
        {
            cout << "栈2为空" << endl;
            return ERROR;
        }
        e = S.data[S.top2];
        S.top2++;
        return OK;
    }
    else
    {
        cout << "输入有误，请输入1或2" << endl;
        return ERROR;
    }

    return OK;
}

//遍历顺序栈
void StackTraverse(SqDoubleStack S)
{
    int p1 = S.top1, p2 = S.top2;

    //遍历栈1
    while (p1 >= 0)
    {
        cout << S.data[p1] << " ";
        p1--;
    }
    cout << endl;

    //遍历栈2
    while (p2 < MAXSIZE)
    {
        cout << S.data[p2] << " ";
        p2++;
    }
    cout << endl;
}

main.cpp

测试：

#include <iostream>
#include "SqDoubleStack.h"
using namespace std;

int main(int argc, char** argv)
{
    SqDoubleStack S;
    InitSqDoubleStack(S);   //初始化栈

    Push(S, 1, 1);          //入栈
    Push(S, 2, 1);
    Push(S, 3, 1);

    Push(S, 1, 2);
    Push(S, 2, 2);
    Push(S, 3, 2);

    StackTraverse(S);       //遍历

    cout << "栈长度：" << StackLength(S) << endl;

    SElemType e;

    Pop(S, e, 1);           //出栈
    cout << "栈1弹出：" << e << endl;
    Pop(S, e, 2);
    cout << "栈2弹出：" << e << endl;
    Pop(S, e, 1);
    Pop(S, e, 1);
    Pop(S, e, 2);
    Pop(S, e, 2);           //元素全部弹出

    if (StackEmpty(S))      //判断栈空
    {
        cout << "栈空" << endl;
    }

    Pop(S, e, 1);           //栈已为空
    Pop(S, e, 2);

    return 0;
}