1. golang 栈数据结构的实现和应用

开发运维 2023-10-12 贤蛋大眼萌 手机阅读

golang-栈.png

前言

本文主要讲述了“栈”数据结构的特性，以及 golang 如何实现栈，并拓展了一些可以使用栈结构解决的算法题。

栈的特性

栈是一种 FILO 类型（FILO 即 Fisrt In Last Out）的数据结构，也就是先进后出，也可以说是后进先出。

算法数据结构.png

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的，所以栈不是容器，而是容器适配器。

栈主要方法为 push 和 pop，不支持迭代器功能（不支持遍历元素），提供查看栈内元素数量、栈顶元素的方法，接下来让我们使用 golang 语言实现一下栈吧。

栈的实现

本小节分别使用 slice 和 链表结构实现栈，并通过 golang benchmark 简单测试一下性能。

使用 slice 实现栈

特点：

  • 依赖 Go 内置数据结构 slice 实现简单
  • 通过读写锁实现线程安全
  • 速度快，但由于共用底层数组的问题，pop 不一定会减少内存占用
package stack

import (
    "sync"
)

// Item 栈中存储的数据类型，这里使用接口
type Item interface{}

// ItemStack 存储 Item 类型的栈
type ItemStack struct {
    items []Item
    lock  sync.RWMutex
}

// NewStack 创建 ItemStack
func NewStack() *ItemStack {
    s := &ItemStack{}
    s.items = []Item{}
    return s
}

// Push 入栈
func (s *ItemStack) Push(t Item) {
    s.lock.Lock()
    s.lock.Unlock()
    s.items = append(s.items, t)
}

// Pop 出栈
func (s *ItemStack) Pop() Item {
    s.lock.Lock()
    defer s.lock.Unlock()
    if s.Len() == 0 {
        return nil
    }
    item := s.items[s.Len()-1]
    s.items = s.items[0 : s.Len()-1]
    return item
}

// Len 栈内存储的元素数量
func (s *ItemStack) Len() int {
    return len(s.items)
}

// Peek 查看栈顶元素
func (s *ItemStack) Peek() interface{} {
    if s.Len() == 0 {
        return nil
    }
    return s.items[s.Len()-1]
}

针对 slice 实现的基准测试

package stack

import (
    "testing"
)

var stack *ItemStack

func init() {
    stack = NewSliceStack()
}

func Benchmark_Push(b *testing.B) {
    for i := 0; i < b.N; i++ {
        stack.Push("test")
    }
}

func Benchmark_Pop(b *testing.B) {
    b.StopTimer()
    for i := 0; i < b.N; i++ {
        stack.Push("test")
    }
    b.StartTimer()
    for i := 0; i < b.N; i++ {
        stack.Pop()
    }
}

测试结果：

go test -test.bench=".*" -benchmem
goos: darwin
goarch: amd64
pkg: data_structure/stack
cpu: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
Benchmark_Push
Benchmark_Push-8        13897054                73.70 ns/op           86 B/op          0 allocs/op
Benchmark_Pop
Benchmark_Pop-8         38605101                28.74 ns/op            0 B/op          0 allocs/op
PASS
ok      data_structure/stack        6.269s

使用链表结构实现栈

特点：

  • node 结构中 prev 指向前一个 node，完成了一个后进先出的链表结构
  • 使用读写锁实现了线程安全
  • 占用的内存就是栈存储的内容，会随着 pop 而减少内存占用
package stack

import (
    "sync"
)

type (
    Stack struct {
        top    *node
        length int
        lock   *sync.RWMutex
    }
    node struct {
        value interface{}
        prev  *node
    }
)

func NewListStack() *Stack {
    return &Stack{nil, 0, &sync.RWMutex{}}
}

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

func (s *Stack) Peek() interface{} {
    if s.length == 0 {
        return nil
    }
    return s.top.value
}

func (s *Stack) Pop() interface{} {
    s.lock.Lock()
    defer s.lock.Unlock()
    if s.length == 0 {
        return nil
    }
    n := s.top
    s.top = n.prev
    s.length--
    return n.value
}

