两栈共享存储空间算法

痛定思痛。 2022-06-03 10:05 208阅读 0赞

我们知道栈是一种先进后出的结构，我们用顺序存储结构进行实现，也是很方便的，唯一的缺陷就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段扩展数组容量，非常麻烦。对于一个栈，我们只能经理设计出合适大小的数组进行处理，但是对于2个相同类型的栈，我们可以**共享其存储空间**，最大限度的利用事先开辟的存储空间进行操作。

![Center][]

关键思路：他们是数组的两端，向中间靠拢。top1和top2是栈和栈2的栈顶指针，可以想象，只要他们俩不见面，2个栈就可以一直使用。2栈见面时，也就是2个指针之间相差1时，即top1+1 == top为栈满。

对于2栈共享空间的**push**方法，我们除了要插入元素值参数外，我们还需要判断是栈1还是栈2的栈号参数stackNumber.注意：先判断栈满没有，先栈顶top+1后，然后在相应栈顶赋值。

对于2栈共享空间**pop**方法，参数就只需判断栈1和栈2 ，空栈返回ERROR，然后相应栈顶元素出栈，然后top-1。

2栈共享空间相关代码如下：

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    
    #define MAXSIZE 100
    #define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    typedef int EleType;
    typedef int Status;
    //2栈共享存储空间 数据结构
    typedef struct SeqDoubleStack 
    {
    	EleType data[MAXSIZE];
    	int top1;
    	int top2;
    
    }SeqDoubleStack;
    /*
    弹栈
    */
    Status pop(SeqDoubleStack* stack,EleType *e,int stackNum)
    {
    	if (!stack || !e)//空指针
    	{
    		return ERROR;
    	}
    	
    	//栈不为空的情况，根据栈编号，pop相应的栈的元素。
    	//栈1空栈判断stack->top1!=-1 栈2空栈判断stack->top2 != MAXSIZE
    	if (stackNum == 1&&stack->top1!=-1)
    	{
    		*e = stack->data[stack->top1];
    		stack -> top1--;
    		return OK;
    	}
    	if (stackNum == 2 && stack->top2 != MAXSIZE)
    	{
    		*e = stack->data[stack->top2];
    		stack->top2++;
    		return OK;
    	}
    	//栈为空或者编号不对
    	return ERROR;
    }
    /*
    压栈操作
    */
    Status push(SeqDoubleStack* stack, EleType e, int stackNum)
    {
    	if (!stack)//空指针
    	{
    		return ERROR;
    	}
    
    	//栈没有满的情况，根据栈编号，push相应的栈的元素。
    	//栈未满的条件都是stack->top1+1 < stack->top2
    	if (stackNum == 1 && stack->top1+1 < stack->top2)
    	{
    		stack->top1++;
    		stack->data[stack->top1] = e;
    		return OK;
    	}
    	if (stackNum == 2 && stack->top1 + 1 < stack->top2)
    	{
    		stack->top2--;
    		stack->data[stack->top2] = e;
    		return OK;
    	}
    	//栈已满或者编号不对
    	return ERROR;
    }
    
    /*
    展示2个栈的元素
    */
    void showStack(SeqDoubleStack* stack)
    {
    	for (int i = 0; i <= stack->top1; i++)
    	{
    		printf("%d,",stack->data[i]);
    	}
    	for (int i = stack->top2; i <= MAXSIZE - 1; i++)
    	{
    		printf("%d,", stack->data[i]);
    	}
    	printf("\n");
    }
    /*
    清空栈元素
    */
    Status clearSeqDoubleStack(SeqDoubleStack* stack)
    {
    	if (!stack)
    	{
    		return ERROR;
    	}
    	stack->top1 = -1;
    	stack->top2 = MAXSIZE;
    	return OK;
    }
    /*
    初始化栈
    */
    Status initSeqDoubleStack(SeqDoubleStack* stack)
    {
    	if (!stack)
    	{
    		return ERROR;
    	}
    	stack->top1 = -1;
    	stack->top2 = MAXSIZE;
    	return OK;
    }
    /*
    栈元素个数
    */
    int getLengthSeqDoubleStack(SeqDoubleStack* stack)
    {
    	if (!stack)
    	{
    		return ERROR;
    	}
    	//stack->top1+1;//栈1元素个数
    	//MAXSIZE - stack->top2;//栈2元素个数
    	return stack->top1 + 1 + MAXSIZE - stack->top2;
    }
    int main(int argc, char *argv[])
    {
    	SeqDoubleStack stack;
    	//初始化
    	initSeqDoubleStack(&stack);
    	//压栈
    	push(&stack, 1, 1);
    	push(&stack, 2, 1);
    	push(&stack, 3, 1);
    	push(&stack, 4, 1);
    	push(&stack, 5, 1);
    	push(&stack, 9, 2);
    	push(&stack, 8, 2);
    	push(&stack, 7, 2);
    	push(&stack, 6, 2);
    	puts("展示元素:");
    	//显示元素
    	showStack(&stack);
    	printf("元素个数：%d\n", getLengthSeqDoubleStack(&stack));
    	EleType e1;
    	EleType e2;
    	//弹栈
    	pop(&stack, &e1,1);
    	printf("pop:%d,",e1);
    	pop(&stack,&e2,2);
    	printf("pop:%d\n", e2);
    	puts("展示元素:");
    	showStack(&stack);
    	//清空
    	clearSeqDoubleStack(&stack);
    	printf("\n");
    	return 0;
    }

验证结果截图：

![Center 1][]

事实上，使用这样的数据结构，通常都是2个栈的空间需求有相反关系时，也就是一个栈增长时，另一个栈在缩短，就像买股票一样，你买入时，一定有人在做卖出操作。这才2栈共享空间存储方法才有比较大的意义。这是针对2个相同类型的栈的一种设计技巧。

[Center]: /images/20220603/dd832edba8aa44918a9585b80385d474.png
[Center 1]: /images/20220603/11fba820801147e09e5b05f483cc8ceb.png