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.
- append insere no final.
- 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 std::deque.
Push e pop no front ou no back
Operação
Ordem do front ao back
Deque em C++
A API usa os nomes appendleft, append, popleft e pop. Todas atuam nas extremidades.
C++17std::deque
#include <deque>
std::deque<int> dados{2, 3, 4};
dados.push_front(1); // insere no início
dados.push_back(5); // insere no final
dados.pop_front(); // remove do início
dados.pop_back(); // remove do finalCustos e acesso
| Operação em std::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.
- cppreference — std::deque: API, custos nas pontas e acesso indexado.