任何人都可以为简单快速的 FIF/队列推荐 Go 容器，Go 有 3 个不同的容器heap：list和vector. 哪个更适合实现队列？
问问题
89630 次
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。
于 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 回答