有队列实现吗？

Question

谁能建议Go容器来实现简单快速的FIFO/队列，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

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

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

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

另外，还有一些代码来说明：

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

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

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

}

或者只是在简单的实现中嵌入一个“容器/列表”并公开接口：

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

Answer 5

向量或列表都应该有效，但向量可能是最佳选择。我这样说是因为向量的分配频率可能比列表少，而且垃圾收集（在当前的 Go 实现中）相当昂贵。不过，在小程序中这可能并不重要。

Answer 6

为了在实施方面进行扩展，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 7

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

Answer 8

不幸的是，队列目前不是 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/

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

Answer 10

从 Go v1.18 开始，添加了泛型，我将用它来创建泛型队列。

以下是我的实现

type queue[T any] struct {
    bucket []T
}

func newQueue[T any]() *queue[T] {
    return &queue[T]{
        bucket: []T{},
    }
}

func (q *queue[T]) append(input T) {
    q.bucket = append(q.bucket, input)
}

func (q *queue[T]) tryDequeue() (T, bool) {
    if len(q.bucket) == 0 {
        var dummy T
        return dummy, false
    }
    value := q.bucket[0]
    var zero T
    q.bucket[0] = zero // Avoid memory leak
    q.bucket = q.bucket[1:]
    return value, true
}

每当调用出队时，都会调整队列大小以使用切片释放内存，以避免复制内存。这不是线程安全的，在这些情况下，通道可能更好 - 但需要知道队列容量才能指定正确的缓冲区大小。

为了好玩，我对使用 interface{} 的队列进行了基准测试 - 这是在 Go v1.18 之前获得通用解决方案的方法。
该测试追加 1、10、100 和 1.000 个整数并将其出列。在所有情况下，泛型速度更快，内存使用量更少。

Benchmark_queues/QueueGeneric-Size_1-8          38296201                32.78 ns/op            8 B/op          1 allocs/op
Benchmark_queues/QueueInterface-Size_1-8        11626666                147.6 ns/op           16 B/op          1 allocs/op
Benchmark_queues/QueueGeneric-Size_10-8          7846665                168.2 ns/op          160 B/op          2 allocs/op
Benchmark_queues/QueueInterface-Size_10-8        1501284                752.8 ns/op          320 B/op          2 allocs/op
Benchmark_queues/QueueGeneric-Size_100-8         1000000                 1088 ns/op         1536 B/op          1 allocs/op
Benchmark_queues/QueueInterface-Size_100-8        240232                 6798 ns/op         3072 B/op          1 allocs/op
Benchmark_queues/QueueGeneric-Size_1000-8         120244                13468 ns/op        17920 B/op          3 allocs/op
Benchmark_queues/QueueInterface-Size_1000-8        20310                54528 ns/op        35776 B/op          4 allocs/op

下面给出了使用 interface{} 的队列实现 - 添加了我认为必要的错误处理。

type queueInterface struct {
    bucket []interface{}
}

func newQueueInterface() *queueInterface {
    return &queueInterface{
        bucket: []interface{}{},
    }
}

func (q *queueInterface) append(input interface{}) error {
    if len(q.bucket) != 0 && reflect.TypeOf(q.bucket[0]) != reflect.TypeOf(input) {
        return errors.New("input type not same as those already in queue")
    }
    q.bucket = append(q.bucket, input)
    return nil
}

func (q *queueInterface) tryDequeue(out interface{}) (bool, error) {
    if len(q.bucket) == 0 {
        return false, nil
    }

    valuePtr := reflect.ValueOf(out)
    if valuePtr.Kind() != reflect.Ptr {
        return false, errors.New("must be a pointer")
    }

    value := q.bucket[0]
    if valuePtr.Elem().Type() != reflect.TypeOf(value) {
        return false, errors.New("output must be of same type as queue elements")
    }
    valuePtr.Elem().Set(reflect.ValueOf(value))

    var zero interface{}
    q.bucket[0] = zero // Avoid memory leak
    q.bucket = q.bucket[1:]
    return true, nil
}

Answer 11

你可以尝试这样的事情，

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

Answer 12

type Queue struct {
    slice []int
    len   int
}
func newq() Queue {
    q := Queue{}
    q.slice = make([]int, 0)
    q.len = 0
    return q
}
func (q *Queue) Add(v int) {
    q.slice = append(q.slice, v)
    q.len++
}

func (q *Queue) PopLeft() int {
    a := q.slice[0]
    q.slice = q.slice[1:]
    q.len--
    return a
}
func (q *Queue) Pop() int {
    a := q.slice[q.len-1]
    q.slice = q.slice[:q.len-1]
    q.len--
    return a
}

对于您的基本需求，上面的代码就可以了

Answer 13

入队、出队、Front 和 Front 的时间为 O(1)后方查找
O(n) 容量空间

type Queue struct {
    front    int
    rear     int
    size     int
    capacity int
    q        []string
}

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

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}
func (q *Queue) EnQueue(s string) error {
    if q.IsFull() {
        return fmt.Errorf("queue is full")
    }
    q.rear = (q.rear + 1) % q.capacity
    q.q[q.rear] = s
    q.size++
    return nil
}

func (q *Queue) DeQueue() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("queue is empty")
    }
    defer func() { q.front, q.size = (q.front+1)%q.capacity, q.size-1 }()
    return q.q[q.front], nil

}

func (q *Queue) Front() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("queue is empty")
    }
    return q.q[q.front], nil
}

func (q *Queue) Rear() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("queue is empty")
    }
    return q.q[q.rear], nil
}

func (q *Queue) Print() []string {
    return q.q[q.front : q.rear+1]
}

func New(capacity int) *Queue {
    q := &Queue{
        capacity: capacity,
        rear:     capacity - 1,
        q:        make([]string, capacity),
    }
    return q
}

