设计一个递归函数来逆序一个栈，用Golang实现

我不是女神ヾ 2022-09-12 08:56 110阅读 0赞

题目：一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底依次为1、2、3、4、5，也就是实现栈中元素的逆序。

要求：只可以用递归函数来实现，不能使用其它数据结构。

解答：用两个递归函数处理。

1、将stack栈底元素返回并移除，假设从栈顶到栈底依次为3、2、1，这个函数的变化过程如下：

![d4e089903f802be3fdaec9f7a882edb7.png][]

2、逆序一个栈，假设从栈顶到栈底依次为3、2、1，这个函数的变化过程如下：

![db5d7044db3bd47524c5f8cdf38e0396.png][]

来看下上述方案的Golang代码实现：

/* *                    .::::. *                  .::::::::. *                 ::::::::::: *             ..:::::::::::' *           '::::::::::::' *             .:::::::::: *        '::::::::::::::.. *             ..::::::::::::.    Utils:仅用递归函数和栈操作，逆序一个栈 *           ``::::::::::::::::    Author:崔金朋 *            ::::``:::::::::'        .:::. *           ::::'   ':::::'       .::::::::. *         .::::'      ::::     .:::::::'::::. *        .:::'       :::::  .:::::::::' ':::::. *       .::'        :::::.:::::::::'      ':::::. *      .::'         ::::::::::::::'         ``::::. *  ...:::           ::::::::::::'              ``::. * ```` ':.          ':::::::::'                  ::::.. *                 '.:::::'                ':'````.. */package mainimport (  "errors")type ReverseStack struct {
         reverseStack []interface{}}// 获取并且移除最后一个元素func (r *ReverseStack) GetAndRemoveLastElement() (interface{}, error) {
         length := len(r.reverseStack)  if length == 0 {
           return nil, errors.New("栈为空")  }  element, elementErr := r.ReversePop()  if len(r.reverseStack) == 0 || elementErr != nil {
           return element, nil  }  lastElement, _ := r.GetAndRemoveLastElement()  _, reverseErr := r.ReversePush(element)  return lastElement, reverseErr}// 逆序一个栈func (r *ReverseStack) Reverse() ([]interface{}, error) {
         length := len(r.reverseStack)  if length == 0 {
           return []interface{}{}, errors.New("参数为空")  }  lastElement, _ := r.GetAndRemoveLastElement()  r.reverseStack, _ = r.Reverse()  r.ReversePush(lastElement)  return r.reverseStack, nil}func (r *ReverseStack) ReversePop() (interface{}, error) {
         length := len(r.reverseStack)  var item interface{}  if length == 0 {
           return 0, errors.New("数据不存在")  } else if length == 1 {
           item = r.reverseStack[0]    r.reverseStack = []interface{}{}  } else {
           item = r.reverseStack[length-1]    r.reverseStack = r.reverseStack[0 : length-1]  }  return item, nil}func (r *ReverseStack) ReversePush(item interface{}) (bool, error) {
         if item == nil {
           return false, errors.New("数据不能为空")  }  r.reverseStack = append(r.reverseStack, item)  return true, nil}

**扫码关注公众号，获取更多优质内容。**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbHV5YXJhbg_size_15_color_FFFFFF_t_70_g_se_x_16][]

[d4e089903f802be3fdaec9f7a882edb7.png]: /images/20220828/2ff685aec1344b6fbc4fff3d1906003f.png
[db5d7044db3bd47524c5f8cdf38e0396.png]: /images/20220828/850fceb1967a43159217cdb2fc7062b0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbHV5YXJhbg_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f5960884c5bf4598ad6084a8ca0ef8dd.png