Buffers circulares y ring buffers

Un FIFO de tamaño fijo acomodado en círculo. La posición de escritura da la vuelta.

Todo el truco: el módulo

• Dos índices: head (lectura), tail (escritura)
• index = (index + 1) % capacity — regresa a 0
• O(1), sin asignación de memoria, memoria fija
• Lleno → sobrescribe el más viejo, o rechaza (backpressure)

Míralo dar la vuelta y sobrescribir

Las ranuras no se mueven; las posiciones viajan. El tail da la vuelta al final; el más viejo se sobrescribe cuando se llena.

Scratch vs librería

Ambos O(1). deque(maxlen) ≈10× más rápido (C vs un módulo de Python por push).

Dónde te lo encuentras

• Buffers de audio/red, packet rings
• dmesg, el log del kernel, "los últimos N eventos"
• deque(maxlen=N) — esto es lo que hace por debajo

Conclusión

Array fijo + dos índices que dan la vuelta = una queue infinita en O(capacity) de memoria. O(1) en el peor caso, sin pausas del GC. Siguiente nivel: hashing.