判断元素出栈,入栈顺序的合法性-创新互联
问题:元素出栈,入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,1,2)
公司主营业务:成都做网站、网站建设、外贸营销网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出张家川回族自治免费做网站回馈大家。定义一个栈sp,入栈序列为str1,出栈序列为str2,长度分别为size1和size2。如果两个序列为空或长度不等,则不合法,针对长度相等且不为空的两个序列进行判断。
先将str1中第一个元素入栈,然后通过循环使str1后移。
1、如果当前栈为空且入栈序列不为空,则入栈序列str1后移,sp入栈。
2、如果栈顶元素不等于出栈序列且入栈序列不为空,则入栈序列str1后移,sp入栈。
3、如果栈顶元素等于出栈序列,sp出栈,出栈序列str2后移。
循环比较后,如果栈为空,则出栈序列是合法的。
下面以入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,1,2)为例进行说明。
利用模板实现对象OutStack,可以判断不同类型元素出栈,入栈顺序的合法性,具体实现如下:
#includeusing namespace std; #include #include template class OutStack { public: OutStack(); OutStack(const T* str1, const T* str2, size_t size1, size_t size2); ~OutStack(); bool OutStack::Legality(); private: T* _str1; T* _str2; size_t _size1; size_t _size2; }; template OutStack ::OutStack() :_str1[NULL] , _str2[NULL] , sp(NULL) {} template OutStack ::OutStack(const T* str1, const T* str2, size_t size1, size_t size2) : _str1(new T[size1]) , _str2(new T[size2]) , _size1(size1) , _size2(size2) { memcpy(_str1, str1,(sizeof(T)*_size1));//memcpy按照字节数进行复制的 memcpy(_str2 ,str2,(sizeof(T)*_size2)); } template OutStack ::~OutStack() { if (_str1 || _str2) { delete[] _str1; delete[] _str2; } } template bool OutStack ::Legality() { T* str1 = _str1;//入栈序列 T* str2 = _str2;//出栈序列 stack sp; if (str1 && str2 && _size1 != _size2) return 0; sp.push(*str1);//先将str1中第一个元素入栈 for (size_t i = 0; i < _size1;)//将出栈序列比较完 { if (*str1 != NULL && sp.empty()) { str1++; sp.push(*str1); i++;//i和str1同步进行,直到str1进行完 } if (*str1 != NULL && sp.top() != *str2)//栈顶元素与出栈元素比较 { str1++; sp.push(*str1); i++;//i和str1同步进行,直到str1进行完 } if (sp.top() == *str2) { sp.pop(); str2++; } } if (sp.empty())//如果栈为空,则出栈序列是合法的 { return 1; } return 0; }
测试用例如下:
void Test1() { int arr1[] = { 1, 2, 3, 4, 5 };//入栈序列 int str1[] = { 4, 5, 3, 1, 2 };//出栈序列 //int str1[] = { 3, 2, 1, 5, 4 };//出栈序列 OutStacks1(arr1, str1, 5, 5); cout << s1.Legality() << endl; char* arr2 = "abcdef";//入栈序列 //char* str2 = "bafdce";//出栈序列 char* str2 = "baefdc";//出栈序列 OutStack s2(arr2, str2, 6, 6); cout << s2.Legality() << endl; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前标题:判断元素出栈,入栈顺序的合法性-创新互联
文章地址:http://pwwzsj.com/article/diegho.html