Skip to content

Instantly share code, notes, and snippets.

@helinwang
Last active July 21, 2018 18:06
Show Gist options
  • Save helinwang/ee7546c60962ccf2e46256b6cba642ca to your computer and use it in GitHub Desktop.
Save helinwang/ee7546c60962ccf2e46256b6cba642ca to your computer and use it in GitHub Desktop.
Simple queue implementation
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())
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment