栈与队列-3-递归实现栈的逆序

递归实现栈的逆序

  • 题目

    ​ 将栈只用递归方式实现栈的逆序。

  • 实现思路:

    ​ 1.先获取到栈底元素,保持原栈的数据信息。

    ​ 2.将每一步获取到的栈底元素最后押入到栈顶。

  • 图示说明

    ​ 1. 返回栈底元素,并将其移出掉

    返回栈底元素并移除

    ​ 2. 递归获取栈底元素,直到栈为空,在将获取到的元素押入到栈中。

    栈元素逆序

  • 实现代码

    注意:本代码中的栈结构及其方法,引用上篇定义的栈结构及其方法

    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
    37
    38
    39
    40
    package main

    import "fmt"
    // 每次弹出栈底元素
    func GetAadRemoveLastElement(m *StackData) interface{} {
    data, _ := m.Poll()
    if m.IsEmpty() {
    return data
    } else {
    last := GetAadRemoveLastElement(m)
    m.Add(data)
    return last
    }
    }

    // 递归实现元素的翻转
    func Reverse(d *StackData) {
    if d.IsEmpty() {
    return
    } else {
    result := GetAadRemoveLastElement(d)
    // 获取 1--2--3
    Reverse(d)
    // 压入 3--2--1
    d.Add(result)
    }
    }


    func main() {
    d := InitStack()
    d.Data = []interface{}{"1", 2, 3}
    d.Length = 3
    fmt.Printf("%#v\n", d.String())
    Reverse(d)
    fmt.Printf("%#v\n", d.String())
    }
    // 输出结果
    "[1 2 3]"
    "[3 2 1]"
本站总访问量 本站总访客数 本文总阅读量
载入天数...载入时分秒...