数据结构两栈共享空间

末蓝、 2022-05-28 03:18 199阅读 0赞

做一个豁达而努力的自己。

两栈共享空间的存储结构：

#define MAXSIZE 100
    typedef struct
    {
        SElemType data[MAXSIZE];    //用以存储数据
        int top1;   //栈1的栈顶
        int top2:   //栈2的栈顶
    }SqDoubleStack;

初始化：

void InitDouStack(SqDoubleStack &s)
    {
        s.top1 = -1;    //初始时栈1下标为-1，因为没有元素
        s.top2 = MAXSIZE;   //初始时栈2下标为MAXSIZE，
    }

清除：

void ClearDouStack(SqDoubleStack &s)
    {
        //跟初始化一样
        s.top1 = -1;
        s.top2 = MAXSIZE;
    }

求双栈的长度：

int DouStackLength(SqDoubleStack s)
    {
        return s.top1 + 1 +(MAXSIZE - s.top2);
    }

判断双栈是否为空：

Status EmptyDouStack(SqDoubleStack s)
    {
        if(s.top1 == -1 && s.top2 == MAXSIZE)
            return TRUE;
        return FALSE;
    }

压栈：

Status Push(SqDoubleStack &s, SElemType e, int stacknumber)
    {
        if(s.top1 + 1 == s.top2)
            return ERROR;
        if(stacknumber == 1)
            s.data[++s.top1] = e;
        else if(stacknumber == 2)
            s.data[--s.top2] = e;
        return OK;
    }

弹栈：

Status Pop(SqDoubleStack &s, SElemType &e, int stacknumber)
    {
        if(stacknumber == 1)
        {
            if(s.top1 == -1)
                return FALSE;
            e = s.data[s.top1--];
        }
        else if(stacknumber == 2)
        {
            if(s.top2 == MAXSIZE)
                return FALSE;
            e = s.data[s.top2++];
        }
        return OK;
    }

打印：

void PrintDouStack(SqDoubleStack s)
    {
        int i;
        i = 0;
        while(i <= s.top1)
            cout << s.data[s.top1--] << '\t';
        i = s.top2;
        while(i < MAXSIZE)
            cout << s.data[s.top2] << '\t';
        cout << endl;
    }

代码：

#include <iostream>
    #include <cstdlib>
    using namespace std;
    #define MAXSIZE 100
    
    //两栈共享空间的存储结构
    typedef struct
    {
        int data[MAXSIZE];
        int top1;   //栈1的栈顶指针
        int top2;   //栈2的栈顶指针
    }SqDoubleStack;
    //共享双栈的初始化
    void InitDouStack(SqDoubleStack &s)
    {
        s.top1 = -1;
        s.top2 = MAXSIZE;
    }
    //清除共享双栈
    void ClearDouStack(SqDoubleStack &s)
    {
        s.top1 = -1;
        s.top2 = MAXSIZE;
    }
    //判断共享双栈是否为空
    bool EmptyDouStack(SqDoubleStack s)
    {
        if(s.top1 == -1 && s.top2 == MAXSIZE)
            return true;
        return false;
    }
    //共享双栈的长度
    int DouStackLength(SqDoubleStack s)
    {
        return s.top1 + 1 + (MAXSIZE - s.top2);
    }
    //压栈
    bool Push(SqDoubleStack &s, int e, int stacknumber)
    {
        if(s.top1 + 1 == s.top2)
            return false;   //栈满
        if(stacknumber == 1)
            s.data[++s.top1] = e;
        else if(stacknumber == 2)
            s.data[--s.top2] = e;
        return true;
    }
    //弹栈
    bool Pop(SqDoubleStack &s, int &e, int stacknumber)
    {
        if(stacknumber == 1)
        {
            if(s.top1 == -1)
                return false;
            e = s.data[s.top1--];
        }
        else if(stacknumber == 2)
        {
            if(s.top2 == MAXSIZE)
                return false;
            e = s.data[s.top2++];
        }
        return true;
    }
    //打印共享双栈
    void PrintDouStack(SqDoubleStack s)
    {
        int i;
        i = 0;
        while(i <= s.top1)
            cout << s.data[i++] << '\t';
        i = s.top2;
        while(i < MAXSIZE)
            cout << s.data[i++] << '\t';
        cout << endl;
    }
    int main()
    {
        SqDoubleStack s;
        InitDouStack(s);    //初始化
        cout << "输入5个元素" << endl;
        int e;
        for(int i = 1; i <=5; i++)
        {
            int n;
            cout << "请选择如1或2号栈:";
            cin >> n;
            cout << "输入数据:";
            cin >> e;
            if(Push(s, e, n))
                ;
            else
                exit(1);
        }
        PrintDouStack(s);
        if(EmptyDouStack(s))
            cout << "为空" << endl;
        else
            cout << "不为空" << endl;
        cout << "长度为:" << DouStackLength(s) << endl;
        cout << "弹出两个元素" << endl;
        for(int i = 1; i <= 2; i++)
        {
            int n;
            cout << "选择弹出的位置:";
            cin >> n;
            if(Pop(s, e, n))
                cout << "弹出的元素是:" << e << endl;
            else
                exit(1);
        }
        PrintDouStack(s);
        cout << "长度为:" << DouStackLength(s) << endl;
        ClearDouStack(s);
        cout << "清除操作" << endl;
        if(EmptyDouStack(s))
            cout << "为空" << endl;
        else
            cout << "不为空" << endl;
        cout << "长度为:" << DouStackLength(s) << endl;
        return 0;
    }