栈的共享

超、凢脫俗 2022-07-16 13:39 196阅读 0赞

2016年7月23日14:01:33
        栈的共享:
        为什么需要共享栈?
            我们构造一个顺序栈的时候一般会分配一个很大数组空间,但通常我们只是利用了一小部分空间,
            当我们还需要定义一个顺序栈的时候,任然需要一个很大的数组空间,这时,为了更好的利用内存
            空间,我们就引入了共享栈.
        什么是共享栈?
            通过两个栈共享一个一维数组,每个栈都有一个栈顶指针,采用以迎面增长的方式,来实现一维数组的
            空间共享;
        共享栈的初始化:当定义了一个共享栈的时候,我们需要对共享栈进行初始化,来达到一种效果,
        什么效果呢?  
            让第一个栈顶指针的值为-1,另一个栈顶指针的值为STICKSIZE,这时两个栈均为空.
        当栈为空时,s->top1= -1,同时s->top2 = STICKSIZE,
        当栈为满时,假设两种极端的情形,1.s->top1 = -1,栈1为空,s->top2 = 0,栈2为满;
                                      2.s->top1 = STICKSIZE -1,栈1为满,s->top2 = STICKSIZE,栈2为空;
        因此当s->top1+1 == s->top2的时候,共享栈为满,

#include<stdio.h>
    #define STICKSIZE 100
    typedef  int  DataType ;
    
    //共享栈的结构体类型
    typedef struct  
    {
        DataType stick[STICKSIZE];
        int top1;
        int top2;
    }ShareStick;
    
    //函数前置声明
    void initStick(ShareStick * ss);//初始化共享栈
    int  getTop(ShareStick * ss,int number,DataType * element);//取栈顶元素
    int  pushStick(ShareStick * ss,int number, DataType element);//压栈
    int  popStick(ShareStick * ss, int number, DataType * element);//弹栈
    
    //初始化共享栈
    void initStick(ShareStick * ss)
    {
        ss->top1 = -1;
        ss->top2 = STICKSIZE;
        return ;
    }
    
    //取栈顶元素
    int  getTop(ShareStick * ss,int number,DataType * element)
    {
        if( 1 == number)//第一个栈
        {
            if(-1 == ss->top1)
                return 0;
            else 
            {
                *element = ss->stick[ss->top1];
                return 1;
            }
        }
        else if( 2 == number)//第二个栈
        {
            if(STICKSIZE == ss->top2)
                return 0;
            else
            {
                *element = ss->stick[ss->top2];
                return 1;
            }
        }
    }
    
    //压栈
    int  pushStick( ShareStick * ss,int number, DataType element)
    {
        if( 1 == number)//第一个栈
        {
            if(STICKSIZE-1 == ss->top1)
                return 0;
            else 
            {
                ss->top1++;
                ss->stick[ss->top1] = element;
                return 1;
            }
        }
        else if( 2 == number)//第二个栈
        {
            if(0 == ss->top2)
                return 0;
            else
            {
                ss->top2--;
                ss->stick[ss->top2] = element;
                return 1;
            }
        }
    }
    
    //出栈
    int  popStick(ShareStick * ss, int number, DataType * element)
    {
        if( 1 == number)//第一个栈
        {
            if(-1 == ss->top1)
                return 0;
            else 
            {
                *element = ss->stick[ss->top1];
                ss->top1--;
                return 1;
            }
        }
        else if( 2 == number)//第二个栈
        {
            if(STICKSIZE == ss->top2)
                return 0;
            else
            {
                *element = ss->stick[ss->top2];
                ss->top2++;
                return 1;
            }
        }
    }
    
    //主函数
    int main(void)
    {
        ShareStick ss;
        initStick(&ss);
    
        return 0;
    }