Go语言数据结构之栈

什么是栈？

栈（stack）又名==堆栈==，它是一种运算==受限的线性表==。限定仅在表尾进行插入和删除操作的线性表，这一端被称为==栈顶==

1、栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

2、压栈：栈的插入操作，叫做进栈，也称压栈、入栈。

3、弹栈：栈的删除操作，也叫做出栈。

avatar

栈的特点？

后进先出（Last In First Out）

如何用go语言实现栈？

栈的相关操作

• 栈的初始化 InitStack
• 弹栈 Pop
• 压栈 Push
• 栈大小 StackLen
• 栈的容量 StackSize
• 判断是否为空 IsEmpty
• 判断是否已满 IsFull
• 获取栈顶元素的值 Peek
• 清空栈 Clear
• 查询某个值==最近==距离栈顶的距离 Search
• 遍历栈 Traverse

实现代码如下:

package Stack

import (
    "fmt"
    "log"
    "reflect"
)

/*
栈的基本操作：
- 栈的初始化 InitStack
- 压栈 Push
- 弹栈 Pop
- 栈大小 StackLen
- 栈的容量 StackSize
- 判断是否为空 IsEmpty
- 判断是否已满 IsFull
- 获取栈顶元素的值 Peek
- 清空栈 Clear
- 查询某个值==最近==距离栈顶的距离 Search
- 遍历栈 Traverse

 */

type stack struct {
    size int64 //容量
    length  int64 //栈的长度
    data []interface{} //存在的元素
}


//初始化栈
func InitStack(size int64) stack {
    t := stack{}
    t.size = size
    t.data = make([]interface{}, size)
    return t
}

//压栈
func (s *stack) Push(r interface{}) (b bool,err error) {
    if s.IsFull() {
        b = false
        err = fmt.Errorf("Stack is Full")
        log.Println("Stack is Full")
        return
    }
    s.data[s.length] = r
    s.length++
    return
}

//弹栈
func (s *stack) Pop() (r interface{},err error) {
    if s.IsEmpty() {
        err = fmt.Errorf("Stack is Empty")
        log.Println("Stack is Empty")
        return
    }
    s.length--
    r = s.data[s.length]
    return
}

//获取栈顶对象
func (s *stack) Peek() (r interface{}, err error) {
    if s.IsEmpty() {
        err = fmt.Errorf("Stack is Empty")
        log.Printf("Stack is Empty")
        return
    }
    r = s.data[s.length-1]
    return
}


/*
    搜索某一个item在该栈中的位置【位置为离栈顶最近的item与栈顶间距离】
    方法调用返回从堆栈中，对象位于顶部的基于1的位置。
*/
func (s *stack) Search(r interface{}) (post int64, err error) {
    post = int64(0)
    if s.IsEmpty() {
        err = fmt.Errorf("")
        log.Printf("Stack is Empty")
        return
    }

    for k, v := range s.data {
        if reflect.DeepEqual(v, r) {
            post = int64(s.length) - int64(k)
        }
    }
    return
}

//遍历栈
func (s *stack) Traverse(fn func(r interface{}), isTop2Bottom bool) {
    if isTop2Bottom {
        var i int64 = 0
        for ; i < s.length; i++ {
            fn(s.data[i])
        }
    } else {
        for i := s.length - 1; i >= 0; i-- {
            fn(s.data[i])
        }
    }
}

//栈的容量
func (s *stack) StackSize() int64 {
    return s.size
}

//栈的长度
func (s *stack) StackLen() int64 {
    return s.length
}

//判断是否栈为空
func (s *stack) IsEmpty() bool {
    return s.length == 0
}

//判断是否已经满了
func (s *stack) IsFull() bool {
    return s.length == s.size
}

//清空
func (s *stack) Clear()  {
    s.length = 0
    s.data = s.data[0:0]
}