算法提高——栈的练习

本文主要是介绍算法提高——栈的练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈的练习

题目：PAT甲级1051

一：题目描述

 给出一个大小为M的栈，现在向栈中顺序输入N个数字，这N个数字属于集合{1、2、3……N}无重复输入，在输入的过程中可以进行出栈操作，设计一个算法，要求给出K个序列，判断这些序列是否为可能的出栈序列，对于某个序列，如果该序列是可能的出栈序列则输出YES，否则输出NO

 输入的第一行分别为栈的大小，N的值，序列个数K

二、解题思路

　　自定义一个栈，然后按照题目进行模拟，将1~N依次入栈，定义一个扫描出栈序列的指针，如果入栈时栈顶元素等于指针所指元素就将栈顶元素出栈，同时后移指针。

　　如果入栈过程中，栈中元素大于M，则返回不合法，如果指针从头扫描到尾时，栈为空，则序列合法，否则不合法

三、算法描述

　　定义一个数组A用于存放出栈序列，定义一个栈S用于模拟，初始时指针current指向A[0]，开始让1~N循环入栈，每次入栈时拿入栈元素与A[current]进行比较，相同则不入栈，且current++，不同则入栈，继续下一此判断

　　当最后一次判断完毕时检查栈是否为空，如果为空则序列合法，不为空则序列不合法

　　在每次入栈后都判断栈中元素数量，可以增设count变量，每次入栈后count++，当count>M时返回不合法

　　核心代码

 关于count与m的判断，第32行代码，因为在对i和A[current]进行判断时，i没有真正入栈，但是题目对栈的大小进行了严格要求，所以按照题目要求i应该先入栈，然后出栈再判断，而我省略的入栈这步，所以栈的大小要减1。还请读者自行理解，当然也可以先进行入栈后出栈判断，那么就不需要对m-1进行判断了。

这篇关于算法提高——栈的练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！