首页 > 其他分享 >Go 容器之队列的几种实现方式

Go 容器之队列的几种实现方式

时间：2022-10-30 15:31:34浏览次数：53  
标签：容器 return 队列 fmt Queue front func Go

Go 容器之队列的几种实现方式_数组

1 队列的概念

队列是有序集合，遵循 FIFO （First in first out，即先进先出）排队方法的容器。添加操作发生在队列的尾部，移除操作则发生在头部。新元素从尾部进入队列，然后一直向前移动到头部，直到下一个被移除的元素。

在日常生活中，我们经常需要排队，这就是队列数据结构的生活例子。排队的概念可以通过在快递驿站取快递的队伍来解释：

当我们进入排队时，我们站在队伍的末端，排在队伍最前面的人就是下一个被服务的人。他拿完快递，就可以退出队列。

当这种情况发生时，下一个人将来到队伍的最前面，将退出队列并得到服务。随着排在队首的每个人不断退出队列，我们向队首移动。最后，我们将到达队首，我们将退出队列并拿到快递。在需要保持先到先服务的情况下，这种行为是非常有用的。

Go 容器之队列的几种实现方式_数组_02

队列的应用

在计算机系统内部，操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法，其目标是尽可能快地执行程序，同时服务尽可能多的用户。

  • 操作系统按照到达的顺序安排工作（优先级相同）（例如，打印队列）。
  • 模拟现实世界中的队列，如售票处的队伍或任何其他先到先得的情况，需要一个队列。
    异步数据传输（文件IO、管道、插座）。
  • 客户在呼叫中心的等待时间。

在打字时，我们有时会发现字符出现的速度比击键速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示。

队列还能用于：

  • 用于其他算法的辅助数据结构（二叉树的层次遍历，图的广度优先）
  • 其他数据结构的组成

2 队列抽象数据类型

如上，队列中的插入和删除必须遵循 FIFO 方案。为了简单起见，我们假设元素是整数。

主要的队列操作

  • ​​EnQueue(item)​​：在队列的尾部添加一个元素，它需要一个元素作为参数，不返回任何值
  • ​​DeQueue()​​：从队列的头部移除一个元素。它不需要参数，并修改队列的内容
  • ​​Front()​​：返回前面的元素，但不删除它
  • ​​Rear()​​：返回后面的元素，而不将其删除
  • ​​Size() int​​：返回存储在队列中的元素数量。它不需要参数，且会返回一个整数
  • ​​isEmpty() bool​​：判断队列是否为空。它不需要参数，且会返回一个布尔值

3 Go 如何实现队列

在 Go 语言中，队列的实现方式也有很多，一些常用的方法列举如下：

  • 链表实现
  • 切片实现
  • 使用通道实现队列
  • 基于循环数组的简单实现
  • 基于动态循环数组的实现

3.1 List 实现

可以利用 Go 语言内置的 ​​container/list​​ 包来实现：

package main

import (
    "container/list"
    "fmt"
)

type customQueue struct {
    queue *list.List
}

func (c *customQueue) Enqueue(value string) {
    c.queue.PushBack(value)
}

func (c *customQueue) Dequeue() error {
    if c.queue.Len() > 0 {
        ele := c.queue.Front()
        c.queue.Remove(ele)
    }
    return fmt.Errorf("Pop Error: Queue is empty")
}

func (c *customQueue) Front() (string, error) {
    if c.queue.Len() > 0 {
        if val, ok := c.queue.Front().Value.(string); ok {
            return val, nil
        }
        return "", fmt.Errorf("Peep Error: Queue Datatype is incorrect")
    }
    return "", fmt.Errorf("Peep Error: Queue is empty")
}

func (c *customQueue) Size() int {
    return c.queue.Len()
}

func (c *customQueue) Empty() bool {
    return c.queue.Len() == 0
}

func main() {
    customQueue := &customQueue{
        queue: list.New(),
    }
    fmt.Printf("Enqueue: A\n")
    customQueue.Enqueue("A")
    fmt.Printf("Enqueue: B\n")
    customQueue.Enqueue("B")
    fmt.Printf("Size: %d\n", customQueue.Size())
    for customQueue.Size() > 0 {
        frontVal, _ := customQueue.Front()
        fmt.Printf("Front: %s\n", frontVal)
        fmt.Printf("Dequeue: %s\n", frontVal)
        customQueue.Dequeue()
    }
    fmt.Printf("Size: %d\n", customQueue.Size())
}

输出：

Enqueue: A
Enqueue: B
Size: 2
Front: A
Dequeue: A
Front: B
Dequeue: B
Size: 0

3.2 切片实现

切片也可以实现相同的功能：

package main

import (
    "fmt"
    "sync"
)

