算法习题29：栈的push、pop序列是否一致

栈的push、p op序列

题目：输入两个整数 序列。其中一个序列表示栈的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，p op，pop，pop，

这样得到的pop序列就是4、5、3、2、1。

但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

----------------------------------------------------------------------------

方法一：用栈模拟过程

这道题其实第一个方法大家可以很快想到，我们不妨模拟这个栈，自己写一个栈的push pop然后根据pop序列来模拟pop过程

例如：

Push：1 2 3 4 5 

Pop: 4 5 3 2 1

我们先得到pop的第一个元素是4，然后我们开始push,直到Push(4)的时候，我们知道，这里要把4pop出来，

然后移动pop序列到下一个元素5，我们先检查此时的栈顶元素3是不是Pop元素，当然不是，所以继续push，这时候push进来的正是5，然后移动Pop到下一个元素，是3，此时栈顶元素就是3，然后pop(3)接下来过程就很好理解了，所以 模拟一个栈的方法是可以的。

————————————

这里插入个注意事项：

1、什么时候停止？或者说什么时候能够判断这个pop就是push对应的呢？一定要把push都push完才算还是Pop遍历完才算？

当然是pop遍历结束就可以了，例如

push: 1 2 3 4 

pop: 4 3

你说这个是不是对应的push pop？当然是，因为Pop序列是可以从push中得到的！

2、如果发现某个元素根本就不再push序列里，就可以停止了！

——————————

方法2：不用栈，采用逻辑模拟

这里可以采用数组来模拟栈，我下面给的程序就是这个过程，push_num表示栈顶指针

同样，先得到pop第一个元素，然后根据改元素值在push中找到，然后将该元素push，我这里假设为-1，然后找下一个pop元素，

因为此时被Push的元素只有两种可能，一个是刚被push元素的前一个元素，要们就是后面push的某个元素，所以遵循这个过程找下一个

比较上面两个方法，第一种方法时间复杂度可以看成是O(N)是用空间换来的O(2N)

第二种方法则在时间复杂度上达到O(N^2)所以。。。

//============================================================================
// Name        : PushPop.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string.h>
using namespace std;

#define MAX 100

int Input(int arr[]);
void Output(int arr[], int num);
bool PushPop(int* push, int push_num, int* pop, int pop_num);

int main() {
	int push[MAX];
	int pop[MAX];
	int push_num=-1, pop_num=-1;

	push_num = Input(push);
	pop_num = Input(pop);

	if(PushPop(push, push_num, pop, pop_num))
		cout<<"yes";
	else
		cout<<"no";

	cout<<endl;
	Output(push, push_num);
	Output(pop, pop_num);

	return 0;
}

bool PushPop(int* push, int push_num, int* pop, int pop_num){
	int i =0,j = 0;

	while(j<pop_num){
		//向前找一个,就是找当前栈顶元素是不是Pop对应的
		if(i>0){
			while(i>0 && push[i]==-1)
				i--;
			if(i>=0 && push[i]!=-1){
				if(push[i]==pop[j]){
					//把前一个再pop出来了
					push[i]=-1;
					j++;
					continue;
				}
			}
		}
		//向后找
		while(i<push_num && push[i]!=pop[j])
			i++;
		if(i<push_num && push[i]==pop[j]){
			push[i] = -1;
		}else{
			cout<<i<<" "<<j<<endl;
			return false;
		}
		j++;
	}
	return true;
}

int Input(int arr[]){
	int num = -1;
	int input;
	while(true){
		num++;
		cin>>input;
		if(input!=-1)
			arr[num] = input;
		else
			break;
	}
	return num;
}

void Output(int arr[], int num){
	int i = 0 ;
	for(;i<num;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
           

测试：

1 2 3 4 5 -1
3 7 -1
5 1
no
1 2 -1 4 5 
3 7 
           

1 2 3 4 5 -1
3 2 1 -1
yes
-1 -1 -1 4 5 
3 2 1 
           

1 2 3 4 5 -1
4 5 3 2 1 -1
yes
-1 -1 -1 -1 -1 
4 5 3 2 1