Golang 程序实现持久数据结构(堆栈)
持久数据结构(例如堆栈)对于编程高效地组织和按时间顺序管理数据至关重要。本文展示了在 Go 中实现持久数据结构的不同示例，重点介绍堆栈。在第一个示例中，我们使用不可变切片来执行操作，而第二种方法使用链接列表，这里的实现意味着我们将演示在持久数据结构上插入、更新和删除等操作。
解释
持久数据结构允许在发生修改时保留以前的版本。在这种情况下，堆栈作为数据结构可确保每次对其本身的推送或弹出操作都会创建一个新版本，并在更改的同时保留旧版本。
假设我们有一棵树，其中包含一些值，我们需要向其中插入更多值。这是插入数据之前和之后持久数据结构的描述。
tree updated tree (After Insertion)
10 10
/ / \
5 ===> 5 15
\ / \ \
8 4 8 20
最初，树中的节点值为 10、5 和 8 ，当向树中插入新值时，插入值 15、4、20 ，新插入后，先前的版本保持不变。
根节点保持不变 [10]，新值 [15] 添加到右侧形成右子树，值 [4] 添加到值 [5] 的左侧，将其保留为二叉搜索树。值 [20] 被添加到 vale[15] 的右侧，使其成为叶节点。
语法
func (s *Stack) Push(val int) *Stack
该语法定义了一个名为 Push 的函数，该函数以整数值作为输入，将其添加到堆栈顶部，并返回 Stack 结构的新实例(指向堆栈的指针)。
func (s *Stack) Pop() (*Stack, int)
该语法定义了一个名为 Pop 的函数，该函数从堆栈中删除顶部元素，并返回两个值，包括 Stack 结构的更新实例(指向堆栈的指针)和原始堆栈顶部的整数值。
算法
首先使用链接列表或数组定义堆栈结构。
实现推送操作以创建带有添加元素的新版本的堆栈。
实现弹出操作以在每次移除顶部元素时生成新版本的堆栈。
创建一种在堆栈的不同版本之间导航的机制。
开发函数以访问特定版本的堆栈的顶部元素。
示例 1
在此示例中，我们将在 go 中实现持久数据结构，我们使用 `Stack` 结构构建堆栈数据结构，该结构将整数数据存储为切片。推送和弹出函数用于处理元素，同时保留以前的版本。 `NewStack` 函数初始化一个空堆栈，`Push` 方法创建一个新版本的堆栈并添加元素，而 `Pop` 方法每次移除顶部元素时都会生成一个新版本。在 `main` 函数中，创建并操作了堆栈的多个版本，展示了持久性方面。
package main
import "fmt"
type Stack struct {
data []int
}
func NewStack() *Stack {
return &Stack{}
}
func (s *Stack) Push(val int) *Stack {
newData := make([]int, len(s.data)+1)
copy(newData, s.data)
newData[len(newData)-1] = val
return &Stack{data: newData}
}
func (s *Stack) Pop() (*Stack, int) {
if len(s.data) == 0 {
return s, -1
}
newData := make([]int, len(s.data)-1)
copy(newData, s.data)
return &Stack{data: newData}, s.data[len(s.data)-1]
}
func main() {
stack1 := NewStack()
stack2 := stack1.Push(10)
stack3 := stack2.Push(20)
fmt.Println("Stack1:", stack1.data)
fmt.Println("Stack2:", stack2.data)
fmt.Println("Stack3:", stack3.data)
stack3, val1 := stack3.Pop()
stack2, val2 := stack2.Pop()
fmt.Println("Popped Value 1:", val1)
fmt.Println("Popped Value 2:", val2)
fmt.Println("Stack1:", stack1.data)
fmt.Println("Stack2:", stack2.data)
fmt.Println("Stack3:", stack3.data)
}
输出
Stack1: [] Stack2: [10] Stack3: [10 20] Popped Value 1: 20 Popped Value 2: 10 Stack1: [] Stack2: [] Stack3: [10]
示例 2
在此示例中，使用 Node 结构构建堆栈，该结构封装了一个整数值和对下一个节点的引用。 Stack 结构使用顶部节点指针。 NewStack 函数初始化一个空堆栈， Push 方法使用提供的值创建一个新节点，然后该节点成为新的顶部，而 Pop 方法检索顶部值、推进顶部指针并处理空堆栈场景。 main 函数演示了堆栈操作。
package main
import "fmt"
type Node struct {
value int
next *Node
}
type Stack struct {
top *Node
}
func NewStack() *Stack {
return &Stack{}
}
func (s *Stack) Push(val int) *Stack {
newNode := &Node{value: val, next: s.top}
return &Stack{top: newNode}
}
func (s *Stack) Pop() (*Stack, int) {
if s.top == nil {
return s, -1
}
poppedValue := s.top.value
return &Stack{top: s.top.next}, poppedValue
}
func main() {
stack1 := NewStack()
stack2 := stack1.Push(10)
stack3 := stack2.Push(20)
fmt.Println("Stack1:")
printStack(stack1)
fmt.Println("Stack2:")
printStack(stack2)
fmt.Println("Stack3:")
printStack(stack3)
stack3, val1 := stack3.Pop()
stack2, val2 := stack2.Pop()
fmt.Println("Popped Value 1:", val1)
fmt.Println("Popped Value 2:", val2)
fmt.Println("Stack1:")
printStack(stack1)
fmt.Println("Stack2:")
printStack(stack2)
fmt.Println("Stack3:")
printStack(stack3)
}
func printStack(s *Stack) {
curr := s.top
for curr != nil {
fmt.Printf("%d -> ", curr.value)
curr = curr.next
}
fmt.Println()
}
输出
Stack1: Stack2: 10 -> Stack3: 20 -> 10 -> Popped Value 1: 20 Popped Value 2: 10 Stack1: Stack2: Stack3: 10 ->
实际实施
浏览器历史记录: Web 浏览器中的浏览历史记录功能允许用户轻松访问和浏览之前查看过的网站列表。实现持久堆栈式数据结构是维护访问过网站历史记录的一种技术。此布局使访问者能够轻松返回之前访问过的网站。
文本编辑器:文本编辑器通常包括撤消和重做功能，使用户能够回滚或重播对文档所做的更改。持久堆栈是一种保留按时间顺序排列的更改记录的潜在方法，允许恢复到以前的文档状态。
结论
持久数据结构允许在进行修改时保留以前的版本。在本文中，我们探讨了如何使用两种不同的方法在 Golang 中实现持久数据结构，即堆栈。第一种方法使用不可变切片，而第二种方法使用链表。在这两种方法中，目标都是高效地维护堆栈的先前版本，确保可以访问历史状态。
