资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

Golang队列基础及实现

创作时间:

作者:

@小白创作中心

Golang队列基础及实现

引用

CSDN

https://blog.csdn.net/2403_88269490/article/details/144644455

前言

本篇文章主要讲解了队列的概念、常用操作及实现方法。本文偏基础，适合初学者理解。本文资料主要引自《Hello 算法》

一、队列基础

1.什么是队列？

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

2.队列常用操作

push()：元素入队，即将元素添加至队尾。
pop()：队首元素出队。
peek()：访问队首元素。

// 初始化队列
// 在 Go 中，将 list 作为队列来使用
queue := list.New()

// 元素入队
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)

// 访问队首元素
peek := queue.Front()

// 元素出队
pop := queue.Front()
queue.Remove(pop)

// 获取队列的长度
size := queue.Len()

// 判断队列是否为空
isEmpty := queue.Len() == 0

二、队列实现

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

1.基于链表的实现

我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

基于链表实现的队列：

type linkedListQueue struct {
    // 使用内置包 list 来实现队列
    data *list.List
}

初始化队列：

func newLinkedListQueue() *linkedListQueue {
    return &linkedListQueue{
        data: list.New(),
    }
}

入队：

func (s *linkedListQueue) push(value any) {
    s.data.PushBack(value)
}

出队：

func (s *linkedListQueue) pop() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    s.data.Remove(e)
    return e.Value
}

访问队首元素：

func (s *linkedListQueue) peek() any {
    if s.isEmpty() {
        return nil
    }
    e := s.data.Front()
    return e.Value
}

获取队列的长度：

func (s *linkedListQueue) size() int {
    return s.data.Len()
}

判断队列是否为空：

func (s *linkedListQueue) isEmpty() bool {
    return s.data.Len() == 0
}

获取 List 用于打印：

func (s *linkedListQueue) toList() *list.List {
    return s.data
}

2.基于数组的实现

在数组中删除首元素的时间复杂度为 O(n)，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]。

入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1。
出队操作：只需将 front 增加 1，并将 size 减少 1。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为O(1)。

在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现（详情请看代码示例）。

基于环形数组实现的队列：

type arrayQueue struct {
    nums        []int // 用于存储队列元素的数组
    front       int   // 队首指针，指向队首元素
    queSize     int   // 队列长度
    queCapacity int   // 队列容量（即最大容纳元素数量）
}

初始化队列：

func newArrayQueue(queCapacity int) *arrayQueue {
    return &arrayQueue{
        nums:        make([]int, queCapacity),
        queCapacity: queCapacity,
        front:       0,
        queSize:     0,
    }
}

获取队列的长度：

func (q *arrayQueue) size() int {
    return q.queSize
}

判断队列是否为空：

func (q *arrayQueue) isEmpty() bool {
    return q.queSize == 0
}

入队：

func (q *arrayQueue) push(num int) {
    // 当 rear == queCapacity 表示队列已满
    if q.queSize == q.queCapacity {
        return
    }
    // 计算队尾指针，指向队尾索引 + 1
    // 通过取余操作实现 rear 越过数组尾部后回到头部
    rear := (q.front + q.queSize) % q.queCapacity
    // 将 num 添加至队尾
    q.nums[rear] = num
    q.queSize++
}

出队：

func (q *arrayQueue) pop() any {
    num := q.peek()
    if num == nil {
        return nil
    }
    // 队首指针向后移动一位，若越过尾部，则返回到数组头部
    q.front = (q.front + 1) % q.queCapacity
    q.queSize--
    return num
}

访问队首元素：

func (q *arrayQueue) peek() any {
    if q.isEmpty() {
        return nil
    }
    return q.nums[q.front]
}

获取 Slice 用于打印：

func (q *arrayQueue) toSlice() []int {
    rear := (q.front + q.queSize)
    if rear >= q.queCapacity {
        rear %= q.queCapacity
        return append(q.nums[q.front:], q.nums[:rear]...)
    }
    return q.nums[q.front:rear]
}