Go语言队列-EW帮帮网

队列(Queue)是一种先进先出(FIFO)的数据结构，队列是算法和并发编程中的基础数据结构，掌握其实现方式对Go开发者非常重要。接下来我将结合案例以及相关的资料，讲解队列的实现。

1. 使用切片(Slice)实现简单队列

下面用泛型切片(Slice)实现一个简单队列，首先声明队列类型，队列中的元素类型可以是任意的，所以类型约束为 any

type Queue[T any] []T

这里做一个延申，大家在查找资料的时候会看到如下的写法：

type Queue []interface{}

区别是：前者为Go 1.18+引入的泛型写法，后者为Go 1.18之前的标准写法。

泛型写法特点：

创建队列时需要指定具体类型
编译时保证类型安全
无需类型断言
代码更清晰且性能更好

标准写法特点：

可以存储任何类型的值
取出值时需要类型断言
缺乏编译时类型检查
运行时可能因类型错误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 的泛型参数 T 一致。
*q = append(*q, e) 使用 append 函数将新元素 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 方法用于获取队列中元素的数量。
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())
}

输出结果

2. 使用链表实现高效队列

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.创建新队列

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

NewQueue[T any]()：定义了一个构造函数，用于创建并返回一个指向新队列的指针。
return &Queue[T]{list: list.New()}：创建一个Queue[T]实例，并初始化其list字段为一个新的链表。

2.入队和出队函数

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

3.主函数

	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 存储可能发生的错误。

3.并发安全队列

首先我们先了解什么是并发环境

并发环境是指程序中多个执行流同时或交替运行的上下文，这些执行流可能共享资源并需要协调操作。在Go语言中，理解并发环境对编写正确高效的代码至关重要。

核心概念

并发 vs 并行
- 并发：逻辑上的同时处理（单核CPU通过时间片切换）
- 并行：物理上的同时执行（多核CPU真正同时运行）
Go的并发模型
- 基于Goroutine（轻量级线程）
- 通过Channel通信（而不是共享内存）
- 标准库提供sync包处理同步

并发环境的典型特征

资源共享
- 多个Goroutine访问同一变量/数据结构
- 示例：多个请求同时修改缓存
执行顺序不确定性
- Goroutine调度顺序不可预测
- 示例：两个Goroutine对同一变量先后写操作
竞态条件(Race Condition)
- 程序行为依赖于不可控的执行时序
- 示例：计数器未同步导致计数错误

接下来是并发安全队列

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：一个互斥锁，用于确保在多线程环境下对队列的操作是线程安全的。

1.入队出队

q.lock.Lock()：锁定互斥锁，确保在添加元素时没有其他 goroutine 可以修改队列。
defer q.lock.Unlock()：延迟解锁互斥锁，确保在函数返回前解锁。
q.lock.Lock() 和 defer q.lock.Unlock()：锁定和解锁互斥锁，确保线程安全。

2.查看队首元素

q.lock.Lock() 和 defer q.lock.Unlock()：锁定和解锁互斥锁，确保线程安全。

4. 使用channel实现队列

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
}

四种方法的选择场景

对于简单场景，使用切片实现即可
需要频繁增删元素时，使用链表实现更高效
并发环境使用带锁的队列或channel
channel适合生产者-消费者模式

Go语言队列

1. 使用切片(Slice)实现简单队列

a.定义 Push 方法：

b.定义 Pop 方法：

c.定义peek方法

d.定义 Size 方法：

2. 使用链表实现高效队列

3.并发安全队列

核心概念

并发环境的典型特征

4. 使用channel实现队列

四种方法的选择场景

网站公告

今日签到

热门文章

最新发布

Go语言 队列

1. 使用切片(Slice)实现简单队列

a.定义 Push 方法：

b.定义 Pop 方法：

c.定义peek方法

d.定义 Size 方法：

2. 使用链表实现高效队列

3.并发安全队列

核心概念

并发环境的典型特征

4. 使用channel实现队列

四种方法的选择场景

网站公告

今日签到

热门文章

最新发布

Go语言队列