两栈共享空间

Bertha 。 2022-06-15 10:50 211阅读 0赞

两栈共享空间

栈的顺序存储只准在栈顶进出元素操作，使用起来还是很方便的，不存在线性表插入和删除时需要移动元素的问题，不足之处是必须事先确定数组空间大小。

两栈共享空间是对于两个相同类型的栈做法就是事先分配一块数组空间两个栈共同使用。

实现方法：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处，这样两个栈如果增加元素，就是两端点向中间延伸。

![Center][]

设计思路：在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，如果两个指针不碰面，说明两个栈就是处于可以使用状态。

分析：

1.      栈1为空时，就是top1等于-1；而当top2等于n时，即栈2为空；

2.      若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之当栈1为空栈时，top2等于0时，为栈2满；

3.      两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2为两栈皆满；

**一、结构**

#define MAXSIZE 50//存储空间初始化分配量
    typedef int SElemType;//此处可能是个结构体，练习使用int型足够了
     
    //两栈共享空间结构
    typedef struct
    {
             SElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
             int top1;//用于栈1栈顶指针
             int top2;//用于栈2栈顶指针
    }SqDoubleStack;

注意：两栈共享空间，一定是两个相同数据类型的栈才可以，否则反而会更加麻烦。

**二、栈顺序存储进栈操作**

**算法思路：**

1.      检查是否是满栈即栈1栈顶指针加1等于栈2栈顶指针，如果满栈返回；

2.      判断要操作哪个栈，并且将数据元素加入栈顶；

3.      如果栈1插入数据则栈顶位置计数加一，反之栈2栈顶指针减1；

**三、栈顺序存储出栈操作**

**算法思路：**

1.      检查是否是空栈，空栈则返回；

2.      判断要操作哪个栈，获取栈顶元素，删除；

3.      栈1操作则栈顶位置减一，栈2操作则栈顶指针加一；

**四、时间复杂度**

没有任何循环，时间复杂度都是O(1)。

**五、代码示例**

