问题描述

如何求入栈顺序为 1,2,3,4……,N的序列的所有可能的出栈序列？

解决方法

在网上找到一个非常巧妙的程序，巧妙地利用回溯思想，利用go语言实现了一下

中心思想是利用两个栈,s1为中间栈进行出栈操作,s2为初始栈进行入栈操作
其中有两种情况：

s1出栈输出值
s1不出栈，s2出栈，其值入s1栈中

重点是每次操作都需要进行记录，保留每次入栈出栈的操作，进行完之后的递归操作后还原其状态，其中s1栈利用一个变量保存出栈值，s1压入s2栈顶值还原状态

代码为：

 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
36
package main

import "fmt"

var (
	s1   = []int{} 
	s2   = []int{}  
	path = [2]int{} //输出队列
)

func main() {
	s2 = append(s2, []int{2, 1}...)
	Solve(0)
}

func Solve(step int) {  //step为输出队列下标
	var temp int
	if len(s1) == 0 && len(s2) == 0 {   //如果s1,s2栈都为空，则输出结果
		fmt.Println(path)
		return
	}
	if len(s1) != 0 {                   //如果中间栈不为空
		temp = s1[len(s1)-1]
		s1 = s1[:len(s1)-1]             
		path[step] = temp               //则出栈至输出队列
		Solve(step + 1)                 //进行下一层递归
		s1 = append(s1, temp)           //还原状态，进行s2栈的判断
	}
	if len(s2) != 0 {                   //如果原始栈不为空
		s1 = append(s1, s2[len(s2)-1])  
		s2 = s2[:len(s2)-1]             //原始栈出栈，中间栈入栈 
		Solve(step)                     //进行下一层递归
		s2 = append(s2, s1[len(s1)-1])
		s1 = s1[:len(s1)-1]             //还原状态
	}
}

算法小结——输出所有出栈情况

一个“简单”的回溯算法

问题描述

解决方法