数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用双向链表实现双端队列的 Golang 程序
双端队列是一种通用的数据结构，它允许高效地从两端插入和删除元素。双向链表为构建双端队列提供了极好的基础，因为它允许轻松地双向遍历。在本文中，我们将探讨使用 Go 语言中双向链表实现双端队列的两种方法：使用自定义双向链表和使用 Golang 内置的 container/list 包。在下面的示例中，我们将展示双端队列的操作，我们将执行两端的插入和删除操作。
解释
如下所示，双端队列将从带有空值的头部开始，并在尾部以空值结束。元素以双向链表的方式连接在头部和尾部之间。我们可以看到每个节点都具有一个值，并与前一个和下一个节点连接，这使得元素的插入和删除更容易。
Front Rear
↓ ↓
+------+------+ +------+------+ +------+------+
| Prev | Next | ↔ | Prev | Next | ↔ | Prev | Next |
| Null | Node +─┐ | Node | Node +─┐ | Node | Null |
| | │ | | │ | | |
+------+------+ | +------+------+ |+------+------+
└─►| Prev | Next | | | Prev | Next |
| Node | Null | | | Node | Node |
| | | | | | |
+------+------+ | +------+------+
└─►| Prev | Next |
| Null | Node |
| | |
+------+------+
语法
newNode := &Node{value: value, prev: nil, next: nil}
语法 `newNode := &Node{value: value, prev: nil, next: nil}` 创建了一个名为 Node 的结构体的实例，该结构体具有三个字段：value、prev 和 next。“&” 符号用于获取新创建结构体的地址，使 newNode 成为指向该结构体的指针。value 字段使用变量 value 中提供的值进行初始化，prev 和 next 字段使用 nil 进行初始化，表示它们最初为空。
deque := list.New()
该语法使用 Go 标准库提供的 container/list 包来实现双端队列。list.New() 函数初始化一个新的双向链表，用作双端队列。
算法
创建一个具有“value”、“prev”和“next”字段的“Node”结构体，以表示双向链表中的节点。创建一个具有“front”和“rear”指针的“Deque”结构体，并将其初始化为 nil。
实现“PushFront(value)”操作，以便在双端队列的头部插入一个具有给定值的新节点。
实现“PushBack(value)”操作，以便在双端队列的尾部插入一个具有给定值的新节点。
实现“PopFront()”操作以删除并返回头部节点的值。实现“PopBack()”操作以删除并返回尾部节点的值。
实现“Front()”操作以获取双端队列头部元素的值。实现“Back()”操作以获取双端队列尾部元素的值。
示例 1
在这个例子中，我们创建了一个自定义数据结构，使用双向链表来实现双端队列。我们定义了一个 Node 结构体，其中包含 value、next 和 prev 指针，以表示双端队列中的每个元素。Deque 结构体包含 front 和 rear 指针。我们提供了在头部和尾部插入元素、从头部和尾部删除元素以及显示双端队列内容的方法。无界链表允许动态调整大小以容纳任意数量的元素。
package main
import (
"fmt"
)
type Node struct {
value interface{}
prev, next *Node
}
type Deque struct {
front, rear *Node
}
func (d *Deque) PushFront(value interface{}) {
newNode := &Node{value: value}
if d.front == nil {
d.front, d.rear = newNode, newNode
} else {
newNode.next = d.front
d.front.prev = newNode
d.front = newNode
}
}
func (d *Deque) PushBack(value interface{}) {
newNode := &Node{value: value}
if d.rear == nil {
d.front, d.rear = newNode, newNode
} else {
newNode.prev = d.rear
d.rear.next = newNode
d.rear = newNode
}
}
func (d *Deque) PopFront() interface{} {
if d.front == nil {
return nil
}
value := d.front.value
d.front = d.front.next
if d.front != nil {
d.front.prev = nil
} else {
d.rear = nil
}
return value
}
func (d *Deque) PopBack() interface{} {
if d.rear == nil {
return nil
}
value := d.rear.value
d.rear = d.rear.prev
if d.rear != nil {
d.rear.next = nil
} else {
d.front = nil
}
return value
}
func main() {
deque := &Deque{}
deque.PushBack(10)
deque.PushFront(5)
deque.PushBack(20)
fmt.Println("Deque after adding elements:", deque)
fmt.Println("Front element:", deque.PopFront())
fmt.Println("Rear element:", deque.PopBack())
fmt.Println("Deque after removing elements:", deque)
}
输出
Deque after adding elements: &{0xc00009c040 0xc00009c060}
Front element: 5
Rear element: 20
Deque after removing elements: &{0xc00009c020 0xc00009c020}
示例 2
在这个例子中，为了使用双向链表实现双端队列，我们使用 Go 标准库提供的 container/list 包来实现双端队列。我们首先使用 list.New() 创建一个名为“deque”的新双向链表。然后，我们分别使用 PushFront() 和 PushBack() 函数在双端队列的头部和尾部插入元素。Front() 和 Back() 函数用于访问双端队列头部和尾部的元素。在使用 Remove() 函数从双端队列的头部和尾部删除元素后，我们显示更新后的头部和尾部元素。
package main
import (
"container/list"
"fmt"
)
func main() {
deque := list.New()
deque.PushFront(3)
deque.PushFront(2)
deque.PushFront(1)
deque.PushBack(4)
deque.PushBack(5)
fmt.Println("Front of the Deque:", deque.Front().Value)
fmt.Println("Rear of the Deque:", deque.Back().Value)
deque.Remove(deque.Front())
deque.Remove(deque.Back())
fmt.Println("Front of the Deque after removal:", deque.Front().Value)
fmt.Println("Rear of the Deque after removal:", deque.Back().Value)
}
输出
Front of the Deque: 1 Rear of the Deque: 5 Front of the Deque after removal: 2 Rear of the Deque after removal: 4
现实生活中的实现
任务优先级
在任务调度系统中，可以使用双端队列来管理具有不同优先级的任务。可以将新任务添加到双端队列的尾部，并将高优先级任务添加到头部或移动到头部。这确保了关键任务的高效执行，同时维护待处理任务的列表。
滑动窗口问题
在处理流数据或序列时，双端队列可以帮助高效地解决滑动窗口问题。它允许以恒定时间从两端添加和删除元素，使其成为在数据移动窗口中查找最大值或最小值等任务的理想选择。
结论
双端队列能够高效地从两端插入和删除，使其成为通用的数据结构。在本文中，我们研究了如何在 Go 中使用双向链表实现双端队列。这里我们看到了两种方法，在第一个示例中，我们创建了一个自定义双向链表，在第二个示例中，我们使用了内置的 container/list 包来执行操作。
260 次查看