func (s *Stack) Push(value interface{}) {
    s.lock.Lock()
    defer s.lock.Unlock()
    n := &node{value, s.top}
    s.top = n
    s.length++
}

针对链表实现的基准测试

package stack

import (
    "testing"
)

var stack *Stack

func init() {
    stack = NewListStack()
}

func Benchmark_Push(b *testing.B) {
    for i := 0; i < b.N; i++ {
        stack.Push("test")
    }
}

func Benchmark_Pop(b *testing.B) {
    b.StopTimer()
    for i := 0; i < b.N; i++ {
        stack.Push("test")
    }
    b.StartTimer()
    for i := 0; i < b.N; i++ {
        stack.Pop()
    }
}

测试结果：

stack go test -test.bench=".*" -benchmem
goos: darwin
goarch: amd64
pkg: data_structure/stack
cpu: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
Benchmark_Push
Benchmark_Push-8        12294496                86.13 ns/op           24 B/op          1 allocs/op
Benchmark_Pop
Benchmark_Pop-8         41718554                36.03 ns/op            0 B/op          0 allocs/op
PASS
ok      data_structure/stack        8.449s

测试结果对比

golang benchmark 参数以及结果简单介绍：

  • benchmark 用例的参数 b *testing.B，有个属性 b.N 表示这个用例需要运行的次数，系统决定的。
  • pop 过程需要先 push 进去，而 push 也很耗时，所以使用 b.StopTimer() 、b.StartTimer() 开关定时器去除 push 操作。
  • -test.bench=".*" 参数支持传入一个正则表达式，匹配到的用例才会得到执行。
  • -benchmem 参数可以看到内存分配的情况。
  • goos 操作系统（darwin 表示 mac）
  • goarch 计算机架构 （amd64 64位计算机）
  • i5-1038NG7 CPU -8 表示 8 核
  • 12294496 表示用例执行次数（列如 push 多少次）
  • 86.13 ns/op 每次用例执行耗时
  • 24 B/op 每次用例执行分配内存， 1 allocs/op 内存分配次数

测试分别执行了 5 次，数据基本偏差不大，可以确定结论

  • 基于 slice 的栈执行速度更快

  • 基于 slice 的栈内存占用的更多（数据太少的情况不算在内）

    栈的实现方式 push 速度 push 内存分配 pop 速度
    基于 slice 73.70 ns/op 86 B/op 28.74 ns/op
    基于 链表 86.13 ns/op 24 B/op 36.03 ns/op

    • 算法实战

    由于栈结构的特殊性，非常适合做对称匹配类的题目。

    有效的括号

    leetcode 原题： 有效的括号

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

    • 示例 1： 输入：s = "()" 输出：true

    示例 2： 输入：s = "()[]{}" 输出：true

    示例 3： 输入：s = "(]" 输出：false

    提示：

    • s 仅由括号 '()[]{}' 组成

    解题思路：

    这是一个对称匹配的问题：

    • 左括号直接入栈即可，不需要做对称匹配
    • 右括号入栈前，需要检测栈顶元素是否和将要入栈的右括号匹配，如果匹配，则左括号出栈抵消，如果不匹配，则不满足要求。
    • 直到最后一个元素入栈判断完成，如果栈内元素个数为 0 表示符合要求，否则不符合要求。
    func isValid(s string) bool {
    // 匹配项
    hash := map[byte]byte{
        '}': '{',
        ']': '[',
        ')': '(',
    }

    stack := make([]byte, 0)
    for i := 0; i  0 && stack[len(stack)-1] == hash[s[i]] {
                // 除左括号外就是有括号（题目提示）
                stack = stack[:len(stack)-1]
            } else {
                // 右括号没匹配上，不符合要求
                return false
            }
        }
    }

    return len(stack) == 0
}

    删除字符串中所有相邻重复项

    leetcode 原题：删除字符串中所有相邻重复项

    给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

    示例： 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

    提示：

  • 1