type customQueue struct {
    queue []string
    lock  sync.RWMutex
}

func (c *customQueue) Enqueue(name string) {
    c.lock.Lock()
    defer c.lock.Unlock()
    c.queue = append(c.queue, name)
}

func (c *customQueue) Dequeue() error {
    if len(c.queue) > 0 {
        c.lock.Lock()
        defer c.lock.Unlock()
        c.queue = c.queue[1:]
        return nil
    }
    return fmt.Errorf("Pop Error: Queue is empty")
}

func (c *customQueue) Front() (string, error) {
    if len(c.queue) > 0 {
        c.lock.Lock()
        defer c.lock.Unlock()
        return c.queue[0], nil
    }
    return "", fmt.Errorf("Peep Error: Queue is empty")
}

func (c *customQueue) Size() int {
    return len(c.queue)
}

func (c *customQueue) Empty() bool {
    return len(c.queue) == 0
}

func main() {
    customQueue := &customQueue{
        queue: make([]string, 0),
    }

    fmt.Printf("Enqueue: A\n")
    customQueue.Enqueue("A")
    fmt.Printf("Enqueue: B\n")
    customQueue.Enqueue("B")
    fmt.Printf("Len: %d\n", customQueue.Size())

    for customQueue.Size() > 0 {
        frontVal, _ := customQueue.Front()
        fmt.Printf("Front: %s\n", frontVal)
        fmt.Printf("Dequeue: %s\n", frontVal)
        customQueue.Dequeue()
    }
    fmt.Printf("Len: %d\n", customQueue.Size())
}

运行结果：

Enqueue: A
Enqueue: B
Size: 2
Front: A
Dequeue: A
Front: B
Dequeue: B
Size: 0

3.3 使用缓冲通道实现队列

从通道中写和读也经常是一个更好的选择。下面是一个使用通道实现队列的例子。

package main

import "fmt"

func main() {
    queueChan := make(chan int, 200)
    value1 := 5
    value2 := 4
    value3 := 6
    // enqueue
    queueChan <- value1
    queueChan <- value2
    queueChan <- value3

    // dequeue and return the value
    receice := <-queueChan
    fmt.Println("dequeue 1st time:  ", receice)
    receice2 := <-queueChan
    fmt.Println("dequeue 2nd time: ", receice2)

    if len(queueChan) == 0 {
        fmt.Println("Queue is empty")
    } else {
        fmt.Println("Queue is not empty")
    }
}

运行结果：

dequeue 1st time:   5
dequeue 2nd time:  4
Queue is not empty

3.4 循环数组的实现

首先，让我们看看我们是否可以像对待堆栈那样使用简单的数组来实现队列。我们知道，在队列中，插入是在一端进行，删除是在另一端进行。在进行了一些插入和删除之后，这个过程就变得容易理解了。

如果是数组实现的话，随着我们队列的入队和出队，数组的初始内存位置被浪费了。所以简单的数组实现队列并不高效。

Go 容器之队列的几种实现方式_数据结构_03

为了解决这个问题，可以使用圆形数组。这意味着，把最后一个元素和第一个数组元素视为连续的。使用这个方式，空间能够得到有效利用。

Go 容器之队列的几种实现方式_数据结构_04

package main

import (
    "bytes"
    "fmt"
)

const MaxInt = int(^uint(0) >> 1)
const MinInt = -MaxInt

type Queue struct {
    array    []interface{}
    front    int
    rear     int
    capacity int
    size     int
}

func New(capacity int) *Queue {
    return new(Queue).Init(capacity)
}

func (q *Queue) Init(capacity int) *Queue {
    q.array = make([]interface{}, capacity)
    q.front, q.rear, q.size, q.capacity = -1, -1, 0, capacity
    return q
}

func (q *Queue) length() int {
    return q.size
}

func (q *Queue) isEmpty() bool {
    return q.size == 0
}

func (q *Queue) isFull() bool {
    return q.size == q.capacity
}

func (q *Queue) String() string {
    var result bytes.Buffer
    result.WriteByte('[')
    j := q.front
    for i := 0; i < q.size; i++ {
        result.WriteString(fmt.Sprintf("%v", q.array[j]))
        if i < q.size-1 {
            result.WriteByte(' ')
        }
        j = (j + 1) % q.capacity
    }
    result.WriteByte(']')
    return result.String()
}

func (q *Queue) Front() interface{} {
    return q.array[q.front]
}

func (q *Queue) Back() interface{} {
    return q.array[q.rear]
}

func (q *Queue) enQueue(v interface{}) {
    if q.isFull() {
        return
    }

    q.rear = (q.rear + 1) % q.capacity
    q.array[q.rear] = v
    if q.front == -1 {
        q.front = q.rear
    }
    q.size++
}

