資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
