是否有队列实现？

Question

有人能建议一个适用于简单且快速FIF/队列的Go容器吗？Go有三种不同的容器：heap、list和vector。哪一种最适合实现队列？

- rev

Answer 1

事实上，如果您需要一个基础且易于使用的FIFO队列，slice提供了您所需的一切。

queue := make([]int, 0)
// Push to the queue
queue = append(queue, 1)
// Top (just get next element, don't remove it)
x = queue[0]
// Discard top element
queue = queue[1:]
// Is empty ?
if len(queue) == 0 {
    fmt.Println("Queue is empty !")
}

当然，我们假设我们可以信任append和slicing的内部实现，以避免无用的重新分配和调整大小。对于基本用途来说，这已经足够了。

- Marwan Burelle

---

SliceTricks: 如何使用切片（slices）来实现类似向量的操作本文将介绍如何使用Go语言中的切片（slices）来实现一些常见的向量操作。这些操作包括追加（append）、拷贝（copy）、截取（slice）、插入（insert）、删除（delete）等等。我们将通过示例代码来说明每个操作的用法和效果，并解释它们的原理和使用场景。这些内容将帮助你更好地理解和掌握Go语言中切片的特性和用法，从而提高编程效率和代码质量。本文还将介绍一些高级的切片操作，例如“去重”、“查找最大/最小值”、“反转切片”等等。这些操作需要一些算法知识和技巧，但是它们可以极大地简化代码，并提高程序的运行效率和内存利用率。阅读本文需要一定的基础知识和经验，但是即使你是刚刚开始学习Go语言，也可以通过仔细阅读和理解每个示例代码来掌握这些技巧和方法。 - peterSO

@Florian，这个示例代码使用 []int，其中复制是所需的。如果改为 type Foo struct{/*许多字段*/}，通常会使用[]*Foo，并且队列将是指针，您不需要复制元素，只需复制指针即可。（然后，您还需要执行queue[0] = nil; queue = queue[1:]，以舍弃第一个元素并从队列中删除对其的引用）。 - Dave C

这种实现的问题在于，它的内存使用量与出队调用的次数成正比。 - kostya

@kostya和@tul的评论不准确。当没有足够的容量来存储新元素时，append将创建一个新的支持数组。因此，只要您丢弃旧切片queue=queue[1：]，内存使用就不会是无界的。如果切片很大，仍可能需要一段时间才能回收该内存。 - Nuno Cruces

同意@NunoCruces。 当向切片添加足够的新元素以导致重新分配时，第一个元素将被垃圾收集-- 然后可以丢弃已删除的元素。https://go.googlesource.com/go/+/master/src/runtime/slice.go#76 - Josh Hibschman

Answer 2

惊讶地发现还没有人建议使用带缓冲通道来实现固定大小的先进先出队列。

//Or however many you might need + buffer.
c := make(chan int, 300)

//Push
c <- value

//Pop
x <- c

- saarrrr

---

对于不需要持久化的小队列，这应该是默认操作。即使您正在向磁盘上的一个无限制队列中写入数据，使用通道进行读写通常也是一个好方法。 - Rob

x = <-c 是一个阻塞调用吗？如果 c 为空，那么您的 Go 协程将一直挂起，直到队列重新填充为止。这不是您想要的简单队列数据结构的行为吧？ - anaken78

没问题，一个选择语句或默认语句就可以解决这个问题，对吧？https://gobyexample.com/non-blocking-channel-operations - Kostas

有些新手会被缓冲通道的简洁语法所吸引，想在单个goroutine内使用它们作为队列，但这是错误的。通道与goroutine调度密切相关，如果没有另一个goroutine从通道接收数据，发送者甚至整个程序可能会永久阻塞。如果你只需要一个简单的队列，使用slice即可。 - izaban

虽然这个实现很优雅，但据我所知它没有我需要的Peek()函数。 - Kevin

Answer 3

大多数队列实现有三种类型：基于切片、基于链表和基于循环缓冲区（环形缓冲区）。

• 基于切片的队列容易浪费内存，因为它们不重用已删除项目之前占用的内存。 此外，基于切片的队列往往只是单端队列。
• 链表队列可以更好地重用内存，但通常会稍微慢一些，并且总体上使用更多内存，因为要维护链接的开销。 它们可以提供在队列中间添加和删除项目的能力，而无需移动内存，但如果您正在做这方面的很多工作，则列表就是错误的数据结构。
• 环形缓冲区队列提供了切片的所有效率，并具有不浪费内存的优势。 更少的分配意味着更好的性能。 它们添加或删除任一端的项时同样有效，因此您自然得到双端队列。 因此，一般建议使用基于环形缓冲区的队列实现。 这是本文剩余部分讨论的内容。

基于环形缓冲区的队列通过将其存储包装在周围来重新使用内存：当队列超出底层切片的一端增长时，它会在切片的另一端添加额外的节点。 请参见deque图表

此外，下面是一些代码示例：

// PushBack appends an element to the back of the queue.  Implements FIFO when
// elements are removed with PopFront(), and LIFO when elements are removed
// with PopBack().
func (q *Deque) PushBack(elem interface{}) {
    q.growIfFull()
    q.buf[q.tail] = elem
    // Calculate new tail position.
    q.tail = q.next(q.tail)
    q.count++
}

// next returns the next buffer position wrapping around buffer.
func (q *Deque) next(i int) int {
    return (i + 1) & (len(q.buf) - 1) // bitwise modulus
}

这个特定的实现总是使用2的幂作为缓冲区大小，因此可以更加高效地计算按位模数。

这意味着只有在全部容量被使用时才需要增长切片。通过避免在同一边界上增长和收缩存储的重新调整策略，这使得它非常节省内存。

以下是调整底层切片缓冲区的代码：

// resize resizes the deque to fit exactly twice its current contents. This is
// used to grow the queue when it is full, and also to shrink it when it is     
// only a quarter full.                                                         
func (q *Deque) resize() {
    newBuf := make([]interface{}, q.count<<1)
    if q.tail > q.head {
        copy(newBuf, q.buf[q.head:q.tail])
    } else {
        n := copy(newBuf, q.buf[q.head:])
        copy(newBuf[n:], q.buf[:q.tail])
    }
    q.head = 0
    q.tail = q.count
    q.buf = newBuf
}

另一个需要考虑的事情是是否需要在实现中构建并发安全性。你可能希望避免这一点，以便可以按照最适合你的并发策略进行操作；如果不需要，则肯定不需要它。原因与不希望具有某些内置序列化功能的切片相同。

如果在 godoc 上搜索deque，就会发现有许多基于环形缓冲区的 Go 队列实现。选择最适合你口味的一个。

- gammazero

Answer 4

向量和列表两者都可以使用，但是向量可能更适合。我这么说是因为相对于列表，向量可能更少地进行分配，并且垃圾收集（在当前Go实现中）相当昂贵。在一个小程序中，这可能无关紧要。

- Evan Shaw

---

注意：Go 1直接删除了container/vector包。使用container/vector的代码应更新为直接使用切片。Go 1发布说明: 已删除的包。SliceTricks如何使用切片实现向量相关操作。 - peterSO

切片在删除元素方面效果不佳。切片并不能替代可变向量。 - mcandre

Answer 5

编辑，清洁实现一个队列：

package main

import "fmt"

type Queue []interface{}

func (self *Queue) Push(x interface{}) {
    *self = append(*self, x)
}

func (self *Queue) Pop() interface{} {
    h := *self
    var el interface{}
    l := len(h)
    el, *self = h[0], h[1:l]
    // Or use this instead for a Stack
    // el, *self = h[l-1], h[0:l-1]
    return el
}

func NewQueue() *Queue {
    return &Queue{}
}


func main() {
  q := NewQueue()
  q.Push(1)
  q.Push(2)
  q.Push(3)
  q.Push("L")

  fmt.Println(q.Pop())
  fmt.Println(q.Pop())
  fmt.Println(q.Pop())
  fmt.Println(q.Pop())

}

或者只需将"container/list"嵌入简单实现中并公开接口：

package queue

import "container/list"

// Queue is a queue
type Queue interface {
    Front() *list.Element
    Len() int
    Add(interface{})
    Remove()
}

type queueImpl struct {
    *list.List
}

func (q *queueImpl) Add(v interface{}) {
    q.PushBack(v)
}

func (q *queueImpl) Remove() {
    e := q.Front()
    q.List.Remove(e)
}

// New is a new instance of a Queue
func New() Queue {
    return &queueImpl{list.New()}
}

- David Rz Ayala

---

你应该检查长度是否为0并弹出nil，否则会引发panic。此外，这不是线程安全的。 - zed

好的，检查长度为0和弹出空值确实是个好方法。但它不具备线程安全性是可以预料的，Java中的ArrayList或c#中的List都不具有线程安全性。基本的集合类型并不应该具备线程安全性，因为那会降低性能。 - David Rz Ayala

Answer 6

很遗憾，队列目前不是Go标准库的一部分，因此您需要编写自己的/导入他人的解决方案。这很遗憾，因为在标准库之外编写的容器无法使用泛型。

一个固定容量队列的简单示例如下：

type MyQueueElement struct {
  blah int // whatever you want
}

const MAX_QUEUE_SIZE = 16
type Queue struct {
  content  [MAX_QUEUE_SIZE]MyQueueElement
  readHead int
  writeHead int
  len int
}

func (q *Queue) Push(e MyQueueElement) bool {
  if q.len >= MAX_QUEUE_SIZE {
    return false
  }
  q.content[q.writeHead] = e
  q.writeHead = (q.writeHead + 1) % MAX_QUEUE_SIZE
  q.len++
  return true
}

func (q *Queue) Pop() (MyQueueElement, bool) {
  if q.len <= 0 {
    return MyQueueElement{}, false
  }
  result := q.content[q.readHead]
  q.content[q.readHead] = MyQueueElement{}
  q.readHead = (q.readHead + 1) % MAX_QUEUE_SIZE
  q.len--
  return result, true
}

这里需要注意的是不要让切片无限增长（通过使用切片[1:]操作来丢弃），并清零弹出的元素以确保它们的内容可以进行垃圾回收。请注意，如果像这里一样的MyQueueElement结构体只包含int，则不会有任何区别，但如果结构体包含指针，则会有所不同。

如果需要自动增长队列，则可以扩展解决方案以重新分配和复制。

此解决方案不是线程安全的，但如果需要，可以在Push / Pop中添加锁。

游乐场https://play.golang.org/

- tul

---

这是通过使用模数包装的最佳队列实现。唯一需要添加的是，如果“满了”，可以通过展开循环缓冲区来使容量加倍并复制。甚至有一个优化方法可以在两个“内存复制”中完成。 - bryanmac

Answer 7

关于实现方面，Moraes在他的gist中提出了一些队列和栈的结构。

// Stack is a basic LIFO stack that resizes as needed.
type Stack struct {
    nodes   []*Node
    count   int
}
// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
    nodes   []*Node
    head    int
    tail    int
    count   int
}

您可以在这个示例中看到它的实际应用。

- VonC

---

那个要点设计得太糟糕了=/ - Sir

Answer 8

使用切片和适当的（“循环”）索引方案仍然似乎是可行的方法。这是我的看法：https://github.com/phf/go-queue 那里的基准测试也证实了通道更快，但代价是更有限的功能。

- Peter Froehlich

---

如果从您的代码库中摘录一些更相关的代码，那么这将是一个更好的答案。 - Nathan Tuggy

我以为想要查看代码的人会直接点击链接。抱歉，我在这里还是个新手。我会更新答案并附上一些片段。 - Peter Froehlich

不要误解我的意思，这个答案本身并不差，而且肯定不会像某些表面上相似的“仅链接”答案一样被删除，但如果能多提供一些：实际代码的解释，这将使其变得更好，因为对于SO答案来说，这是最重要的。 - Nathan Tuggy

有趣的是，发布这个答案让我修改了代码，现在我的队列比通道更快。稍后会有一份修订后的答案，更加详细。 - Peter Froehlich

Answer 9

我也像上面那样使用切片来实现队列。但是，它不是线程安全的。因此，我决定添加锁（互斥锁）来保证线程安全。

package queue

import (
  "sync"
)

type Queue struct {
  lock *sync.Mutex
  Values []int
}

func Init() Queue {
  return Queue{&sync.Mutex{}, make([]int, 0)}
}

func (q *Queue) Enqueue(x int) {
  for {
    q.lock.Lock()
    q.Values = append(q.Values, x)
    q.lock.Unlock()
    return
  }
}

func (q *Queue) Dequeue() *int {
  for {
    if (len(q.Values) > 0) {
      q.lock.Lock()
      x := q.Values[0]
      q.Values = q.Values[1:]
      q.lock.Unlock()
      return &x
    }
    return nil
  }
  return nil
}

你可以在这里检查我在Github上的解决方案：简单队列。

- Dat Tran

Answer 10

您可以尝试像这样的方法：

// queue.go
package queue

type Queue struct {
    data []int
}

func (q *Queue) Enqueue(d int) {
    q.data = append(q.data, d)
}

func (q *Queue) Dequeue() int {
    dequeued := q.data[0]
    q.data = q.data[1:]
    return dequeued
}

func (q *Queue) IsEmpty() bool {
    return len(q.data) == 0
}

func NewQueue() *Queue {
    return &Queue{
        data: make([]int, 0),
    }
}

//queue_test.go

package queue

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestQueue_ShouldInitialiseWithEmpty(t *testing.T) {
    q := NewQueue()
    assert.Equal(t, true, q.IsEmpty())
}

func TestQueue_ShouldErrorIfDequeuePerformedOnEmpty(t *testing.T) {
    q := NewQueue()
    _, err := q.Dequeue()
    assert.NotNil(t, err)
    assert.Equal(t, "nothing to dequeue", err.Error())
}

func TestQueue(t *testing.T) {
    q := NewQueue()
    q.Enqueue(1)
    q.Enqueue(2)
    q.Enqueue(3)
    q.Enqueue(4)

    dequeued1, err1 := q.Dequeue()
    assert.Nil(t, err1)
    assert.Equal(t, 1, dequeued1)

    dequeued2, err2 := q.Dequeue()
    assert.Nil(t, err2)
    assert.Equal(t, 2, dequeued2)

    dequeued3, err3 := q.Dequeue()
    assert.Nil(t, err3)
    assert.Equal(t, 3, dequeued3)

    dequeued4, err4 := q.Dequeue()
    assert.Nil(t, err4)
    assert.Equal(t, 4, dequeued4)
}

- Shunmugam V