隊(duì)列(Queue)是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列是算法和并發(fā)編程中的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，掌握其實(shí)現(xiàn)方式對(duì)Go開發(fā)者非常重要。接下來我將結(jié)合案例以及相關(guān)的資料，講解隊(duì)列的實(shí)現(xiàn)。

1. 使用切片(Slice)實(shí)現(xiàn)簡(jiǎn)單隊(duì)列

下面用泛型切片(Slice)實(shí)現(xiàn)一個(gè)簡(jiǎn)單隊(duì)列，首先聲明隊(duì)列類型，隊(duì)列中的元素類型可以是任意的，所以類型約束為 any

type Queue[T any] []T

這里做一個(gè)延申，大家在查找資料的時(shí)候會(huì)看到如下的寫法：

type Queue []interface{}

區(qū)別是：前者為Go 1.18+引入的泛型寫法，后者為Go 1.18之前的標(biāo)準(zhǔn)寫法。

泛型寫法特點(diǎn)：

• 創(chuàng)建隊(duì)列時(shí)需要指定具體類型
• 編譯時(shí)保證類型安全
• 無需類型斷言
• 代碼更清晰且性能更好

標(biāo)準(zhǔn)寫法特點(diǎn)：

• 可以存儲(chǔ)任何類型的值
• 取出值時(shí)需要類型斷言
• 缺乏編譯時(shí)類型檢查
• 運(yùn)行時(shí)可能因類型錯(cuò)誤panic

小編更傾向泛型寫法，當(dāng)然這個(gè)因人而異。雖然標(biāo)準(zhǔn)寫法可以存儲(chǔ)混合類型，但是泛型寫法可以是使用any解決。

隊(duì)列的基本操作有四個(gè)方法：入隊(duì)（Push）、出隊(duì)（Pop）、查看隊(duì)首元素（Peek）和獲取隊(duì)列大小（Size）

a.定義 Push 方法：

func (q *Queue[T]) Push(e T) {
  *q = append(*q, e)
}

• Push 方法用于將一個(gè)元素添加到隊(duì)列的末尾。
• q *Queue[T] 表示接收者是指向 Queue 結(jié)構(gòu)體的指針。
• e T 是要添加的元素，其類型與 Queue 的泛型參數(shù) T 一致。
• *q = append(*q, e) 使用 append 函數(shù)將新元素 e 添加到隊(duì)列的切片 *q 中。

b.定義 Pop 方法：

func (q *Queue[T]) Pop() (_ T) {
  if q.Size() > 0 {
    res := q.Peek()
    *q = (*q)[1:]
    return res
  }
  return
}

• Pop 方法用于從隊(duì)列的頭部移除并返回一個(gè)元素。
• q *Queue[T] 表示接收者是指向 Queue 結(jié)構(gòu)體的指針。
• _ T 表示返回值的類型為 T，但返回值的名稱被忽略。
• if q.Size() > 0 檢查隊(duì)列是否為空。
• res := q.Peek() 獲取隊(duì)列的頭部元素。
• *q = (*q)[1:] 將隊(duì)列的切片從第二個(gè)元素開始截取，從而移除隊(duì)首元素。
• return res 返回隊(duì)首元素。
• 如果隊(duì)列為空，則返回類型的零值。

c.定義peek方法

func (q *Queue[T]) Peek() (_ T) {
  if q.Size() > 0 {
    return (*q)[0]
  }
  return
}

• Peek 方法用于查看隊(duì)列的頭部元素而不移除它。
• q *Queue[T] 表示接收者是指向 Queue 結(jié)構(gòu)體的指針。
• _ T 表示返回值的類型為 T，但返回值的名稱被忽略。
• if q.Size() > 0 檢查隊(duì)列是否為空。
• return (*q)[0] 返回隊(duì)列的頭部元素。
• 如果隊(duì)列為空，則返回類型的零值。

d.定義 Size 方法：

func (q *Queue[T]) Size() int {
  return len(*q)
}

• Size 方法用于獲取隊(duì)列中元素的數(shù)量。
• q *Queue[T] 表示接收者是指向 Queue 結(jié)構(gòu)體的指針。
• return len(*q) 返回隊(duì)列切片的長(zhǎng)度。

