-
Notifications
You must be signed in to change notification settings - Fork 23
/
queue.go
56 lines (44 loc) · 938 Bytes
/
queue.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package circ
type Queue[T any] struct {
arr []T
begin int
len int
}
func NewQueue[T any](capacity int) *Queue[T] {
return &Queue[T]{
// TODO: Do not preallocate whole capacity of Go upstream
// accepts this: https://github.com/golang/go/issues/55978
arr: make([]T, capacity),
}
}
func (q *Queue[T]) Cap() int { return len(q.arr) }
func (q *Queue[T]) Len() int { return q.len }
func (q *Queue[T]) end() int {
e := q.begin + q.len
if l := len(q.arr); e >= l {
e -= l
}
return e
}
func (q *Queue[T]) Enqueue(elem T) {
if q.len == len(q.arr) {
panic("enqueue: queue is full")
}
q.arr[q.end()] = elem
q.len++
}
func (q *Queue[T]) Dequeue() T {
if q.len < 1 {
panic("dequeue: queue is empty")
}
elem := q.arr[q.begin]
// Avoid memory leaks if T is pointer or contains pointers.
var zeroVal T
q.arr[q.begin] = zeroVal
q.len--
q.begin++
if q.begin == len(q.arr) {
q.begin = 0
}
return elem
}