How to implement a simple queue properly?

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

When Enqueue fails, you're still incrementing p.tail, so next time it will appear not to fail -- that explains the single false in your first loop (and messes everything up for the second one). The original algorithm says OVERFLOW meaning "give everything up", not "just keep going as if nothing untowards happened";-).

All you need to do is decrement p.tail if you've checked that failure's occurring -- or put the incremented value in a local temporary and move it to p.tail only if failure is not occurring, that may be more elegant. This way, the failing Enqueue does not enqueue the new value, but the queue itself (without that overflowing value) is still semantically intact and correct for future operations.

Answer 2

It's true that there's no package called queue, but either vector or list would make fine queues. Also see this question.

Answer 3

I modify the original implementation to make a dynamic queue. I.e. when the queue fills up it will allocate a larger queue and move all the items over.

package main

import (
    "fmt"
)

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

func NextPowerOfTwo(v uint) uint {
    if v == 0 {
        return 1
    }
    v--
    v |= v >> 1
    v |= v >> 2
    v |= v >> 4
    v |= v >> 8
    v |= v >> 16
    v++
    return v
}

func NewQueue(n uint) *Queue {
    n = NextPowerOfTwo(n)
    if n < 4 {
        n = 4
    }
    println("create queue of", n)
    return &Queue{n, 0, 0, make([]int, n)}
}

func (p *Queue) Resize() {
    if p.head == (p.tail + 1) % p.len {
        new_len := p.len * 2;
        new_q := make([]int, new_len)
        // currently there are (len - 1) items in the queue
        var i uint
        for i = 0; i < p.len - 1; i++ {
            n, _ := p.Dequeue()
            new_q[i] = n
        }
        p.q = new_q
        p.head, p.tail = 0, p.len - 1
        p.len = new_len
        println("queue resized to ", p.len)
    }
}

func (p *Queue) Enqueue(x int) {
    p.Resize();
    p.q[p.tail] = x
    p.tail = (p.tail + 1) % p.len
}

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

func main() {
    q := NewQueue(1)
    for i := 1; i < 13; i++ {
        q.Enqueue(2 * i + 1)
        println("enqueued item ", i)
    }
    println("** queue content **")
    for i := 1; i < 13 + 1; i++ {
        fmt.Println(q.Dequeue())
    }
}