极客笔记Golang 通过使用链表实现优先队列
优先队列是一种数据结构，其中每个元素都被分配了一个优先级，具有较高优先级的元素先出列。在本文中，Golang程序专注于使用链表实现优先队列。在这里，我们将使用七种不同的方法：PriorityQueue结构体，Node结构体，insert、remove、Isempty、size和peek以及相关示例来阐述该概念。
语法
type PriorityQueue struct { head *Node}
语法类型PriorityQueue struct { … } 在Golang中定义了一个名为PriorityQueue的结构类型。它有一个字段：类型为*Node的head。PriorityQueue结构用于表示优先级队列，其中head字段指向链表中的第一个节点。此结构用于维护优先级队列的整体结构并对其执行操作。
func (pq *PriorityQueue) Insert(value interface{}, priority int)
在Golang中，语法func (pq *PriorityQueue) Insert(value interface{}, priority int)是一个方法声明。它定义了一个名为Insert的方法，该方法在表示为pq的PriorityQueue实例（接收者）上进行操作。
func (pq *PriorityQueue) Remove() interface{}
The Syntax func (pq *PriorityQueue) Remove() interface{} 是 Golang 中的另一种方法声明。它定义了一个名为 Remove 的方法，该方法操作由 pq 代表的 PriorityQueue 实例（接收器）。
func (pq *PriorityQueue) IsEmpty() bool
这个方法通过检查指针pq表示的优先队列的头指针来确定优先队列是否为空。如果头指针为nil，这意味着链表中没有节点，因此优先队列为空。
func (pq *PriorityQueue) Size() int
此方法通过遍历链表并计算节点数量来计算优先级队列的大小。它从头节点开始，沿着每个下一个指针遍历，直到到达链表的末尾。
func (pq *PriorityQueue) Peek() interface{}
这种方法允许您在不删除元素的情况下查看优先级队列中优先级最高的元素。它通过访问头节点的value字段来实现，该字段表示优先级队列前面的元素。
步骤
- 定义一个结构体来表示优先级队列的元素。每个元素应该有一个值和一个优先级。
-
为链表节点创建一个结构体类型，它应该包含指向元素的指针和指向下一个节点的指针。
-
声明一个变量来跟踪链表的头节点。
-
实现一个函数来插入一个元素到优先级队列中。这个函数应该接受值和优先级作为参数，创建一个带有该元素的新节点，并根据其优先级在链表中适当位置插入它。
-
实现一个函数来删除并返回优先级队列中优先级最高的元素。这个函数应该更新链表的头节点并返回元素。
-
实现一个函数来检查优先级队列是否为空，通过检查头节点是否为nil来判断。
-
可选：根据需要实现其他函数来检索优先级最高的元素而不删除它，或执行其他优先级队列操作。
示例1
在这个示例中，我们定义了一个名为Node的结构体，它表示优先级队列中的一个节点。它有三个字段：value用于存储节点的值，priority用于表示节点的优先级，next用于指向链表中的下一个节点。在main函数中，我们创建了一个示例Node实例并初始化其字段。然后，我们使用fmt.Println()打印节点字段的值。
package main
import "fmt"
type Node struct {
value interface{}
priority int
next *Node
}
func main() {
node := &Node{
value: "Sample Value",
priority: 1,
next: nil,
}
fmt.Println("Node Value:", node.value)
fmt.Println("Node Priority:", node.priority)
fmt.Println("Next Node:", node.next)
}
输出
Node Value: Sample Value
Node Priority: 1
Next Node: <nil>
示例2
在这个示例中，我们定义了一个名为PriorityQueue的结构体，表示一个优先队列。它有一个字段head，它指向链表的头部。在主函数中，我们创建了一个示例PriorityQueue实例，并将其head字段初始化为nil。然后，我们使用fmt.Println()打印head字段的值。
package main
import "fmt"
type Node struct {
value interface{}
priority int
next *Node
}
type PriorityQueue struct {
head *Node
}
func main() {
pq := &PriorityQueue{
head: nil,
}
fmt.Println("PriorityQueue Head:", pq.head)
}
输出
PriorityQueue Head: <nil>
示例3
在这个示例中，我们定义了PriorityQueue结构的Insert方法。该方法以值和优先级作为输入，并将具有给定值和优先级的新节点插入到优先队列中。在主函数中，我们创建了一个示例的PriorityQueue实例，并插入了三个具有不同值和优先级的节点。最后，我们打印优先队列中所有节点的值和优先级，以验证插入操作。
package main
import "fmt"
type Node struct {
value interface{}
priority int
next *Node
}
type PriorityQueue struct {
head *Node
}
func (pq *PriorityQueue) Insert(value interface{}, priority int) {
newNode := &Node{
value: value,
priority: priority,
next: nil,
}
if pq.head == nil || newNode.priority > pq.head.priority {
newNode.next = pq.head
pq.head = newNode
} else {
curr := pq.head
for curr.next != nil && newNode.priority <= curr.next.priority {
curr = curr.next
}
newNode.next = curr.next
curr.next = newNode
}
}
func main() {
pq := &PriorityQueue{
head: nil,
}
pq.Insert("Apple", 2)
pq.Insert("Banana", 1)
pq.Insert("Orange", 3)
curr := pq.head
for curr != nil {
fmt.Println("Value:", curr.value, "Priority:", curr.priority)
curr = curr.next
}
}
输出
Value: Orange Priority: 3
Value: Apple Priority: 2
Value: Banana Priority: 1
示例4
在这个示例中，我们为PriorityQueue结构定义了Remove方法。该方法从优先级队列中移除具有最高优先级的节点，并返回其值。在主函数中，我们创建了一个示例的PriorityQueue实例，并插入了三个具有不同值和优先级的节点。然后，我们调用Remove方法两次，并将返回的值存储在removed1和removed2变量中。最后，我们打印被移除节点的值，以验证移除操作。
package main
import "fmt"
type Node struct {
value interface{}
priority int
next *Node
}
type PriorityQueue struct {
head *Node
}
func (pq *PriorityQueue) Insert(value interface{}, priority int) {
}
func (pq *PriorityQueue) Remove() interface{} {
if pq.head == nil {
return nil
}
removedValue := pq.head.value
pq.head = pq.head.next
return removedValue
}
func main() {
pq := &PriorityQueue{
head: nil,
}
pq.Insert("Apple", 2)
pq.Insert("Banana", 1)
pq.Insert("Orange", 3)
removed1 := pq.Remove()
removed2 := pq.Remove()
fmt.Println("Removed value 1:", removed1)
fmt.Println("Removed value 2:", removed2)
}
输出
Removed value 1: <nil>
Removed value 2: <nil>
结论
总之，Golang程序成功地使用链表实现了一个优先级队列。优先级队列允许根据元素的优先级高低进行高效的插入和获取最高优先级的元素。该程序利用Node结构表示队列中的每个元素，利用PriorityQueue结构管理队列操作。该实现提供了插入元素到队列、移除最高优先级元素、检查队列是否为空、获取队列的大小，以及查看最高优先级元素而不移除它的方法。