Go语言 设计一个有getMin功能的栈

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

栈的实现借助于下面原文的作者提供链接如下，并在上面完善功能
go语言数据结构之栈的实现 栈

模拟栈的方法如下

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]
	t.data = 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
}