Jak efektivně odstranit první prvek z dynamického pole v konstantním čase?

V Go jsou dynamické pole reprezentovány pomocí řezů (slices). Odstranění prvního prvku z řezů se obvykle provádí pomocí posunutého řezání:

slice = slice[1:]

Tato operace se provádí v konstantním čase, protože nekopíruje prvky, pouze mění ukazatele a délku řezu.

Pokud však chcete zachovat původní pole a zabránit hromadění nevyužité paměti, můžete použít kruhový buffer (ring buffer) nebo frontu implementovanou na základě řezů s dvěma indexy (začátek a konec). To umožní efektivně odstranit první prvek v O(1), aniž by bylo nutné posouvat ostatní prvky.

Pří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
}

Protože je vhodnější použít datovou strukturu, která podporuje tuto operaci, než přímo řez, je efektivnější ji použít pro odstranění prvního prvku v konstantním čase.