设计一个有getMin功能的栈（go 语言版本）

一、go语言 栈的实现 代码如下

栈的实现借助于g o语言数据结构之栈的实现 栈 慕课网大佬文章参考，并在上面完善功能

模拟栈的方法如下

InitStack 初始化栈
StackLength 获取栈的长度
IsEmpty 判断是否为空
IsFull 判断是否已经满了
Clear 清空栈
Peek 获取栈顶对象
Search
Pop 出栈
Push 入栈
Traverse 遍历栈

package MyStack
import (
    "fmt"
    "log"
    "reflect"
)
type Stack struct {
    size int64 //容量
    top  int64 //栈顶
    data []interface{}
}
//初始化栈
func InitStack(size int64) Stack {
    t := Stack{}
    t.size = size
    t.data = make([]interface{}, size)
    return t
}
//出栈，栈顶下降
func (t *Stack) Pop() (r interface{}, err error) {
    if t.IsEmpty() {
        err = fmt.Errorf("栈已空，无法完成出栈")
        log.Printf("栈已空，无法完成出栈")
        return
    }
    t.top--
    r = t.data[t.top]
    return
}
//入栈，栈顶升高
func (t *Stack) Push(element interface{}) bool {
    if t.IsFull() {
        log.Printf("栈已满，无法完成入栈")
        return false
    }
    t.data[t.top] = element
    t.top++
    return true
}
//遍历栈
func (t *Stack) Traverse(fn func(node interface{}), isTop2Bottom bool) {
    if isTop2Bottom {
        var i int64 = 0
        for ; i < t.top; i++ {
            fn(t.data[i])
        }
    } else {
        for i := t.top - 1; i >= 0; i-- {
            fn(t.data[i])
        }
    }
}
//栈的长度
func (t *Stack) StackLength() int64 {
    return t.top
}
//检查栈是否为空
func (t *Stack) IsEmpty() bool {
    return t.top == 0
}
//清空栈
func (t *Stack) Clear() {
    t.top = 0
}
//判断是否已满
func (t *Stack) IsFull() bool {
    return t.size == t.top
}
//获取栈顶对象
func (t *Stack) Peek() (r interface{}, err error) {
    if t.IsEmpty() {
        err = fmt.Errorf("")
        log.Printf("栈已空，无法获取栈顶")
        return
    }
    r = t.data[t.top-1]
    return
}
/*
    搜索某一个item在该栈中的位置【位置为离栈顶最近的item与栈顶间距离】
    方法调用返回从堆栈中，对象位于顶部的基于1的位置。
*/
func (t *Stack) Search(r interface{}) (post int64, err error) {
    post = int64(0)
    if t.IsEmpty() {
        err = fmt.Errorf("")
        log.Printf("栈已空，无法获取栈顶")
        return
    }

    for k, v := range t.data {
        fmt.Println(k, v)
        if reflect.DeepEqual(v, r) {
            post = int64(t.top) - int64(k)
        }
    }
    return
}

二、getMin功能的栈实现设计方案如下

方案一、 压入数据规则

压入规则：​

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：​ 如果为空，则newNum也压入stackMin。​如果不为空，则比较newNum和stackMin的栈顶元素哪一个更小：如果newNum更小或两者相等，newNum也压入stackMin;​如果stackMin中栈顶元素小，则stackMin不压入任何内容。

//MyStack1.go文件
package MyStack
//方案一、 压入数据规则，获取最小值
import (
    "fmt"
    "log"
)

type MyStack1 struct {
    stackData Stack
    stackMin Stack
}

//初始化结构体数值
func InitStackData(size int64) MyStack1 {
    t := MyStack1{}
    t.stackData = InitStack(size)
    t.stackMin = InitStack(size)
    return t
}
func (t *MyStack1) Push(newNum interface{}) {
    if t.stackMin.IsEmpty() {
        t.stackMin.Push(newNum)
    } else if v := t.GetMin();v.(int) >= newNum.(int) {
        t.stackMin.Push(newNum)
    }
    t.stackData.Push(newNum)
}
func (t *MyStack1) Pop() (r interface{}) {
    if t.stackData.IsEmpty() {
        fmt.Errorf("stackData is empty")
        log.Print("stackData is empty")
        return
    }
    r,_ = t.stackData.Pop()
    if r== t.GetMin() {
        t.stackMin.Pop()
    }
    return
}
func (t *MyStack1) GetMin() (r interface{}) {
     if t.stackMin.IsEmpty() {
         fmt.Errorf("stackMin is empty")
         log.Print("stackMin is empty")
         return
     }
     r,_ = t.stackMin.Peek()
     return r
}

//main.go文件

/**
作者：black
日期： 2020年03月22日
说明文档：设计一个特殊功能的栈 getMin
*/
package main
import (
    "MyStack"
    "fmt"
)
func main()  {
    size := int64(10)
    //方案 一、压入数据规则
    fmt.Println("方案1:压入数据规则")
    MyStack1 := MyStack.InitStackData(size);
    MyStack1.Push(10)
    MyStack1.Push(3)
    MyStack1.Push(13)
    MyStack1.Push(10)
    MyStack1.Push(14)
    MyStack1.Push(6)
    MyStack1.Push(433)
    fmt.Println("方案1:压入数据规则最小值",MyStack1.GetMin())

    //方案 二、弹出数据规则
    fmt.Println("方案2:弹出数据规则")
    MyStack2 := MyStack.InitStackData2(size);
    MyStack2.Push(10)
    MyStack2.Push(3)
    MyStack2.Push(13)
    MyStack2.Push(10)
    MyStack2.Push(14)
    MyStack2.Push(6)
    MyStack2.Push(433)
    fmt.Println("方案2:压入数据规则最小值",MyStack2.GetMin())
}

方案二、 弹出数据规则

弹出规则：​

当入栈的时候，如果stackMin是空，则入栈stackMin，当再此入栈，stackMin栈顶数值val和入栈的数值newval做比较，如果val>newval,那么stackMin就入栈newval到stackMin,如果val<= newval,就拿到stackMin栈顶的值入到stackMin里面

package MyStack
//方案一、 压入数据规则，获取最小值
import (
    "fmt"
    "log"
)

type MyStack2 struct {
    stackData Stack
    stackMin Stack
}

//初始化结构体数值
func InitStackData2(size int64) MyStack2 {
    t := MyStack2{}
    t.stackData = InitStack(size)
    t.stackMin = InitStack(size)
    return t
}

func (t *MyStack2) Push(r interface{}) {
    if t.stackMin.IsEmpty() {
        t.stackMin.Push(r)
    } else if v := t.GetMin();v.(int) > r.(int) {
        t.stackMin.Push(r)
    } else { // v<=r
        r1,_ := t.stackMin.Peek()
        t.stackMin.Push(r1)
    }
    t.stackData.Push(r)
}

func (t *MyStack2) Pop() (r interface{}) {
    if t.stackData.IsEmpty() {
        fmt.Errorf("stackData is empty")
        log.Print("stackData is empty")
        return
    }
    t.stackMin.Pop()
    r,_ = t.stackData.Pop()
    return
}

func (t *MyStack2) GetMin() (r interface{}) {
     if t.stackMin.IsEmpty() {
         fmt.Errorf("stackMin is empty")
         log.Print("stackMin is empty")
         return
     }
     r,_ = t.stackMin.Peek()
     return r
}