Go语言数据结构之 栈

什么是栈？

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

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

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

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

栈的特点？

后进先出（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]
}