Colas
Sacar el primero de 1000 valores de un arreglo de JavaScript con shift mueve los otros 999; un búfer circular hace el mismo trabajo en un paso.
El primero en entrar, el primero en salir
Una cola es la fila en el mostrador de una tienda. La gente se forma al final y la atienden por delante, así que quien llegó primero se va primero. La regla es primero en entrar, primero en salir (FIFO). Las dos operaciones son enqueue (encolar), que agrega un valor al final, y dequeue (desencolar), que quita el valor del frente. En las notas del 6.006 del MIT, una cola es la interfaz de secuencia limitada a insert last(x) y delete first().
Las colas están en todos los lugares donde el trabajo debe atenderse en orden de llegada: documentos esperando a una impresora, pulsaciones de teclas esperando a un programa, mensajes esperando a un servidor. La búsqueda en anchura, del curso de algoritmos, guarda en una cola las casillas que todavía tiene que visitar, y precisamente por eso explora en anillos de igual distancia.
La forma fácil y su costo oculto
En JavaScript, la cola obvia es un arreglo: push para encolar al final y shift para desencolar del frente. Funciona, y para colas cortas está bien. Pero fíjate en lo que hace shift. MDN dice que "desplaza todos los valores 1 posición a la izquierda", y la especificación de ECMAScript lo escribe como un bucle que copia el elemento k a la posición k − 1 para cada k. El principio de un arreglo es el extremo caro, como mostró la primera unidad. Desencolar de una cola de n valores cuesta 1 lectura más n − 1 movimientos, así que una cola de 1000 valores cuesta 1000 pasos por cada dequeue. (Los motores pueden usar atajos internos, pero la especificación no promete nada).
Si encolas 5 valores en un arreglo vacío y luego desencolas los 5, los enqueue cuestan 5 pasos y los dequeue cuestan 5 + 4 + 3 + 2 + 1 = 15, en total 20. Casi todo eso es mover valores que ni siquiera se están quitando.
No muevas los valores, mueve el frente
La solución es dejar de mover valores y, en cambio, recordar dónde está el frente. Guarda un índice llamado head. Dequeue lee el valor en head y le suma 1 a head; nada más se mueve. El inconveniente es que las celdas antes de head se desperdician. Un búfer circular (ring buffer) las reutiliza: el arreglo tiene un número fijo de celdas, digamos 8, y las posiciones dan la vuelta, así que la celda que sigue a la 7 es la 0. Guarda head y size. El siguiente enqueue va a la celda (head + size) mod 8, y un dequeue toma la celda head y mueve head a (head + 1) mod 8. Las dos operaciones son 1 paso. El precio es una capacidad fija: cuando size llega a 8 la cola está llena, a menos que copies todo a un anillo más grande, como haría un arreglo dinámico.
Arrastra para girar. Desplaza o pellizca para acercar.
| Cola de n valores | Encolar | Desencolar |
|---|---|---|
| Arreglo con push y shift | 1 (amortizado) | 1 lectura + (n − 1) movimientos |
| Arreglo con un índice head | 1 (amortizado) | 1, pero se desperdician las celdas del frente |
| Búfer circular de tamaño fijo | 1, o llena | 1 |
¿Cuál conviene usar? Para una cola que nunca tiene más de unas cuantas decenas de valores, push y shift es corto y claro, y los movimientos casi no cuestan nada. Para una cola por la que pasan miles de elementos, como las casillas de una búsqueda en anchura grande, un índice head o un búfer circular mantienen cada dequeue en un paso, y la diferencia crece con el largo de la fila.
| FIFO | Primero en entrar, primero en salir: los valores salen en el orden en que llegaron. |
| Enqueue / dequeue (encolar / desencolar) | Agregar al final / quitar del frente. |
| shift | Quita el primer valor del arreglo y mueve todos los demás una celda a la izquierda. |
| Búfer circular | Un arreglo fijo usado en círculo: la siguiente celda libre es (head + size) mod capacidad. |
- ¿En qué orden devuelve los valores una cola?
- El primero en entrar, el primero en salir
- El último en entrar, el primero en salir
- El más grande primero
- En orden aleatorio
- Encola A, B, C. Desencola una vez. Encola D. Ahora desencola hasta vaciarla. Ordena esos valores.
- Con push y shift, ¿cuántos pasos lleva un dequeue en una cola de 4 valores (1 lectura más los movimientos)?
- El mismo método, una cola de 1000 valores: ¿cuántos pasos lleva un dequeue?
- Empieza con un arreglo vacío. Encola 5 valores con push y luego desencola los 5 con shift. ¿Cuántos pasos en total?
- Un búfer circular tiene 8 celdas (de 0 a 7), head = 6 y size = 3. ¿Qué celda usa el siguiente enqueue?
- ¿Cuántos pasos lleva un dequeue en un búfer circular, contenga los valores que contenga?
- Un anillo fijo de 8 celdas contiene 8 valores. ¿Qué pasa al hacer enqueue?
- Sobrescribe el valor del frente
- La cola está llena y el valor se rechaza
- Mueve todos los valores a la izquierda
- Ordena los valores
- ¿Qué búsqueda del curso de algoritmos guarda en una cola las casillas pendientes?
- Búsqueda binaria
- Búsqueda en anchura
- Búsqueda en profundidad
- Búsqueda lineal
- En los términos del 6.006 del MIT, ¿qué dos operaciones de secuencia usa una cola?
- insert last y delete last
- insert last y delete first
- insert first y delete first
- get at y set at
- Una cola es primero en entrar, primero en salir: enqueue al final, dequeue del frente.
- shift mueve todos los valores que quedan, así que desencolar de n valores cuesta n pasos.
- Un índice head o un búfer circular hacen que dequeue sea 1 paso.
- En un anillo de tamaño c, la siguiente celda libre es (head + size) mod c.
Fuentes de este curso (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Fecha de consulta: 2026-10-18