scratch/algos/queue.go (view raw)
| 1 | package algos |
| 2 | |
| 3 | type QNode[T any] struct { |
| 4 | v T |
| 5 | next *QNode[T] |
| 6 | } |
| 7 | |
| 8 | type Queue[T any] struct { |
| 9 | Len int |
| 10 | head *QNode[T] |
| 11 | tail *QNode[T] |
| 12 | } |
| 13 | |
| 14 | func (q *Queue[T]) Push(item T) { |
| 15 | node := &QNode[T]{v: item} |
| 16 | if q.Len == 0 { |
| 17 | q.head = node |
| 18 | q.tail = node |
| 19 | } else { |
| 20 | q.tail.next = node |
| 21 | q.tail = node |
| 22 | } |
| 23 | q.Len++ |
| 24 | } |
| 25 | |
| 26 | func (q *Queue[T]) Peek() T { |
| 27 | return q.head.v |
| 28 | } |
| 29 | |
| 30 | func (q *Queue[T]) Pop() (T, bool) { |
| 31 | if q.Len == 0 { |
| 32 | var t T |
| 33 | return t, false |
| 34 | } |
| 35 | |
| 36 | res := q.head.v |
| 37 | q.head = q.head.next |
| 38 | if q.head == nil { |
| 39 | q.tail = nil |
| 40 | } |
| 41 | q.Len-- |
| 42 | return res, true |
| 43 | } |
| 44 | |
| 45 | /// Ring buffer based |
| 46 | |
| 47 | type RQueue[T any] struct { |
| 48 | buf []T |
| 49 | head, tail int |
| 50 | Len int |
| 51 | } |
| 52 | |
| 53 | func (q *RQueue[T]) Enqueue(v T) { |
| 54 | if q.Len == len(q.buf) { |
| 55 | q.grow() |
| 56 | } |
| 57 | q.buf[q.tail] = v |
| 58 | q.tail = (q.tail + 1) % len(q.buf) |
| 59 | q.Len++ |
| 60 | } |
| 61 | |
| 62 | func (q *RQueue[T]) Peek() T { |
| 63 | return q.buf[q.head] |
| 64 | } |
| 65 | |
| 66 | func (q *RQueue[T]) Dequeue() (T, bool) { |
| 67 | var zero T |
| 68 | if q.Len == 0 { |
| 69 | return zero, false |
| 70 | } |
| 71 | v := q.buf[q.head] |
| 72 | q.buf[q.head] = zero |
| 73 | q.head = (q.head + 1) % len(q.buf) |
| 74 | q.Len-- |
| 75 | return v, true |
| 76 | } |
| 77 | |
| 78 | func (q *RQueue[T]) grow() { |
| 79 | newCap := max(8, len(q.buf)*2) |
| 80 | newBuf := make([]T, newCap) |
| 81 | if q.head < q.tail { |
| 82 | copy(newBuf, q.buf[q.head:q.tail]) |
| 83 | } else { |
| 84 | head := copy(newBuf, q.buf[q.head:]) |
| 85 | copy(newBuf[head:], q.buf[:q.tail]) |
| 86 | } |
| 87 | q.head = 0 |
| 88 | q.tail = q.Len |
| 89 | q.buf = newBuf |
| 90 | } |