两栈共享空间的存储结构和入栈出栈操作-白红宇

两栈共享空间的存储结构和入栈出栈操作

阅读量：4947 次

发布时间：2019-06-11

本文共 1890 字，大约阅读时间需要 6 分钟。

参考《大话数据结构》P95~96——两栈共享存储空间。

当两个栈的需求空间有相反关系时，也就是一个栈增长时，另一个栈在缩短，可以采用两栈共享空间结构。这是针对两个具有相同数据类型的栈的一个设计技巧。

举个简单的例子：

代码和解释如下（VS2012测试通过）：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 #define MAXSIZE 6 //本例中栈满共6个元素 6 typedef string status;//本例尝试用书上推荐的status返回是否成功，C++中的模板类string比字符数组char[]更方便 7  8 //两栈共享空间的存储结构 9 typedef struct10 {11     char data[MAXSIZE];12     int top1;//栈1的栈顶所在元素的数组下标13     int top2;//栈2的栈顶所在元素的数组下标14 }SqDoubleStack;15 16 //两栈共享空间的初始化，申请内存，把栈初始化为空栈17 //返回指向SqDoubleStack结构的地址18 SqDoubleStack *InitSqDoubleStack(SqDoubleStack *s)19 {20     s=new SqDoubleStack;21     s->top1=-1;22     s->top2=MAXSIZE;23     return s;24 }25 26 //入栈27 //插入元素e为新的栈顶元素，stacknumber是栈号参数28 //因为在开始判断了是否栈满，后面的top1+1和top2-1是不担心溢出问题的29 status Push(SqDoubleStack *s,char e,int stacknumber)30 {31     if(s->top1+1==s->top2)//若栈已满，不能插入新的元素32         return "error";33     if(stacknumber==1)//栈1有元素进栈34         s->data[++s->top1]=e;//先top1加1，再给数组元素赋值35     else if(stacknumber==2)//栈2有元素进栈36         s->data[--s->top2]=e;//先top2减1，再给数组元素赋值37     return "push ok";//元素入栈成功38 }39 40 //出栈41 status Pop(SqDoubleStack *s,char *e,int stacknumber)42 {43     if(stacknumber==1)44     {45         if(s->top1==-1)//若栈1已空，没有元素出栈46             return "error";    47         *e=s->data[s->top1--];//将栈1的栈顶元素先出栈，再top1减1        48     }49     else if(stacknumber==2)50     {51         if(s->top2==MAXSIZE)//若栈2已空，没有元素出栈52             return "error";    53         *e=s->data[s->top2++];//将栈1的栈顶元素出栈，再top2加1    54     }55     return "pop ok";//元素出栈成功56 }57 58 int main()59 {60     SqDoubleStack *p=NULL;61 62     //调用初始化函数63     p=InitSqDoubleStack(p);64 65     //入栈66     cout<<"A"<<" "<
       
        <<" ";//进栈1，A67     cout<
        
         top1<
         
          top2<
          
           top1<
           
            top2<