How to implement a queue in Go?

Question

The current Go library doesn't provide the queue container. To implement a simple queue, I use circle array as the underlying data structure. It follows algorithms mentioned in TAOCP:

Insert Y into queue X: X[R]<-Y; R<-(R+1)%M; if R=F then OVERFLOW.
Delete Y from queue X: if F=R then UNDERFLOW; Y<-X[F]; F<-(F+1) % M.
F: Front, R: Rear, M: Array length.

Following is the code:

package main

import (
    "fmt"
)

type Queue struct {
    len        int 
    head, tail int 
    q          []int
}

func New(n int) *Queue {
    return &Queue{n, 0, 0, make([]int, n)} 
}

func (p *Queue) Enqueue(x int) bool {
    p.q[p.tail] = x 
    p.tail = (p.tail + 1) % p.len
    return p.head != p.tail
}

func (p *Queue) Dequeue() (int, bool) {
    if p.head == p.tail {
        return 0, false
    }   
    x := p.q[p.head]
    p.head = (p.head + 1) % p.len
    return x, true
}

func main() {
    q := New(10)
    for i := 1; i < 13; i++ {
        fmt.Println(i, q.Enqueue(i))
    }   
    fmt.Println()
    for i := 1; i < 13; i++ {
        fmt.Println(q.Dequeue())
    }   
}

But the output is obviously wrong:

1 true 2 true 3 true 4 true 5 true 6 true 7 true 8 true 9 true 10 false 11 true 12 true

11 true 12 true 0 false 0 false 0 false 0 false 0 false 0 false 0 false 0 false 0 false 0 false

I think I need one more field to make the code work properly. What do you suggest?

The improved code has a small shortcoming: an array of size n can contain only n-1 elements.

package main

import (
    "fmt"
)

type Queue struct {
    len        int 
    head, tail int 
    q          []int
}

func New(n int) *Queue {
    return &Queue{n, 0, 0, make([]int, n)} 
}

func (p *Queue) Enqueue(x int) bool {
    p.q[p.tail] = x 
    ntail := (p.tail + 1) % p.len
    ok := false
    if ntail != p.head {
        p.tail = ntail
        ok = true
    }   
    return ok
}

func (p *Queue) Dequeue() (int, bool) {
    if p.head == p.tail {
        return 0, false
    }   
    x := p.q[p.head]
    p.head = (p.head + 1) % p.len
    return x, true
}

func main() {
    q := New(10)
    for i := 1; i < 13; i++ {
        fmt.Println(i, q.Enqueue(i))
    }   
    fmt.Println()
    for i := 1; i < 13; i++ {
        fmt.Println(q.Dequeue())
    }   
}

Answer 1

You do not need all this hustle in any reasonable go version (after 1.x). Everything can be achieved with slices.

queue := []int{}

Add to a queue:

queue = append(queue, 6)

Pop from a queue:

el := queue[0]
queue = queue[1:]

---

Here is implementation that shows that pop does not take a lot of time (in fact here it is shorter than push because in my opinion of reallocation of memory when the queue is growing).

package main

import (
    "fmt"
    "time"
)

func main() {
    n := 10000000
    queue := []int{1, 2, 3}

    start := time.Now()
    for i := 0; i < n; i++ {
        queue = append(queue, i)
    }
    elapsed := time.Since(start)
    fmt.Println(elapsed)

    start = time.Now()
    for i := 0; i < n; i++ {
        _ = queue[0]
        queue = queue[1:]
    }
    elapsed = time.Since(start)
    fmt.Println(elapsed)
    fmt.Println(queue)
}

On my machine the numbers are:

216.611664ms
13.441106ms

From @DaveC's comment:

This is simple and works very well for everything except critical code where allocations (pressure on the garbage collector) is undesirable.Two things to note, first it does keep re-allocating the underlying array on push (although efficiently and not on every call) and pop doesn't free any space until that happens. This leads to the second thing, if (as is common) the queue contains a pointer to something, then it's good to do queue[0] = nil; queue = queue[1:] to have the queue stop referencing the pointer right away.