元素出栈、入栈顺序的合法性【数据结构】

2021年9月3日 2点热度 0条评论 来源: CZF_csdn

元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)。

Test.c

int TestStackInAndOutValid(int* In, int InSize, int* Out, int OutSize)
{
	Stack s;
	int InIndex = 0;
	int OutIndex = 0;
	//入栈次序的大小和出栈的不相等 ,返回
	InitStack(&s);
	if (InSize != OutSize)
	{
		return 0;
	}
	//栈为空,栈顶元素与出栈次序索引标记位置元素值不相等,入栈(入栈需判断入栈索引小于入栈的次序大小)
	//出栈索引未超过边界循环上一步
	while (OutIndex < OutSize)
	{
		while (StackEmpty(&s) || TopStack(&s) != Out[OutIndex])
		{
			if (InIndex < InSize)		//入栈索引小于入栈数组的大小
				PushStack(&s, In[InIndex++]);
			else						//入栈次序的索引越界
				return 0;
		}
		//栈不为空,且栈顶和出栈次序的索引指向的元素相同
		PopStack(&s);
		OutIndex++;
	}
	return 1;
}

void TestStackValid()
{
	int tmp = 0;
	int In[] = { 1, 2, 3, 4, 5 };
	int Out[] = { 4, 5, 3, 1, 2 };
	TestStackInAndOutValid(In, 5, Out, 5);
	if (tmp)
	{
		printf("匹配成功!\n");
	}
	else
	{
		printf("匹配失败!\n");
	}
}

    原文作者:CZF_csdn
    原文地址: https://blog.csdn.net/bian_cheng_ru_men/article/details/79604897
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。