数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Go语言程序实现持久化数据结构（栈）
持久化数据结构，例如栈，对于高效组织和按时间顺序管理编程中的数据至关重要。本文展示了在 Go 语言中实现持久化数据结构（重点是栈）的不同示例。在第一个示例中，我们使用不可变切片来执行操作，而在第二种方法中，我们使用链表。这里的实现意味着我们将演示在持久化数据结构上进行插入、更新和删除等操作。
解释
持久化数据结构允许在进行修改时保留以前的版本。在这种情况下，栈作为一种数据结构确保每次对其进行 push 或 pop 操作都会创建一个新版本，同时保留旧版本及其更改。
让我们假设我们有一棵树，其中包含一些值，我们需要向其中插入更多值。这是插入数据前后持久化数据结构的描述。
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] 添加到值 [15] 的右侧，使其成为叶子节点。
语法
func (s *Stack) Push(val int) *Stack
语法定义了一个名为 Push 的函数，它以整数值作为输入，将其添加到堆栈顶部，并返回 Stack 结构的新实例（指向堆栈的指针）。
func (s *Stack) Pop() (*Stack, int)
语法定义了一个名为 Pop 的函数，它从堆栈中移除顶部元素，并返回两个值，包括 Stack 结构的更新实例（指向堆栈的指针）以及原始堆栈顶部处的整数值。
算法
首先使用链表或数组定义栈结构。
实现 push 操作以创建包含添加元素的栈的新版本。
实现 pop 操作，每次移除顶部元素时都会生成栈的新版本。
创建在栈的不同版本之间导航的机制。
开发函数以访问栈特定版本的顶部元素。
示例 1
在这个示例中，我们将用 Go 语言实现持久化数据结构，我们使用 `Stack` 结构构建栈数据结构，该结构将整数数据存储为切片。push 和 pop 函数用于处理元素，同时保留以前的版本。`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 浏览器的浏览历史记录功能允许用户轻松访问和浏览以前查看过的网站列表。实现持久化的类似栈的数据结构是维护已访问网站历史记录的一种技术。此布局使访问者可以轻松返回以前访问过的网站。
文本编辑器：文本编辑器通常包含撤消和重做功能，允许用户回滚或重播对文档所做的更改。持久化栈是保留更改的时间顺序记录的潜在方法，允许恢复到以前的文档状态。
结论
持久化数据结构允许在进行修改时保留以前的版本。在本文中，我们探讨了如何使用两种不同的方法在 Go 语言中实现持久化数据结构（栈）。第一种方法使用不可变切片，而第二种方法使用链表。在这两种方法中，目标都是高效地维护栈的先前版本，确保可以访问历史状态。
210 次浏览
