I have seen some implementations of FIFO Queues using slices in Go. As items exit the queue can this memory be freed up without reallocating the underlying array? If this doesn't occur it would seem to me that the queue would leak a ton of memory. This is what I mean:
type queue
{
[]int
int head
}
func (q *queue) enqueue(val int) {
q = append(q, val)
}
func (q *queue) dequeue() int {
return (*q)[q.head++]
}
After calling enqueue/dequeue a bunch of times, the low indexes of the array underying the slice are no longer usable but I am not sure how they can be freed either. Can someone point me to a proper queue implementation that does not use pointers, and doesn't leak memory like this or have performance issues? Alternatively a description of how this might work would also be appreciated.
Thank you, Plamen
You can use a circular buffer. From wikipedia:
A circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.
...
Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a linked list approach may be preferred instead.
Here's a package that implements this: https://github.com/eapache/queue.
Depending on the use case, a channel is also a good way to implement a queue. It blocks, but using a select with a default you can avoid that behavior:
select {
case msg := <-queue:
default:
}