func (q *Queue) dequeue() interface{} {
    if q.isEmpty() {
        return MinInt
    }

    data := q.array[q.front]
    if q.front == q.rear {
        q.front = -1
        q.rear = -1
        q.size = 0
    } else {
        q.front = (q.front + 1) % q.capacity
        q.size -= 1
    }
    return data
}

func main() {
    var q Queue
    q.Init(6)
    q.enQueue(1)
    q.enQueue(2)
    q.enQueue(3)
    q.enQueue(4)
    q.enQueue(5)

    q.enQueue(2022)
    fmt.Println("现在的队列：", q.String())

    fmt.Println("出队元素：", q.dequeue())

    fmt.Println("队列的长度：", q.length())
    fmt.Println("当前队首：", q.Front())
    fmt.Println("当前队尾:", q.Back())
    
}

运行结果：

Go 容器之队列的几种实现方式_循环数组_05

3.5 动态数组的实现

当队列满的时候，在原有的代码上增加一个 ​​resize()​​ 函数，用于重新分配数组大小：

func (q *Queue) resize() {
    size := q.capacity
    q.capacity = q.capacity * 2
    adjusted := make([]interface{}, q.capacity)
    if q.front < q.rear {
        copy(adjusted, q.array[q.front:q.rear+1])
    } else {
        n := copy(adjusted, q.array[q.front:])
        copy(adjusted[n:], q.array[:q.rear+1])
    }
    q.array = adjusted
    q.front = 0
    q.rear = size - 1
}

完整代码如下：

package main

import (
    "bytes"
    "fmt"
)

const MaxInt = int(^uint(0) >> 1)
const MinInt = -MaxInt

type Queue struct {
    array    []interface{}
    front    int
    rear     int
    capacity int
    size     int
}

func New(capacity int) *Queue {
    return new(Queue).Init(capacity)
}

func (q *Queue) Init(capacity int) *Queue {
    q.array = make([]interface{}, capacity)
    q.front, q.rear, q.size, q.capacity = -1, -1, 0, capacity
    return q
}

func (q *Queue) length() int {
    return q.size
}

func (q *Queue) isEmpty() bool {
    return q.size == 0
}

func (q *Queue) isFull() bool {
    return q.size == q.capacity
}

func (q *Queue) String() string {
    var result bytes.Buffer
    result.WriteByte('[')
    j := q.front
    for i := 0; i < q.size; i++ {
        result.WriteString(fmt.Sprintf("%v", q.array[j]))
        if i < q.size-1 {
            result.WriteByte(' ')
        }
        j = (j + 1) % q.capacity
    }
    result.WriteByte(']')
    return result.String()
}

func (q *Queue) Front() interface{} {
    return q.array[q.front]
}

func (q *Queue) Back() interface{} {
    return q.array[q.rear]
}

func (q *Queue) resize() {
    size := q.capacity
    q.capacity = q.capacity * 2
    adjusted := make([]interface{}, q.capacity)
    if q.front < q.rear {
        copy(adjusted, q.array[q.front:q.rear+1])
    } else {
        n := copy(adjusted, q.array[q.front:])
        copy(adjusted[n:], q.array[:q.rear+1])
    }
    q.array = adjusted
    q.front = 0
    q.rear = size - 1
}

func (q *Queue) enQueue(v interface{}) {
    if q.isFull() {
        // return
        q.resize()
    }

    q.rear = (q.rear + 1) % q.capacity
    q.array[q.rear] = v
    if q.front == -1 {
        q.front = q.rear
    }
    q.size++
}

func (q *Queue) dequeue() interface{} {
    if q.isEmpty() {
        return MinInt
    }

    data := q.array[q.front]
    if q.front == q.rear {
        q.front = -1
        q.rear = -1
        q.size = 0
    } else {
        q.front = (q.front + 1) % q.capacity
        q.size -= 1
    }
    return data
}

func main() {
    var q Queue
    q.Init(1) // 初始化长度为 1 的队列
    q.enQueue(1)
    q.enQueue(2)
    q.enQueue(3)
    q.enQueue(4)
    q.enQueue(5)
    q.enQueue(2012)
    q.enQueue(2022)
    fmt.Println("现在的队列：", q.String())

    fmt.Println("出队元素：", q.dequeue())

    fmt.Println("队列的长度：", q.length())
    fmt.Println("当前队首：", q.Front())
    fmt.Println("当前队尾:", q.Back())

}

运行代码：

Go 容器之队列的几种实现方式_循环数组_06

3.6 自定义链表实现

我们也可以自己定义链表结构来实现队列。

package main

import (
    "bytes"
    "errors"
    "fmt"
)

type ListNode struct {
    data interface{}
    next *ListNode
}

