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

举报
宇宙之一粟 发表于 2022/10/30 15:10:29 2022/10/30
【摘要】 1 队列的概念队列是有序集合，遵循 FIFO （First in first out，即先进先出）排队方法的容器。添加操作发生在队列的尾部，移除操作则发生在头部。新元素从尾部进入队列，然后一直向前移动到头部，直到下一个被移除的元素。在日常生活中，我们经常需要排队，这就是队列数据结构的生活例子。排队的概念可以通过在快递驿站取快递的队伍来解释：当我们进入排队时，我们站在队伍的末端，排在队伍最前面...


1 队列的概念

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


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

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

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



队列的应用


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

  • 操作系统按照到达的顺序安排工作（优先级相同）（例如，打印队列）。

  • 模拟现实世界中的队列，如售票处的队伍或任何其他先到先得的情况，需要一个队列。

    异步数据传输（文件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 循环数组的实现

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


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


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


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

运行结果：


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

}

运行代码：


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 语言的自带数据结构列表和切片实现了队列，也用循环数组和自定义链表分别实现队列。队列在计算机的运用广泛，希望读者能够好好利用这一容器。


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


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

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

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
Golang 容器 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入