嘗試打印一下：

func main() {
	q := Queue[int]{}
	q.Push(1)
	q.Push(2)
	q.Push(3)
	fmt.Println(q)
	fmt.Println(q.Pop())
	fmt.Println(q.Peek())
	fmt.Println(q.Size())
}

輸出結(jié)果

[1 2 3]
1
2
2

2. 使用鏈表實(shí)現(xiàn)高效隊(duì)列

package main
 
import (
    "container/list"
    "fmt"
)
 
// 隊(duì)列內(nèi)部用了一個(gè)鏈表來存儲(chǔ)元素
type Queue[T any] struct {
    list *list.List
}
 
func NewQueue[T any]() *Queue[T] {
    return &Queue[T]{list: list.New()}
}
 
func (q *Queue[T]) Enqueue(item T) {
    q.list.PushBack(item)
}
 
func (q *Queue[T]) Dequeue() (T, error) {
    if q.list.Len() == 0 {
        var zero T
        return zero, fmt.Errorf("queue is empty")
    }
    front := q.list.Front()
    q.list.Remove(front)
    return front.Value.(T), nil
}
 
func (q *Queue[T]) Peek() (T, error) {
    if q.list.Len() == 0 {
        var zero T
        return zero, fmt.Errorf("queue is empty")
    }
    return q.list.Front().Value.(T), nil
}
 
func (q *Queue) IsEmpty() bool {
    return q.list.Len() == 0
}
 
func (q *Queue) Size() int {
    return q.list.Len()
}
 
func main() {
    q := NewQueue[string]()
    q.Enqueue("a")
    q.Enqueue("b")
    q.Enqueue("c")
    
 
	if val, err := q.Dequeue(); err == nil {
		fmt.Println(val)
	}
 
	if peekVal, err := q.Peek(); err == nil {
		fmt.Println(peekVal)
	}
    fmt.Println(q.Size())    // 2
}

解讀一下與上一個(gè)例子不同的地方：

1.創(chuàng)建新隊(duì)列

func NewQueue[T any]() *Queue[T] {
    return &Queue[T]{list: list.New()}
}

• NewQueue[T any]()：定義了一個(gè)構(gòu)造函數(shù)，用于創(chuàng)建并返回一個(gè)指向新隊(duì)列的指針。
• return &Queue[T]{list: list.New()}：創(chuàng)建一個(gè)Queue[T]實(shí)例，并初始化其list字段為一個(gè)新的鏈表。

2.入隊(duì)和出隊(duì)函數(shù)

• q.list.PushBack(item)：使用鏈表的PushBack方法將元素添加到鏈表的尾部。
• front := q.list.Front()：獲取鏈表的首元素。
• q.list.Remove(front)：移除首元素。
• return front.Value.(T), nil：返回被移除元素的值。

3.主函數(shù)

	if peekVal, err := q.Peek(); err == nil {
		fmt.Println(peekVal)
	} else {
		fmt.Println("Error:", err)
	}

• q.Peek()：調(diào)用 Queue 類型的 Peek() 方法，該方法返回隊(duì)首元素的值和一個(gè)錯(cuò)誤（如果隊(duì)列為空，則返回零值和一個(gè)錯(cuò)誤）。
• peekVal, err := q.Peek()：使用多重賦值語法將 Peek() 方法的返回值分別賦給 peekVal 和 err 變量。peekVal 存儲(chǔ)隊(duì)首元素的值，err 存儲(chǔ)可能發(fā)生的錯(cuò)誤。

3.并發(fā)安全隊(duì)列

首先我們先了解什么是并發(fā)環(huán)境

并發(fā)環(huán)境是指程序中多個(gè)執(zhí)行流同時(shí)或交替運(yùn)行的上下文，這些執(zhí)行流可能共享資源并需要協(xié)調(diào)操作。在Go語言中，理解并發(fā)環(huán)境對(duì)編寫正確高效的代碼至關(guān)重要。

核心概念

1. 并發(fā) vs 并行

   • 并發(fā)：邏輯上的同時(shí)處理（單核CPU通過時(shí)間片切換）
   • 并行：物理上的同時(shí)執(zhí)行（多核CPU真正同時(shí)運(yùn)行）

