Ako efektívne odstrániť prvý prvok z dynamického poľa v konštantnom čase?

V Go sú dynamické polia reprezentované pomocou rezov (slices). Odstránenie prvého prvku z rezov sa zvyčajne vykonáva pomocou posunutého rezovania:

slice = slice[1:]

Táto operácia sa vykonáva v konštantnom čase, pretože nekopíruje prvky, iba mení ukazovatele a dĺžku rezov.

Ak však chcete zachovať pôvodné pole a vyhnúť sa hromadeniu nevyužitej pamäti, môžete použiť kruhový buffer (ring buffer) alebo frontu implementovanú na základe rezov s dvoma indexmi (začiatok a koniec). To umožní efektívne odstrániť prvý prvok v O(1), bez posúvania ostatných prvkov.

Príklad kruhového bufferu:

type RingBuffer struct {
    data []int
    start int
    size  int
}

func (r *RingBuffer) PopFront() int {
    if r.size == 0 {
        panic("buffer is empty")
    }
    val := r.data[r.start]
    r.start = (r.start + 1) % len(r.data)
    r.size--
    return val
}

Preto je efektívnejšie použiť dátovú štruktúru, ktorá podporuje túto operáciu, než priamo s rezom.