Double-ended queue
Deque: operações nas duas extremidades
Um deque permite inserir e remover tanto no front quanto no back. O nome vem de double-ended queue e costuma ser pronunciado “deck”.
Contrato do deque
- push_front insere no front.
- push_back insere no back.
- pop_front remove do front.
- pop_back remove do back.
Relação com pilha e fila
Se inserirmos e removermos pela mesma ponta, usamos o deque como pilha. Se inserirmos no back e removermos no front, usamos o deque como fila.
Importante: deque define operações, não exige que a implementação seja uma lista duplamente encadeada.
Laboratório: uma implementação duplamente encadeada
Para tornar as duas direções visíveis, este laboratório escolhe nós com prev e next. Essa é uma implementação possível, não uma descrição do interior de collections.deque.
Push e pop no front ou no back
Operação
Ordem do front ao back
Deque em Python
A API usa os nomes appendleft, append, popleft e pop. Todas atuam nas extremidades.
Pythoncollections.deque
from collections import deque
d = deque([2, 3, 4]) # front = 2 e back = 4
d.appendleft(1) # push_front: insere antes do front
d.append(5) # push_back: insere depois do back
esquerda = d.popleft() # pop_front: remove 1
direita = d.pop() # pop_back: remove 5
print(esquerda, direita) # 1 5
print(list(d)) # [2, 3, 4]Custos e acesso
| Operação em collections.deque | Custo esperado | Observação |
|---|---|---|
| append / appendleft | aproximadamente O(1) | Inserção nas extremidades. |
| pop / popleft | aproximadamente O(1) | Remoção nas extremidades. |
| Acesso nas extremidades | O(1) | d[0] e d[-1]. |
| Acesso no meio | O(n) | Para acesso aleatório frequente, prefira list. |
Referências usadas
- NIST — deque: inserção e remoção no head ou tail.
- Python — collections.deque: API, custos nas pontas e acesso indexado.