Queues · Colas
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
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 and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
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?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
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.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
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.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
Ahora tú intentarlo
- Usa una lista como tu cola (
appendpara enqueue,pop(0)para dequeue). - Presiona Check answer para probar tu código.
A queue is FIFO · Una cola es FIFO
A queue adds at the back and removes at the front — first in, first out. · Una cola agrega al final y elimina al principio — primero en entrar, primero en salir.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · 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"].)
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same · mismo order. (result should be [1, 2, 3].) · 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].)
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write serve(queue) that dequeues the front item: remove it from the list and return · retorno it. The caller's list should get shorter. · Escribe serve(queue) que haga dequeue del elemento frontal: elimínalo de la lista y devuélvelo. La lista del llamante debe acortarse.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write front(queue) that returns · retornos the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.