使用双向链表实现双端队列的Golang程序

双端队列是一种多用途的数据结构，可以高效地在两端插入和删除元素。双向链表提供了构建双端队列的良好基础，因为它可以方便地在两个方向上进行遍历。在本文中，我们将使用自定义的双向链表和使用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 |
                                    |      |      |
                                    +------+------+

Syntax

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()函数初始化一个新的双向链表，它作为双端队列。

算法

• 创建一个”Node”结构体，它具有”value”、”prev”和”next”字段，用于表示双向链表中的节点。创建一个”Deque”结构体，它的”front”和”rear”指针初始化为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包来实现一个双向链表作为deque。我们首先使用list.New()创建一个名为”deque”的新双向链表。然后使用PushFront()和PushBack()函数在deque的前端和后端插入元素。使用Front()和Back()函数来访问deque的前端和后端的元素。在使用Remove()函数从deque的前端和后端移除元素之后，我们显示更新后的前端和后端元素。

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 包来执行操作。