func main() {
    queue := New(6)
    queue.EnQueue("10")
    queue.EnQueue("20")
    queue.EnQueue("30")
    queue.EnQueue("40")
    queue.EnQueue("50")
    queue.EnQueue("60")
    fmt.Println(queue.EnQueue("70")) // Test Capcacity Exceeded EnQueue.
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue()) // Test Empty DeQueue.
    fmt.Println(queue.Print())
    queue.EnQueue("80")
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.Print())
}

Answer 14

我实现了一个将自动扩展底层缓冲区的队列：

package types

// Note: this queue does not shrink the underlying buffer.                                                                                                               
type queue struct {
        buf  [][4]int // change to the element data type that you need                                                                                                   
        head int
        tail int
}

func (q *queue) extend(need int) {
        if need-(len(q.buf)-q.head) > 0 {
                if need-len(q.buf) <= 0 {
                        copy(q.buf, q.buf[q.head:q.tail])
            q.tail = q.tail - q.head
                        q.head = 0
                        return
                }

                newSize := len(q.buf) * 2
                if newSize == 0 {
                    newSize = 100
            }
                newBuf := make([][4]int, newSize)
                copy(newBuf, q.buf[q.head:q.tail])
                q.buf = newBuf
        q.tail = q.tail - q.head
                q.head = 0
        }
}

func (q *queue) push(p [4]int) {
        q.extend(q.tail + 1)
        q.buf[q.tail] = p
        q.tail++
}

func (q *queue) pop() [4]int {
        r := q.buf[q.head]
        q.head++
        return r
}

func (q *queue) size() int {
        return q.tail - q.head
}


// put the following into queue_test.go
package types

import (
        "testing"

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

func TestQueue(t *testing.T) {
        const total = 1000
        q := &queue{}
        for i := 0; i < total; i++ {
                q.push([4]int{i, i, i, i})
                assert.Equal(t, i+1, q.size())
        }

    for i := 0; i < total; i++ {
                v := q.pop()
                assert.Equal(t, [4]int{i, i, i, i}, v)
                assert.Equal(t, total-1-i, q.size())
        }
}

Answer 15

list 对于队列和堆栈来说就足够了，我们应该做的是 l.Remove(l.Front()) 对于队列 Poll，l.Remove(l.Back()) >用于堆栈轮询，PushBack 用于堆栈和队列的添加操作。 list有前后指针，时间复杂度为O(1)

Answer 16

双栈实现：

O(1) Enqueue 和 Dequeue 并使用 slices （这对于缓存来说往往更好）错过）。

type Queue struct{
    enqueue, dequeue Stack
}

func (q *Queue) Enqueue(n *Thing){
    q.enqueue.Push(n)
}

func (q *Queue) Dequeue()(*Thing, bool){
    v, ok := q.dequeue.Pop()
    if ok{
        return v, true
    }

    for {
        v, ok := d.enqueue.Pop()
        if !ok{
            break
        }

        d.dequeue.Push(v)
    }

    return d.dequeue.Pop()
}

type Stack struct{
    v []*Thing
}

func (s *Stack)Push(n *Thing){
    s.v=append(s.v, n)
}

func (s *Stack) Pop()(*Thing, bool){
    if len(s.v) == 0 {
        return nil, false
    }

    lastIdx := len(s.v)-1
    v := s.v[lastIdx]
    s.v=s.v[:lastIdx]
    return v, true
}

Answer 17

在Golang中实现队列数据结构的最简单方法是使用切片。

由于队列遵循 FIFO（先进先出）结构，因此可以按如下方式执行出队和入队操作：

• 使用内置的追加函数入队。
• 切掉第一个要出列的元素。

下面的代码片段使用切片实现了一个基本队列。请注意入队和出队是如何在切片的两端发生的。

package main
import "fmt"

func enqueue(queue[] int, element int) []int {
  queue = append(queue, element); // Simply append to enqueue.
  fmt.Println("Enqueued:", element);
  return queue
}

func dequeue(queue[] int) ([]int) {
  element := queue[0]; // The first element is the one to be dequeued.
  fmt.Println("Dequeued:", element)
  return queue[1:]; // Slice off the element once it is dequeued.
}

func main() {
  var queue[] int; // Make a queue of ints.

  queue = enqueue(queue, 10);
  queue = enqueue(queue, 20);
  queue = enqueue(queue, 30);

  fmt.Println("Queue:", queue);

  queue = dequeue(queue);
  fmt.Println("Queue:", queue);

  queue = enqueue(queue, 40);
  fmt.Println("Queue:", queue);
}

警告（内存泄漏）：在上面的出队函数中，内存
分配给数组中第一个元素的分配永远不会返回。

我们可以使用动态数据结构（链表）来避免内存泄漏。示例代码如下：

package main
import "container/list"
import "fmt"

func main() {
    // new linked list
    queue := list.New()

    // Simply append to enqueue.
    queue.PushBack(10)
    queue.PushBack(20)
    queue.PushBack(30)

    // Dequeue
    front:=queue.Front()
    fmt.Println(front.Value)
    // This will remove the allocated memory and avoid memory leaks
    queue.Remove(front)
}

Answer 18

package queue

type Queue struct {
    data []any
}

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

func (q *Queue) Dequeue() any {
    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([]any, 0),
    }
}

Answer 19

Slice可以用来实现队列。

type queue struct {
    values []*int
}

func New() *queue {
   queue := &queue{}
   return queue
}

func (q *queue) enqueue(val *int) {
   q.values = append(q.values, val)
}

//deque function

更新：

这是我的 GitHub 页面上的完整实现 https://github.com/raiskumar/algo-ds/blob/master/tree/queue.go