79

任何人都可以为简单快速的 FIF/队列推荐 Go 容器，Go 有 3 个不同的容器heap：list和vector. 哪个更适合实现队列？

4

15 回答 15

117

事实上，如果你想要的是一个基本且易于使用的 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 !")
}

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

于 2014-11-11T11:22:14.643 回答
85

惊讶地看到还没有人建议缓冲通道，因为无论如何都是大小受限的 FIFO 队列。

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

//Push
c <- value

//Pop
x <- c
于 2016-09-20T15:46:48.090 回答
15

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

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

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

另外，一些代码来说明：

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

于 2018-05-18T20:27:56.023 回答
13

向量或列表都应该工作，但向量可能是要走的路。我这么说是因为 vector 分配的频率可能比 list 少，而且垃圾收集（在当前的 Go 实现中）相当昂贵。不过，在一个小程序中，它可能无关紧要。

于 2010-05-12T13:56:56.510 回答
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()}
}
于 2019-03-18T05:06:13.933 回答
8

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

您可以在这个操场示例中看到它的实际效果。

于 2012-08-01T10:18:24.477 回答
5

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

于 2017-04-22T02:16:56.893 回答
4

不幸的是，队列目前不是 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 的结构，它不会有任何区别，但如果 struct 包含指针，它会。

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

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

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

于 2018-06-08T11:08:45.760 回答
2

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

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 上的解决方案simple queue

于 2017-08-22T02:49:51.970 回答
1

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

于 2019-01-08T00:33:07.980 回答
1 
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
}

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

于 2020-05-19T21:00:57.800 回答
0

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

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())
        }
}
于 2018-07-17T06:31:46.440 回答
0

O(1) EnQueue、DeQueue、前后查找的时间 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())
}
于 2022-02-16T06:03:40.907 回答
-1

双栈实现：

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
}
于 2018-09-16T05:39:49.027 回答
-2

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

于 2017-06-04T09:54:11.067 回答