判断元素出栈、入栈顺序的合法性

ゝ一纸荒年。 2022-06-12 11:39 227阅读 0赞

元素出栈、入栈顺序的合法性。

如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1），则合法。入栈的序列（1,2,3,4,5），出栈序列为（4,5,2,3,1），则不合法。

定义一个栈s，入栈序列为dataPush，出栈序列为dataPop及dataPop2，长度分别为len1和len2, len3。

在判断的方法中，如果两个序列为空或长度不等，则不合法，出栈序列和入栈序列必须长度相等且不为空才能进行判断。  
先将dataPush中第一个元素入栈，然后通过循环使dataPush后移。  
如果当前栈为空且入栈序列不为空，则入栈序列dataPush后移，s入栈。  
如果栈顶元素不等于出栈序列元素且入栈序列不为空，则入栈序列dataPush后移，s入栈。  
如果栈顶元素等于出栈序列元素，则s出栈，出栈序列dataPop后移。  
循环比较后，如果栈为空，则出栈序列是合法的,否则不合法。

代码：

#include<iostream>
    #include<stack>
    #include<assert.h>
    using namespace std;
    bool CheckPopOrder(int dataPush[], int dataPop[], int Push_len, int Pop_len)
    {
    	assert(dataPush && dataPop);
    	if(Push_len != Pop_len && Push_len > 0)
    	{
    		return false;
    	}
    
    	stack<int> s;
    	int i = 0;
    	int j = 0;
    	for( ; i < Push_len; i++)
    	{
    		s.push(dataPush[i]);
    		while(s.size() > 0 && s.top() == dataPop[j])
    		{
    			s.pop();
    			j++;
    		}
    	}
    	return s.size() > 0 ? false : true;
    }
    
    int main()
    {
    	int dataPush[] = {1, 2, 3, 4, 5};
    	int dataPop[] = {4, 5, 3, 2, 1};
    	int dataPop2[] = {4, 5, 2, 3, 1};
    	int len1 = sizeof(dataPush)/sizeof(dataPush[0]);
    	int len2 = sizeof(dataPop)/sizeof(dataPop[0]);
    	int len3 = sizeof(dataPop2)/sizeof(dataPop2[0]);
    	cout<< CheckPopOrder(dataPush, dataPop, len1, len2) << endl;
    	cout<< CheckPopOrder(dataPush, dataPop2, len1, len3) << endl;
    
    	return 0;
    }