Queues · Filas
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.
Uma queue é FIFO
- Uma queue é First In, First Out (FIFO).
- O primeiro item que você adiciona é o primeiro a sair.
- Pense em uma fila de pessoas: a pessoa na frente é atendida primeiro.
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 e dequeue com uma lista
- Podemos construir uma queue a partir de uma lista Python.
- enqueue =
queue.append(x)— adicionar à parte traseira. - dequeue =
queue.pop(0)— remover e retornar a frente.
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 e empty
- Olhe para a frente sem removê-la:
queue[0]. - Uma fila está vazia quando
len(queue) == 0. - Verifique se não está vazia antes de fazer 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.
Uma nota sobre velocidade
pop(0)precisa mover todos os outros itens para frente em uma posição.- Para uma queue grande isso é lento, usando mais tempo.
- Sistemas reais usam um buffer circular com ponteiros front e rear em vez disso.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
Em pseudocódigo do Cambridge
- O exame constrói uma queue a partir de um array com um ponteiro
fronte umrear.
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.
Erros comuns
- Uma queue é first-in, first-out: entre pela traseira, saia pela frente.
- Verifique se não está vazia antes de fazer dequeue.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
Agora você tenta
- Use uma lista como sua queue (
appendpara enqueue,pop(0)para dequeue). - Clique em Check answer para testar seu código.
A queue is FIFO · Uma fila é FIFO
A queue adds at the back and removes at the front — first in, first out. · Uma fila adiciona no final e remove na frente — primeiro a entrar, primeiro a sair.
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"].) · Comece com uma fila vazia. Enfileire "a", depois "b", depois "c". Depois desenfileire uma vez, armazenando o valor removido em first. (first deve ser "a" e a fila deve ser ["b", "c"].)
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same · mesmo order. (result should be [1, 2, 3].) · Enfileire 1, 2, 3 em uma fila, depois desenfileire todos em result. Diferente de uma pilha, uma fila mantém a mesma ordem. (result deve ser [1, 2, 3].)
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write serve(queue) that dequeues the front item: remove it from the list and return · retorno it. The caller's list should get shorter. · Escreva serve(queue) que desenfileira o item frontal: remova-o da lista e retorne-o. A lista do chamador deve ficar menor.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write front(queue) that returns · decrescentes the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · Escreva front(queue) que retorna o item frontal sem removê-lo, para que a fila permaneça inalterada. Se a fila estiver vazia, retorne None.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.