type Queue struct {
    front *ListNode
    rear  *ListNode
    size  int
}

func (q *Queue) enQueue(data interface{}) {
    rear := new(ListNode)
    rear.data = data
    if q.isEmpty() {
        q.front = rear
    } else {
        oldLast := q.rear
        oldLast.next = rear
    }
    q.rear = rear
    q.size++
}

func (q *Queue) deQueue() (interface{}, error) {
    if q.isEmpty() {
        q.rear = nil
        return nil, errors.New("unable to deQueue element, queue is empty")
    }
    data := q.front.data
    q.front = q.front.next
    q.size--
    return data, nil
}

func (q *Queue) frontElement() (interface{}, error) {
    if q.isEmpty() {
        return nil, errors.New("unable to peek element, queue is empty")
    }
    return q.front.data, nil
}

func (q *Queue) isEmpty() bool {
    return q.front == nil
}

func (q *Queue) length() int {
    return q.size
}

func (q *Queue) String() string {
    var result bytes.Buffer
    result.WriteByte('[')

    j := q.front
    for i := 0; i < q.size; i++ {
        result.WriteString(fmt.Sprintf("%v", j.data))
        if i < q.size-1 {
            result.WriteByte(' ')
        }
        j = j.next
    }
    result.WriteByte(']')
    return result.String()
}

func main() {
    q := new(Queue)
    q.enQueue(1)
    q.enQueue(2)
    q.enQueue(3)

    fmt.Println(q.String())
    fmt.Println(q.length())
    fmt.Println(q.deQueue())

}

运行结果：

$ go run main.go 
[1 2 3]
3
1 <nil>

4 总结

本文介绍了队列的概念，学习了队列这一数据结构的抽象数据类型，最后用 Go 语言的自带数据结构列表和切片实现了队列，也用循环数组和自定义链表分别实现队列。队列在计算机的运用广泛，希望读者能够好好利用这一容器。

希望本文能对你有所帮助，如果喜欢本文，可以点个关注。

这里是宇宙之一粟，下一篇文章见！

宇宙古今无有穷期，一生不过须臾，当思奋争。

标签：容器,return,队列,fmt,Queue,front,func,Go
From： https://blog.51cto.com/yuzhou1su/5807521

相关文章

  • go excelize 批量写入数据到Excel
    funcCreateXlS(data[][]string,fileNamestring,headerNameArray[]string){f:=excelize.NewFile()sheetName:="sheet1"sheetWords:=[]strin......
  • 【博学谷学习记录】超强总结，用心分享|Python容器详解
    一、Python中容器的介绍容器：也可以称为是数据序列,或者高级数据类型,也是Python中的数据类型。容器中可以存放多个数据。Python中常用的容器有4种：list（列表）、......
  • kali自带sqlmap使用报错[CRITICAL] unable to connect to the target URL. sqlmap is
    kali自带的sqlmap使用报错root@kali:~#sqlmap-u"http://192.168.204.133/mutillidae/index.php?page=user-info.php&username=admin&password=admin&user-info-php-sub......
  • go 切片长度与容量的区别
    ###切片的声明切片可以看成是数组的引用（实际上切片的底层数据结构确实是数组）。在Go中，每个数组的大小是固定的，不能随意改变大小，切片可以为数组提供动态增长和缩小的需求，但......
  • 进入Pod中的容器
    查看帮助一、pod中只有1用户容器#只有一个容器时，进入时不需要指定容器，因为就是只有一个#test-pod为pod名称kubectlexec-ittest-pod-ntest--/bin/sh二、pod......
  • Android开发页面重定向导致WebvView.canGoBack一直返回true的解决方法
    Android开发页面重定向导致WebvView.canGoBack一直返回true的解决方法原因：打开页面A的时候重定向到页面B，页面B回退的时候回退到页面A，但是接着又重定向到页面B，所以canGoBack......
  • 数据结构之环形队列
    概述队列是一种具有先进先出（FIFO）的数据类型，可以使用多种数据结构来实现队列：数组和链表。简单队列的应用场景比较有限，于是那些牛人们就发明一些复杂的队列：环形队列双端队列优......
  • 0096-Go-错误处理
    环境Time2022-08-24Go1.19前言说明参考：https://gobyexample.com/errors目标使用Go语言的错误处理。错误处理packagemainimport("errors""fmt......
  • 0097-Go-协程
    环境Time2022-08-24Go1.19前言说明参考：https://gobyexample.com/goroutines目标使用Go语言的协程。启动函数协程packagemainimport("fmt""ti......
  • 0098-Go-通道
    环境Time2022-08-24Go1.19前言说明参考：https://gobyexample.com/channels目标使用Go语言的通道。示例packagemainimport"fmt"funcmain(){ messag......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99