資料結構
網路
關係資料庫管理系統 (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 次瀏覽
