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

程序浅谈 后端 2024-09-30

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

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

前言

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

栈的特性

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

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

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

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

栈的实现

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

使用 slice 实现栈

特点:

  • 依赖 Go 内置数据结构 slice 实现简单
  • 通过读写锁实现线程安全
  • 速度快,但由于共用底层数组的问题,pop 不一定会减少内存占用go
代码解读
复制代码
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 实现的基准测试go

代码解读
复制代码
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

代码解读
复制代码
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 而减少内存占用go
代码解读
复制代码
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++ }

针对链表实现的基准测试go

代码解读
复制代码
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() } }

测试结果:go

代码解读
复制代码
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 次,数据基本偏差不大,可以确定结论

  1. 基于 slice 的栈执行速度更快

  2. 基于 slice 的栈内存占用的更多(数据太少的情况不算在内)

    栈的实现方式push 速度push 内存分配pop 速度
    基于 slice73.70 ns/op86 B/op28.74 ns/op
    基于 链表86.13 ns/op24 B/op36.03 ns/op

算法实战

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

有效的括号

leetcode 原题: 有效的括号

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

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

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

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

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

提示:

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

解题思路:

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

  • 左括号直接入栈即可,不需要做对称匹配
  • 右括号入栈前,需要检测栈顶元素是否和将要入栈的右括号匹配,如果匹配,则左括号出栈抵消,如果不匹配,则不满足要求。
  • 直到最后一个元素入栈判断完成,如果栈内元素个数为 0 表示符合要求,否则不符合要求。go
代码解读
复制代码
func isValid(s string) bool { // 匹配项 hash := map[byte]byte{ '}': '{', ']': '[', ')': '(', } stack := make([]byte, 0) for i := 0; i < len(s); i++ { if s[i] == '{' || s[i] == '[' || s[i] == '(' { // 左括号 stack = append(stack, s[i]) } else { if len(stack) > 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. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

解题思路:

类似上题,这是个匹配消除问题,也是需要找到对称匹配,进行消除。

  • 遍历字符串,入栈前进行检查,入栈元素和栈顶元素重复,则删除,即可。go
代码解读
复制代码
func removeDuplicates(s string) string { stack := make([]byte, 0) for i := 0; i < len(s); i++ { if len(stack) == 0 { stack = append(stack, s[i]) continue } // 和栈顶元素重复,则删除 if s[i] == stack[len(stack)-1] { stack = stack[:len(stack)-1] } else { stack = append(stack, s[i]) } } return string(stack) }

括号的分数

leetcode 原题:括号的分数

给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

  • () 得 1 分。
  • AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分,其中 A 是平衡括号字符串。

示例 1:

输入: "()" 输出: 1

示例 2:

输入: "(())" 输出: 2

示例 3:

输入: "()()" 输出: 2

示例 4:

输入: "(()(()))" 输出: 6

提示:

  1. S 是平衡括号字符串,且只含有 ( 和 ) 。
  2. 2 <= S.length <= 50

解题思路:

看到括号匹配,就会想到用栈解决,但这道题按以往的思路尝试解决似乎不太容易,如果只是把括号入栈,则无法记录消除匹配括号产生的中间值,因此变得难以下手。但换种思路想一想,我们利用栈记录平衡括号字符串的分数,利用栈结构对中间值进行计算,最终栈顶元素则为最终结果,问题迎刃而解。

通过观察我们可以发现,()结构贡献了分数,外括号为该结构添加了乘数,同层括号之间以加法计算,计算平衡括号字符串 s 分数的过程可以拆解为计算平衡括号字符串子串的过程,可能的结果有两种:

  1. s = A + B 比如 "()()" ,此时 A=(),B=()
  2. s = (A + B) 比如 "(()(()))",此时 A=(),B=(())

通过栈结构,可以先把不能计算的部分入栈,将可计算的子串计算出来后,合并为更大的子串,通过出栈的方式,把之前入栈的部分继续计算,一步步计算更大的子串,最终 s 为自身最大的子串,计算结束。

可以把 s 看作是一个空字符串加上 s 本身,并且定义空字符串的分数为 0。使用栈记录平衡字符串的分数,在开始之前要压入分数 0,表示空字符串的分数。

在遍历字符串 s 的过程中:

  • 遇到左括号,那么我们需要计算该左括号内部的子平衡括号字符串 A 的分数,要先压入分数 0,表示 A 前面的空字符串的分数。
  • 遇到右括号,说明该右括号内部的子平衡括号字符串 A 的分数已经计算出来了,我们将它弹出栈,并保存到变量 item 中。如果 item=0 ,那么说明子平衡括号字符串 A 是空串,(A) 的分数为 1,否则 (A) 的分数为 2*item,然后将 (A) 的分数加到栈顶元素上。

遍历结束后,栈顶元素保存的就是 s 的分数。go

代码解读
复制代码
func scoreOfParentheses(s string) int { // 栈顶元素表示子串得分 // 压 0 入栈,表示空字符串的得分 // s = "" + s st := []int{0} for _, v := range s { // 左括号:压 0 入栈(表示空字符串的得分),表示本括号对开始 if v == '(' { st = append(st, 0) continue } // 右括号表示本括号对结束:计算子串分数 // 1. 出栈(子串得分) item := st[len(st)-1] st = st[:len(st)-1] // 2. 栈顶元素为 0,说明子串 =()得分为1 if item == 0 { item = 1 } else { // 栈顶不为 0,说明子串 = (A), 得分为 2 * A item = 2 * item } // 子串计算完毕后与栈顶元素(前一个子串)相加,成为更大的子串 st[len(st)-1] = st[len(st)-1] + item } // 栈顶元素为最终得分,最终 len(st)-1 = 0 return st[len(st)-1] }

转载来源:https://juejin.cn/post/7288628985322356751

Apipost 私有化火热进行中

评论