一个进栈的所有出栈序列

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//给出出栈顺序  求所有进栈的序列 || 给出入栈顺序 求出栈顺序 
void print(stack<int> v) { 
	while (v.size() != 0) {
		cout<<v.top()<<" ";
		v.pop();
	}
	cout<<endl;
}
//a存放入栈序列，b模拟入栈， c存放可能的出栈的序列
void dfs(stack<int> a, stack<int> b, stack<int> c) {           
	
	if (a.size() == 0 && b.size() == 0 ) {
		print(c);	
		return;
	} 
	
	if (a.size() != 0) {		//入栈 
		int val = a.top();
		b.push(val);
		a.pop();
		dfs(a, b, c);
		b.pop();
		a.push(val);
	} 
	if (b.size() != 0) {		//出栈 
		int val = b.top();
		c.push(val);
		b.pop();
		dfs(a, b, c);
		c.pop();
		b.push(val);
	}
	
	return;
}