前言

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

栈的特性

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

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

栈主要方法为 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 < 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 <= S.length <= 20000
S 仅由小写英文字母组成。

解题思路：

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

遍历字符串，入栈前进行检查，入栈元素和栈顶元素重复，则删除，即可。

代码解读

复制代码

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

提示：

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

解题思路：

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

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

s = A + B 比如 "()()" ，此时 A=()，B=()
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 的分数。

代码解读

复制代码

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

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

前言

栈的特性

栈的实现

使用 slice 实现栈

使用链表结构实现栈

测试结果对比

算法实战

有效的括号

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

括号的分数

热门文章

最新文章

相关课程

相关电子书

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

前言

栈的特性

栈的实现

使用 slice 实现栈

使用链表结构实现栈

测试结果对比

算法实战

有效的括号

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

括号的分数

热门文章

最新文章

相关课程

相关电子书

推荐镜像