腳本之家服務器常用軟件

快捷導航

Go語言隊列的四種實現(xiàn)及使用場景

更新時間：2025年09月26日 09:02:13 作者：Jayden_念舊

本文主要介紹了Go語言隊列的四種實現(xiàn)及使用場景,包括切片、鏈表、帶鎖隊列和Channel,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

1. 使用切片(Slice)實現(xiàn)簡單隊列

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

type Queue[T any] []T

這里做一個延申，大家在查找資料的時候會看到如下的寫法：

type Queue []interface{}

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

泛型寫法特點：

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

標準寫法特點：

可以存儲任何類型的值
取出值時需要類型斷言
缺乏編譯時類型檢查
運行時可能因類型錯誤panic

小編更傾向泛型寫法，當然這個因人而異。雖然標準寫法可以存儲混合類型，但是泛型寫法可以是使用any解決。

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

a.定義 Push 方法：

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

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

b.定義 Pop 方法：

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

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

c.定義peek方法

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

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

d.定義 Size 方法：

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

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

嘗試打印一下：

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())
}

輸出結果

[1 2 3]
1
2
2

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

package main
 
import (
    "container/list"
    "fmt"
)
 
// 隊列內部用了一個鏈表來存儲元素
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
}

解讀一下與上一個例子不同的地方：

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

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

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

2.入隊和出隊函數(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()：調用 Queue 類型的 Peek() 方法，該方法返回隊首元素的值和一個錯誤（如果隊列為空，則返回零值和一個錯誤）。
peekVal, err := q.Peek()：使用多重賦值語法將 Peek() 方法的返回值分別賦給 peekVal 和 err 變量。peekVal 存儲隊首元素的值，err 存儲可能發(fā)生的錯誤。

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

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

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

核心概念

并發(fā) vs 并行
- 并發(fā)：邏輯上的同時處理（單核CPU通過時間片切換）
- 并行：物理上的同時執(zhí)行（多核CPU真正同時運行）
Go的并發(fā)模型
- 基于Goroutine（輕量級線程）
- 通過Channel通信（而不是共享內存）
- 標準庫提供sync包處理同步

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

資源共享
- 多個Goroutine訪問同一變量/數(shù)據(jù)結構
- 示例：多個請求同時修改緩存
執(zhí)行順序不確定性
- Goroutine調度順序不可預測
- 示例：兩個Goroutine對同一變量先后寫操作
競態(tài)條件(Race Condition)
- 程序行為依賴于不可控的執(zhí)行時序
- 示例：計數(shù)器未同步導致計數(shù)錯誤

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

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：一個互斥鎖，用于確保在多線程環(huán)境下對隊列的操作是線程安全的。

1.入隊出隊

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

2.查看隊首元素

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

4. 使用channel實現(xiàn)隊列

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
}