AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-09-30 61
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文详细介绍了“栈”这一数据结构的特点，并用Golang实现栈。栈是一种FILO（First In Last Out，即先进后出或后进先出）的数据结构。文章展示了如何用slice和链表来实现栈，并通过golang benchmark测试了二者的性能差异。此外，还提供了几个使用栈结构解决的实际算法问题示例，如有效的括号匹配等。

前言

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

栈的特性

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

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

栈主要方法为 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 速度
基于 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. 左括号必须用相同类型的右括号闭合。
  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

文章标签：
Go
测试技术
容器
算法
安全
关键词：
Golang应用
数据结构应用
栈数据结构
Golang数据结构
栈数据结构应用
大数据文摘
目录
相关文章
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
42 1
RossyYan
|
4天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
116 75
RossyYan
|
4天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
27 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
4天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
30 9
RossyYan
|
4天前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
25 7
阿里云云原生
|
1月前
|
运维 监控 Cloud Native
一行代码都不改，Golang 应用链路指标日志全知道
本文将通过阿里云开源的 Golang Agent，帮助用户实现“一行代码都不改”就能获取到应用产生的各种观测数据，同时提升运维团队和研发团队的幸福感。
阿里云云原生
157 9
龙大吉
|
2月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
80 5
德国都芳最好
|
2月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
98 21
土木林森
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
74 1
龙大吉
|
2月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点，在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点，在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用，并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
龙大吉
47 5