Большинство реализаций очереди представлены в одном из трех вариантов: на основе слайса, на основе связанного списка и на основе кольцевого буфера (кольцевой буфер).
- Очереди на основе слайсов имеют тенденцию тратить впустую память, потому что они не используют память, ранее занятую удаленными элементами. Кроме того, очереди на основе срезов имеют тенденцию быть только односторонними.
- Очереди со связным списком могут быть лучше с памятью Повторное использование , но, как правило, немного медленнее и используют больше памяти в целом из-за накладных расходов на поддержание ссылок. Они могут предлагать возможность добавлять и удалять элементы из середины очереди, не перемещая память, но если вы делаете большую часть этой очереди, неправильная структура данных.
- Очереди кольцевого буфера предлагают всю эффективность срезов, с преимуществом не тратить память. Меньшее распределение означает лучшую производительность. Они одинаково эффективны при добавлении и удалении элементов с любого конца, поэтому вы, естественно, получаете двустороннюю очередь. Поэтому в качестве общей рекомендации я бы рекомендовал реализацию очереди на основе кольцевого буфера. Это то, что обсуждается в оставшейся части этого поста.
Очередь, основанная на кольцевом буфере, повторно использует память, оборачивая свое хранилище: по мере того, как очередь выходит за пределы одного конца основного слайса, она добавляет дополнительные узлы к другому концу слайса. См Диаграмма deque
Также немного кода для иллюстрации:
// PushBack appends an element to the back of the queue. Implements FIFO when
// elements are removed with PopFront(), and LIFO when elements are removed
// with PopBack().
func (q *Deque) PushBack(elem interface{}) {
q.growIfFull()
q.buf[q.tail] = elem
// Calculate new tail position.
q.tail = q.next(q.tail)
q.count++
}
// next returns the next buffer position wrapping around buffer.
func (q *Deque) next(i int) int {
return (i + 1) & (len(q.buf) - 1) // bitwise modulus
}
Эта конкретная реализация всегда использует размер буфера, равный степени 2, и поэтому может вычислить побитовый модуль, чтобы быть немного более эффективным.
Это означает, что срез должен расти только тогда, когда все его возможности исчерпаны. Благодаря стратегии изменения размера, позволяющей избежать увеличения и уменьшения объема хранилища на одной границе, это делает его очень эффективным для использования памяти.
Вот код, который изменяет размер нижележащего буфера слайса:
// resize resizes the deque to fit exactly twice its current contents. This is
// used to grow the queue when it is full, and also to shrink it when it is
// only a quarter full.
func (q *Deque) resize() {
newBuf := make([]interface{}, q.count<<1)
if q.tail > q.head {
copy(newBuf, q.buf[q.head:q.tail])
} else {
n := copy(newBuf, q.buf[q.head:])
copy(newBuf[n:], q.buf[:q.tail])
}
q.head = 0
q.tail = q.count
q.buf = newBuf
}
Еще одна вещь, которую нужно учитывать, - если вы хотите, чтобы безопасность параллелизма была встроена в реализацию. Возможно, вы захотите избежать этого, чтобы вы могли делать все, что лучше всего подходит для вашей стратегии параллелизма, и вы определенно не хотите этого, если она вам не нужна; та же причина, по которой не нужен фрагмент, имеющий некоторую встроенную сериализацию.
Существует ряд реализаций очереди на основе кольцевого буфера для Go, если вы выполняете поиск по godoc для deque. Выберите тот, который лучше всего соответствует вашим вкусам.