#include <stdio.h>
    #include <string.h>
    
    #define ERROR -1
    #define OK 0
    
    #define MAXSIZE 50//存储空间初始化分配量
    typedef int SElemType;//此处可能是个结构体，练习使用int型足够了
    
    //两栈共享空间结构
    typedef struct
    {
    	SElemType data[MAXSIZE];//数组存储数据元素，最大存储量MAXSIZE
    	int top1;//用于栈1栈顶指针
    	int top2;//用于栈2栈顶指针
    }SqDoubleStack;
    
    
    
    //初始化操作，建立一个空栈S
    voidInitStack(SqDoubleStack *S)
    {
    	memset(S,0,sizeof(SqDoubleStack));
    	S->top1 = -1;//置成空栈
    	S->top2 = MAXSIZE;//置成空栈
    }
    //若栈存在，则销毁它,因为是数组，置成空栈即可
    int DestroyStack(SqDoubleStack *S)
    {
    	if((S->top1 == -1)&&(S->top2 == MAXSIZE))
    	{
    		return ERROR;
    	}
    	InitStack(S);
    	return OK;
    }
    
    //将栈清空
    void ClearStack(SqDoubleStack *S)
    {
    	InitStack(S);
    }
    
    //若栈为空，返回true，否则返回false
    int StackEmpty(SqDoubleStackS,int stackNumber)
    {
    	if(1 == stackNumber)
    	{
    		if(S.top1 == -1)
    		{
    			return ERROR;
    		}
    	}
    	else if(2 == stackNumber)
    	{
    		if(S.top2 == MAXSIZE)
    		{
    			return ERROR;
    		}
    	}
    	else
    	{
    		return ERROR;
    	}
    	return OK;
    }
    
    //若栈存在且非空，用e返回S的栈顶元素
    int GetTop(SqDoubleStack S,SElemType *e,int stackNumber)
    {
    	if(1 == stackNumber)
    	{
    		if(S.top1 == -1)
    		{
    			return ERROR;
    		}
    		*e = S.data[S.top1];
    	}
    	else if(2 == stackNumber)
    	{
    		if(S.top2 == MAXSIZE)
    		{
    			return ERROR;
    		}
    		*e = S.data[S.top2];
    	}
    	else
    	{
    		return ERROR;
    	}
    	return OK;
    }
    
    
    //若栈存在，插入新元素e到栈S中并成为栈顶元素
    int Push(SqDoubleStack *S,SElemTypee,int stackNumber)
    {
    	if(S->top1 + 1 == S->top2)//栈满，不能再插入新元素了
    	{
    		return ERROR;
    	}
    
    	if(1 == stackNumber)//栈1有元素进栈
    	{
    		S->data[++S->top1] = e;//若栈1则先top1+1后给数组元素赋值
    	}
    	if(2 == stackNumber)//栈2有元素进栈
    	{
    		S->data[--S->top2] = e;//若栈2则先top2-1后给数组元素赋值
    	}
    	else
    	{
    		return ERROR;
    	}
    	return OK;
    }
    
    //删除S中栈顶元素，并用e返回其值
    int Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
    {
    	if(1 == stackNumber)//栈1有元素出栈
    	{
    		if(S->top1 == -1)//说明栈1是空栈，溢出
    		{
    			return ERROR;
    		}
    		*e = S->data[S->top1];//将栈1栈顶元素出栈
    		S->top1--;//栈顶指针减一
    	}
    	if(2 == stackNumber)//栈2有元素出栈
    	{
    		if(S->top2 == MAXSIZE)//说明栈2是空栈，溢出
    		{
    			return ERROR;
    		}
    		*e = S->data[S->top2];//将栈1栈顶元素出栈
    		S->top2++;//栈顶指针加一
    	}
    	else
    	{
    		return ERROR;
    	}
    
    	return OK;
    }
    
    //返回栈S的元素个数
    int StackLength(SqDoubleStack S,int stackNumber)
    {
    
    	if(1 == stackNumber)
    	{
    		return S.top1+1;//加一的原因是计数从0开始的
    	}
    	else if(2 == stackNumber)
    	{
    		return (MAXSIZE - S.top2);//加一的原因是计数从0开始的
    	}
    	else
    	{
    		return ERROR;
    	}
    }
    
    //打印栈
    int StackPrint(SqDoubleStack S,int stackNumber)
    {
    	if(1 == stackNumber)
    	{
    		if(S.top1 == -1)
    		{
    			return ERROR;
    		}
    		while(S.top1 != -1)
    		{
    			printf("栈1位置:%d 元素:%d\n",S.top1,S.data[S.top1]);
    			S.top1--;
    		}
    	}
    	else if(2 == stackNumber)
    	{
    		if(S.top2 == MAXSIZE)
    		{
    			return ERROR;
    		}
    		while(S.top2 != MAXSIZE)
    		{
    			printf("栈2位置:%d 元素:%d\n",S.top2,S.data[S.top2]);
    			S.top2++;
    		}
    	}
    	else
    	{
    		if((S.top1 == -1)&&(S.top2 == MAXSIZE))
    		{
    			return ERROR;
    		}
    		while(S.top1 != -1)
    		{
    			printf("栈1位置:%d 元素:%d\n",S.top1,S.data[S.top1]);
    			S.top1--;
    		}
    
    		while(S.top2 != MAXSIZE)
    		{
    			printf("栈2位置:%d 元素:%d\n",S.top2,S.data[S.top2]);
    			S.top2++;
    		}
    	}
    	return OK;
    }
    
    int main()
    {
    inti = 0;
    	SElemType e = 0;
    SqDoubleStack S;
    	printf("\n=======初始化操作=========\n");
    InitStack(&S);
    	printf("\n=======是否为空栈=========\n");
    	if(ERROR == StackEmpty(S,1))//空栈
    	{
    		printf("栈1是空栈插入元素\n");
    		for(i = 1;i< 5;i++)
    		{
    			Push(&S,i,1);
    		}
    	}
    
    	if(ERROR == StackEmpty(S,2))//空栈
    	{
    		printf("栈1是空栈插入元素\n");
    		for(i = 1;i< 5;i++)
    		{
    			Push(&S,i+10,2);
    		}
    	}
    	printf("\n======打印栈1信息=========\n");
    	StackPrint(S,1);
    	printf("\n======打印栈2信息=========\n");
    	StackPrint(S,2);
    	printf("\n======打印栈信息=========\n");
    	StackPrint(S,0);
    
    	printf("\n=======获取栈长度========\n");
    	printf("栈1长度:%d\n",StackLength(S,1));
    	printf("栈2长度:%d\n",StackLength(S,2));
    	printf("\n=====获取栈顶元素========\n");
    	GetTop(S,&e,1);
    	printf("栈1栈顶元素:%d\n",e);
    	GetTop(S,&e,2);
    	printf("栈2栈顶元素:%d\n",e);
    
    	printf("\n=====删除栈顶元素========\n");
    	Pop(&S,&e,1);
    	printf("删除1栈顶元素:%d\n",e);
    	Pop(&S,&e,2);
    	printf("删除2栈顶元素:%d\n",e);
    	printf("\n======打印栈信息=========\n");
    	StackPrint(S,0);
    
    	printf("\n=====清空并销毁栈========\n");
    	ClearStack(&S);
    	DestroyStack(&S);
    	if(ERROR == StackEmpty(S,1))//空栈
    	{
    		printf("1空栈\n");
    	}
    
    	if(ERROR == StackEmpty(S,2))//空栈
    	{
    		printf("2空栈\n");
    	}
    return 0;
    }

[Center]: /images/20220615/d2a42a2f59ad4214a91deb2ea0ec35f7.png