现在的位置: 首页 > 综合 > 正文

第二十一题 栈的输入输出是否符合栈的规则

2018年04月13日 ⁄ 综合 ⁄ 共 1190字 ⁄ 字号 评论关闭

题目:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。

比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

//判断输入输出是否符合栈的规则
#include <iostream>
#include <stack>
using namespace std;
bool isstack(int *pushstr,int *popstr,int length)
{
    
	if (pushstr==nullptr||popstr==nullptr||length<=0)
	{
		return false;
	}
	bool ismstack=false;
	stack<int> stackdata;//辅助栈
	int *m_nextpush=pushstr;//输入栈中的数据
	int *m_nextpop=popstr;//输出栈中的数据
	stackdata.push(*m_nextpush);//给辅助栈一个初值
	while (m_nextpop-popstr<length)
	{
		//判断栈顶元素是否与输出数组中的数相等,不等的话则继续输入
		while (*m_nextpop!=stackdata.top())
		{
			if (m_nextpush-pushstr<length-1)
			{
				m_nextpush++;
				stackdata.push(*m_nextpush);
			}
			//输入数组已经全部输入进去
			else
			{
				m_nextpush==nullptr;
				break;
			}	
		}
		//若与栈顶元素相等,将栈顶元素pop出去,表示已经输出了一个数,输出数组指针+1,指向下一个输出的数,
		if (*m_nextpop==stackdata.top())
		{
			stackdata.pop();
			m_nextpop++;
		}
		else
		{
			break;
		}
	}
	//当输出数组中所有的数都已经输出后,辅助栈的为空时则是正确的
	if (stackdata.empty()&&m_nextpop-popstr==length)
	{
		ismstack=true;
	}
	return ismstack;
}
int main()
{
	int m_push[5]={1,2,3,4,5};
	int m_pop[5]={4,5,3,2,1};
	bool c=false;
	c=isstack(m_push,m_pop,5);
	if (c==true)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

抱歉!评论已关闭.