2. Go的并發(fā)模型

   • 基于Goroutine（輕量級(jí)線程）
   • 通過Channel通信（而不是共享內(nèi)存）
   • 標(biāo)準(zhǔn)庫(kù)提供sync包處理同步

并發(fā)環(huán)境的典型特征

1. 資源共享

   • 多個(gè)Goroutine訪問同一變量/數(shù)據(jù)結(jié)構(gòu)
   • 示例：多個(gè)請(qǐng)求同時(shí)修改緩存

2. 執(zhí)行順序不確定性

   • Goroutine調(diào)度順序不可預(yù)測(cè)
   • 示例：兩個(gè)Goroutine對(duì)同一變量先后寫操作

3. 競(jìng)態(tài)條件(Race Condition)

   • 程序行為依賴于不可控的執(zhí)行時(shí)序
   • 示例：計(jì)數(shù)器未同步導(dǎo)致計(jì)數(shù)錯(cuò)誤

接下來是并發(fā)安全隊(duì)列

package main

import (
	"container/list"
	"fmt"
	"sync"
)

type ConcurrentQueue[T any] struct {
	list *list.List
	lock sync.Mutex
}

func NewQueue[T any]() *ConcurrentQueue[T] {
	return &ConcurrentQueue[T]{list: list.New()}
}

func (q *ConcurrentQueue[T]) Enqueue(item T) {
	q.lock.Lock()
	defer q.lock.Unlock()
	q.list.PushBack(item)
}

func (q *ConcurrentQueue[T]) Dequeue() (T, error) {
	q.lock.Lock()
	defer q.lock.Unlock()

	if q.list.Len() == 0 {
		var zero T
		return zero, fmt.Errorf("queue is empty")
	}

	front := q.list.Front()
	q.list.Remove(front)
	return front.Value.(T), nil
}

// 帶類型安全的Peek方法
func (q *ConcurrentQueue[T]) Peek() (T, error) {
	q.lock.Lock()
	defer q.lock.Unlock()

	if q.list.Len() == 0 {
		var zero T
		return zero, fmt.Errorf("queue is empty")
	}
	return q.list.Front().Value.(T), nil
}

func main() {
	q := NewQueue[string]()
	q.Enqueue("first")
	q.Enqueue("second")

	if val, err := q.Dequeue(); err == nil {
		fmt.Println("Dequeue:", val) // 輸出：Dequeue: first
	}

	if peekVal, err := q.Peek(); err == nil {
		fmt.Println("Peek:", peekVal) // 輸出：Peek: second
	}
}

代碼解讀：

• lock sync.Mutex：一個(gè)互斥鎖，用于確保在多線程環(huán)境下對(duì)隊(duì)列的操作是線程安全的。

1.入隊(duì)出隊(duì)

• q.lock.Lock()：鎖定互斥鎖，確保在添加元素時(shí)沒有其他 goroutine 可以修改隊(duì)列。
• defer q.lock.Unlock()：延遲解鎖互斥鎖，確保在函數(shù)返回前解鎖。
• q.lock.Lock() 和 defer q.lock.Unlock()：鎖定和解鎖互斥鎖，確保線程安全。

2.查看隊(duì)首元素

• q.lock.Lock() 和 defer q.lock.Unlock()：鎖定和解鎖互斥鎖，確保線程安全。

4. 使用channel實(shí)現(xiàn)隊(duì)列

package main

import "fmt"

func main() {
    queue := make(chan int, 3) // 緩沖大小為3
    
    queue <- 1
    queue <- 2
    queue <- 3
    
    fmt.Println(<-queue) // 1
    fmt.Println(<-queue) // 2
}

四種方法的選擇場(chǎng)景

1. 對(duì)于簡(jiǎn)單場(chǎng)景，使用切片實(shí)現(xiàn)即可
2. 需要頻繁增刪元素時(shí)，使用鏈表實(shí)現(xiàn)更高效
3. 并發(fā)環(huán)境使用帶鎖的隊(duì)列或channel
4. channel適合生產(chǎn)者-消費(fèi)者模式

到此這篇關(guān)于Go語言隊(duì)列的四種實(shí)現(xiàn)及使用場(chǎng)景的文章就介紹到這了,更多相關(guān)Go語言隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論