Colas
Una cola es FIFO
- Una cola es Primero en Entrar, Primero en Salir (FIFO).
- El primer elemento que agregas es el primero en salir.
- Piensa en una fila de personas: la persona al frente es atendida primero.
enqueue y dequeue con una lista
- Podemos construir una cola a partir de una lista de Python.
- enqueue =
queue.append(x)— agregar al final. - dequeue =
queue.pop(0)— eliminar y devolver el inicio.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front y empty
- Mirar el inicio sin eliminarlo:
queue[0]. - Una cola está vacía cuando
len(queue) == 0. - Verifica que no esté vacía antes de hacer un dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
Una nota sobre la velocidad
pop(0)tiene que desplazar cada otro elemento hacia adelante un lugar.- Para una cola grande esto es lento, por lo que consume más tiempo.
- Los sistemas reales utilizan un buffer circular con punteros de inicio y final en su lugar.
En pseudocódigo de Cambridge
- El examen construye una cola a partir de un array con un puntero
fronty un punterorear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Errores comunes
- Una cola es primero en entrar, primero en salir: únete al final, sal del principio.
- Verifica que no esté vacía antes de hacer un dequeue.
Ahora tú prueban
- Usa una lista como tu cola (
appendpara enqueue,pop(0)para dequeue). - Pulsa Check answer para probar tu código.
Una cola es FIFO
Una cola agrega al final y elimina al principio — primero en entrar, primero en salir.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Comienza con una cola vacía. Enqueue "a", luego "b", luego "c". Luego dequeue una vez, almacenando el valor eliminado en first. (first debe ser "a" y la cola debe ser ["b", "c"].)
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Hace enqueue de 1, 2, 3 a una cola, luego haz dequeue de todos ellos hacia result. A diferencia de una pila, una cola mantiene el mismo orden. (result debe ser [1, 2, 3].)
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe serve(queue) que haga dequeue del elemento frontal: elimínalo de la lista y devuélvelo. La lista del llamante debe acortarse.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe front(queue) que devuelva el elemento frontal sin eliminarlo, para que la cola permanezca sin cambios. Si la cola está vacía, devuelve None.
Haz clic en Ejecutar para ver la salida aquí.