【数据结构】之两栈共享空间（C语言）

迈不过友情╰ 2023-02-14 05:47 20阅读 0赞

### 文章目录 ###

*   *   *  引言
         *  实现之两栈共享空间
         *   *  插入元素
             *  删除元素
             *  完整代码

### 引言 ###

栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过栈有一个比较大的缺陷，就是必须事先确定数组存储空间的大小。万一不够用，就需要手动编程来扩展数组的容量，非常麻烦。对于一个栈，我们也尽可能考虑周全，设计出合适大小的数组来处理，单相对于两个相同类型的栈，我们却可以做到极大限度的利用其事先开辟的存储空间来进行操作。

打个比方，两个大学室友毕业同时到北京工作，开始时，他们觉得住了这么多年学校的集体宿舍，现在工作了-要有自己的私密空间。于是他们都希望租房时能找到独住的一居室，可找来找去却发现，最便宜的一居室也要每月1500 元，地段还不好，实在是承受不起，最终他俩还是合租了一套两居室，-一共2000元，各出一半，还不错。  
对于一个两居室，都有独立的卫生间和厨房，是私密了，但大部分空间的利用率却不高。而两居室，两个人各有卧室，还共享了客厅，厨房和卫生间，房间的利用率就显著提高，而且租房成本也下降了。

同样的道理，如果我们有两个相同类型的栈，我们为了他们各自开辟了数组空间，极有可能是第一个栈满了，在进栈就溢出了，而另外一个栈还有很多存储空间空闲，**这时候我们可以用一个数组存储两个栈。**

### 实现之两栈共享空间 ###

数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的低端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处，这样，如果两个栈增加元素，就是两端点向中间延伸。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]其关键思路就是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们两不见面，两个栈就可以一直使用。  
栈1为空时，就是top1 = -1，top2等于n时，栈2就是空栈。

极端的情况：栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之栈1为空栈，top2等于0时，为栈2满。但是在更多的情况下，就是两个栈见面之时，也就是两个指针之间相差1，top1 +1 ==top2为栈满。

//两栈共享空间结构
    typedef struct
    {
        
    	SElemType data[MAXSIZE];
    	int top1;  //栈1栈顶指针
    	int top2;	//栈2栈顶指针
    }SqDoubleStack

#### 插入元素 ####

对于两栈共享空间的push方法，我们除了要插入元素值之外，还需要判断是栈1还是栈2的栈号参数。

/* 插入元素e为新的栈顶元素 */
    Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
    {
        
            if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
                    return ERROR;	
            if (stackNumber==1)			/* 栈1有元素进栈 */
                    S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
            else if (stackNumber==2)	/* 栈2有元素进栈 */
                    S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
            return OK;
    }

#### 删除元素 ####

对于删除，就是判断栈1和栈2的stackNumber。

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
    Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
    {
         
            if (stackNumber==1) 
            {
        
                    if (S->top1==-1) 
                            return ERROR; /* 说明栈1已经是空栈，溢出 */
                    *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
            }
            else if (stackNumber==2)
            {
         
                    if (S->top2==MAXSIZE) 
                            return ERROR; /* 说明栈2已经是空栈，溢出 */
                    *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
            }
            return OK;
    }

事实上，使用这样的数据结构，通常就是当连个栈的空间需求有相反关系时，也就是一个栈增长是，另外一个栈在缩短的情况。

#### 完整代码 ####

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20 /* 存储空间初始分配量 */
    
    typedef int Status; 
    
    typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
    
    
    /* 两栈共享空间结构 */
    typedef struct 
    {
        
            SElemType data[MAXSIZE];
            int top1;	/* 栈1栈顶指针 */
            int top2;	/* 栈2栈顶指针 */
    }SqDoubleStack;
    
    
    Status visit(SElemType c)
    {
        
            printf("%d ",c);
            return OK;
    }
    
    /*  构造一个空栈S */
    Status InitStack(SqDoubleStack *S)
    {
         
            S->top1=-1;
            S->top2=MAXSIZE;
            return OK;
    }
    
    /* 把S置为空栈 */
    Status ClearStack(SqDoubleStack *S)
    {
         
            S->top1=-1;
            S->top2=MAXSIZE;
            return OK;
    }
    
    /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
    Status StackEmpty(SqDoubleStack S)
    {
         
            if (S.top1==-1 && S.top2==MAXSIZE)
                    return TRUE;
            else
                    return FALSE;
    }
    
    /* 返回S的元素个数，即栈的长度 */
    int StackLength(SqDoubleStack S)
    {
         
            return (S.top1+1)+(MAXSIZE-S.top2);
    }
    
    /* 插入元素e为新的栈顶元素 */
    Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
    {
        
            if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
                    return ERROR;	
            if (stackNumber==1)			/* 栈1有元素进栈 */
                    S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
            else if (stackNumber==2)	/* 栈2有元素进栈 */
                    S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
            return OK;
    }
    
    /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
    Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
    {
         
            if (stackNumber==1) 
            {
        
                    if (S->top1==-1) 
                            return ERROR; /* 说明栈1已经是空栈，溢出 */
                    *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
            }
            else if (stackNumber==2)
            {
         
                    if (S->top2==MAXSIZE) 
                            return ERROR; /* 说明栈2已经是空栈，溢出 */
                    *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
            }
            return OK;
    }
    
    Status StackTraverse(SqDoubleStack S)
    {
        
            int i;
            i=0;
            while(i<=S.top1)
            {
        
                    visit(S.data[i++]);
            }
            i=S.top2;
            while(i<MAXSIZE)
            {
        
                    visit(S.data[i++]);
            }
            printf("\n");
            return OK;
    }
    
    int main()
    {
        
            int j;
            SqDoubleStack s;
            int e;
            if(InitStack(&s)==OK)
            {
        
                    for(j=1;j<=5;j++)
                            Push(&s,j,1);
                    for(j=MAXSIZE;j>=MAXSIZE-2;j--)
                            Push(&s,j,2);
            }
    
            printf("栈中元素依次为：");
            StackTraverse(s);
    
            printf("当前栈中元素有：%d \n",StackLength(s));
    
            Pop(&s,&e,2);
            printf("弹出的栈顶元素 e=%d\n",e);
            printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
    
            for(j=6;j<=MAXSIZE-2;j++)
                    Push(&s,j,1);
    
            printf("栈中元素依次为：");
            StackTraverse(s);
    
            printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));
    
            
            ClearStack(&s);
            printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
            
            return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200601095148617.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70