递归——逆序一个栈

/*

仰望好的尝试？
给你一个栈，请你逆序这个栈，
不能申请额外的数据结构
只能使用递归函数。如何实现？
*/


/*
第一步  实现去掉栈底，并返回的函数 int f(stack)


| 1 |  |   |
| 2 |  | 1 |
| 3 |  | 2 |
-----  -----
f  r = 1 , last = f2(stack)
                  f2    r = 2, last = f3(stack)
                                      f3  r = 3  return
 */




type Stack []int

func (s *Stack)IsEmpty() bool {
	return len(*s) == 0
}

func (s *Stack)Pop() int {
	res := (*s)[len(*s)-1]
     *s = (*s)[:len(*s)-1]
	return res
}

func (s *Stack)Push(val int)  {
	*s = append(*s,val)
}

func reverse(stack *Stack)  {
	if stack.IsEmpty() {
		return
	}
	i := f(stack)
	reverse(stack)
	stack.Push(i)
}


func f(stack *Stack)  int {
	result := stack.Pop()
	if stack.IsEmpty() {
		return result
	}else {
		last := f(stack)
		stack.Push(result)
		return last
	}
}

func TestReverse(t *testing.T)  {
	stack := &Stack{}
	stack.Push(100)
	stack.Push(200)
	stack.Push(300)
	reverse(stack)

	for !stack.IsEmpty() {
		fmt.Println(stack.Pop())
	}
}