C语言实现出栈序列合法性判定
本文实例为大家分享了C语言实现出栈序列合法性判定的具体代码,供大家参考,具体内容如下
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
输入格式
第一行一个整数n,表示输入序列的长度。(1<=n<=10000)
第二行n个整数,表示栈的压入顺序。
第三行n个整数,表示栈的出栈顺序。
输出格式
如果是弹出序列,输出yes,否则输出no。
输入样例
5
1 2 3 8 6
8 6 3 2 1
输出样例
yes
准备工作:
①定义一个栈,并且实现它的基本操作(出栈popStack()/压栈pushStack()/访问栈顶元素getTop()/判断栈是否为空isEmpty()等)
②定义两个长度为10000的整形数组的,分别表示要压入顺序的数字msg以及出栈顺序的数字target.。为了避免要书写两个for循环来输入,这里可以通过调用方法input(int *arr,int len),每次输入msg/target的时候,只要调用这个方法即可,从而减少代码量。
解题思路:(主要是通过循环嵌套)
1、通过遍历msg,将遍历得到的数字压入到栈中。
2、每次压入数字之后,要获取栈顶元素ch,然后判断ch是否和当前target下标对应的数字相同,如果相同,那么就从栈中跳出一个元素,同时target的下标后移。这时候,我们依旧需要从栈中获取栈顶元素,那这个栈顶元素和当前target下标的数字进行比较,如果相等,那么继续重复上述的操作。
这里之所以需要这么做,是因为考虑到类似于压入一个元素之后,就跳出一个元素的可能,所以我们需要在target中找到相同的数字之后,不仅需要将target后移,同时需要将从栈中跳出原来的栈顶元素,然后拿新的栈顶元素和target当前下标的值进行比较,直到新的栈顶元素和target当前下标的值不相等。
3、如果不相等,那么这时候就将msg后移。重复1、2步骤。直到msg已经遍历完了。
4、这时候如果target已经遍历完了,那么就说明了target就是msg的一种出栈可能,否则,如果target没有遍历完,说明target不是msg的一种出栈可能。
图解:
完整代码(C语言):
#include<stdio.h> #define ERROR 0 #define OK 1 #define MAX_SIZE 10000 typedef struct NODE{ int arr[MAX_SIZE]; int top; }Node; void init(Node &s){ s.top = 0; } int pushElem(Node &s,int c){ if(s.top == MAX_SIZE) return ERROR; s.arr[s.top++] = c; return OK; } int popElem(Node &s,int &e){ if(s.top == 0) return ERROR; e = s.arr[--s.top]; return OK; } int getTop(Node &s,int &e){ if(s.top == 0) return ERROR; e = s.arr[s.top - 1]; return OK; } int isEmpty(Node &s){ return s.top == 0; } int testIsTrue(int *msg,int *target){ Node s; int ch; init(s); while(*msg != '\0'){ pushElem(s,*msg);//将压栈字符串中的字符压入栈中 //获取栈顶元素 getTop(s,ch); while(ch == *target){ //如果当前栈顶的字符和弹栈字符相同,那么就从栈中跳出 popElem(s,ch); target++;//弹栈字符串后移 /* //获取栈顶元素,这里之所以不用判断栈是否为空,是因为主要考虑ch是否等于target 而此时target已经后移了,所以并不会造成死循环 */ getTop(s,ch); } msg++;//当ch不等于弹栈字符串的字符的时候,那么就将后移 } if(*target != '\0') return 0; return 1; } void input(int *arr,int n){ int i; for(i = 0; i < n; i++) scanf("%d",&arr[i]); } int main(){ int msg[10000],target[10000]; int n,flag; printf("请输入栈的元素个数:"); scanf("%d",&n); input(msg,n);//调用input方法,从而输入n个数字 input(target,n); flag = testIsTrue(msg,target);//判断出栈顺序是否为压栈顺序的一种出栈可能 if(flag) printf("yes"); else printf("no"); return 0; }
运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04