1

基于Go的slice实现的栈式操作

 2 years ago
source link: https://allenwind.github.io/blog/3650/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Mr.Feng Blog

NLP、深度学习、机器学习、Python、Go

基于Go的slice实现的栈式操作

实现栈结构的常规思路是采用链式结构，用过指针和栈有关的属性值实现、控制栈的接口和规范。另外一种思路是采用数据组，把栈操作的数据保存在数组中。但采用数据的一个特点是，数组的大小是确定的，当需要改变数据的存储容量时需要重新分配内存和拷贝数据。

基于go内置的数据结构slice，可以实现灵活的栈结构。类实地，实现队列、堆、优先队列都可以使用Slice结构存储元素。下面给出栈的实现。

定义栈结构

type Stack struct {
    s      []int
    top    int
    length int
}

初始化栈结构

func NewStack() *Stack {
    stack := &Stack{
        s: make([]int, 0, 10),
    }
    return stack
}

为了简洁，如果遇到空栈，Pop和Top默认返回0值，改为弹出异常也不难。

func (s *Stack) Push(item int) {
    s.s = append(s.s, item)
    s.top = item
    s.length += 1
}

func (s *Stack) Empty() bool {
    return s.length == 0
}

func (s *Stack) Pop() int {
    if s.Empty() {
        return 0
    }
    item := s.s[s.length-1]
    s.s = s.s[:s.length-1]
    s.length -= 1
    return item
}

func (s *Stack) Len() int {
    return s.length
}

func (s *Stack) Top() int {
    if s.Empty() {
        return 0
    } else {
        return s.top
    }
}
func TestStack() {
    stack := NewStack()
    for i := 0; i <= 10; i++ {
        stack.Push(i)
    }

for !stack.Empty() {
        fmt.Println(stack.Pop())
    }
}

实现栈结构确实不难，但需要分析使用场景和实现的储存结构。这里采用了Slice实现，本质上就是数组，一篇连续的内存空间，在存储上更紧凑。关于栈的链式结构实现见栈的链式结构实现（Go语言版）。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK