有队列实现吗？

Question

任何人都可以提出转到容器,简单快速的FIF /队列,Go有3个不同的容器:heap,list和vector.哪一个更适合实现队列？

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 !")
}

当然,我们假设我们可以信任追加和切片的内部实现,以避免无用的调整大小和重新分配.对于基本用法,这是完全足够的.

Answer 2

令人惊讶的是,没有人建议缓冲通道,无论如何,对于大小限制的FIFO队列.

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

//Push
c <- value

//Pop
x <- c

Answer 3

矢量或列表应该可以工作,但矢量可能是要走的路.我这样说是因为vector可能比list更少分配和垃圾收集(在当前的Go实现中)相当昂贵.但是,在一个小程序中,它可能无关紧要.

Answer 4

大多数队列实现都属于以下三种风格之一：基于切片、基于链表和基于循环缓冲区（环形缓冲区）。

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

基于环形缓冲区的队列通过包装其存储来重用内存：当队列增长到超出底层切片的一端时，它会向切片的另一端添加额外的节点。查看双端队列图

另外，一些代码来说明：

// 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 队列实现。选择最适合您口味的一种。

Answer 5

为了扩展实现方面,Moraes在他的要点中提出了一些来自队列和堆栈的结构:

// 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
}

您可以在此操场示例中看到它的运行情况.

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:] 操作进行丢弃而导致），以及将弹出元素清零以确保其内容可用于垃圾回收。请注意，在像这里这样的结构仅包含 int 的情况下MyQueueElement，这不会有任何区别，但如果结构包含指针，则会有区别。

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

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

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

Answer 7

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

Answer 8

我还如上所述从切片实现了队列。但是，它不是线程安全的。所以我决定加一个锁（互斥锁）来保证线程安全。

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 上查看我的解决方案，简单队列

Answer 9

编辑，更清晰的队列实现：

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