任何人都可以建议Go容器用于简单快速的FIF /队列，Go有3个不同的容器：heap，list和vector。哪一个更适合实现队列？
矢量或列表应该可以工作，但矢量可能是要走的路。我这样说是因为vector可能比list更少分配和垃圾收集（在当前的Go实现中）相当昂贵。但是，在一个小程序中，它可能无关紧要。
我实现了一个自动扩展底层缓冲区的队列：
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())
}
}
双栈实现：
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
}
list足以用于队列和堆栈，我们要做的是l.Remove(l.Front())用于队列轮询，l.Remove(l.Back())for堆栈轮询，PushBack用于堆栈和队列的添加操作。列表有前后指针，时间复杂度为O（1）
切片可用于实现队列。
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上的完整实现
事实上，如果你想要的是一个基本的，易于使用的fifo队列，切片提供了你所需要的一切。
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 !")
}
当然，我们假设我们可以信任追加和切片的内部实现，以避免无用的调整大小和重新分配。对于基本用法，这是完全足够的。
令人惊讶的是，没有人建议缓冲通道，无论如何，对于大小限制的FIFO队列。
//Or however many you might need + buffer.
c := make(chan int, 300)
//Push
c <- value
//Pop
x <- c
为了扩展实现方面，Moraes在his 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
}
你可以在这个playground example中看到它的实际效果。
在顶部使用切片和适当的（“循环”）索引方案似乎仍然是要走的路。以下是我对它的看法：https://github.com/phf/go-queue那里的基准测试也证实了渠道更快，但代价更加有限。
大多数队列实现有三种类型之一：基于切片，基于链表和循环缓冲（环缓冲）。
基于环形缓冲区的队列通过包装其存储来重用内存：当队列增长超出底层切片的一端时，它会将另外的节点添加到切片的另一端。见deque diagram
还有一些代码来说明：
// 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
}
这个particular implementation总是使用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有很多基于ring-buffer的队列实现。选择一个最适合您口味的。
不幸的是，队列目前不是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
}
这里避免的问题包括没有无限制的切片增长（由于使用slice [1：]操作丢弃），并将弹出的元素清零以确保其内容可用于垃圾回收。注意，如果MyQueueElement结构只包含像这里的int，它将没有区别，但如果struct包含指针，它会。
如果需要自动增长队列，可以将解决方案扩展为重新分配和复制。
此解决方案不是线程安全的，但如果需要，可以向Push / 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()}
}
我也像上面那样从slice实现了队列。但是，它不是线程安全的。所以我决定添加一个锁（互斥锁）来保证线程安全。
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