French
DeutschDeque (estruturas de dados) – Wikipédia, a enciclopédia livre
 |
Em ciência da computação, uma fila duplamente terminada (frequentemente abreviada como DEQUE, do inglês Double Ended Queue) é um tipo de dado abstrato que generaliza uma fila, para a qual os elementos podem ser adicionados ou removidos da frente (cabeça) ou de trás (cauda).[1] Também é chamada de lista encadeada cabeça-cauda, apesar de propriamente isto se referir a uma implementação de estrutura de dados específica.
As deques são filas duplamente ligadas, isto é, filas com algum tipo de prioridade. Por exemplo, sistemas distribuídos sempre necessitam que algum tipo de processamento seja mais rápido, por ser mais prioritário naquele momento, deixando outros tipos mais lentos ou em fila de espera, por não requerem tanta pressa. Ele pode ser entendido como uma extensão da estrutura de dados Fila.
A implementação de um deque por alocação estática ou seqüencial é feita por meio de um arranjo de dimensão máxima predefinida e de duas variáveis inteiras que indicam o topo e a base (head e tail, respectivamente). Da mesma forma que ocorre com a fila, o deque deve ser implementado segundo a abordagem circular, que confere eficiência à estrutura ao mesmo tempo em que evita o desperdício de memória.
A declaração em C++ adotada para o deque implementado por arranjo é:
#define MAXDEQUE <tamanho máximo deque> struct deque { tipo itens[MAXDEQUE]; int inicio_esq, inicio_dir; }; pont. esq. pont. dir. | | Overflow [A] [B] [C] [D] [E] [F] overflow 1 2 3 4 5 6 | | | | (ini. esq) (fim. esq) (ini. dir) (fim dir.)
A Deque é dividida pelo total de posições em duas extremidades, onde o total não pode ser extrapolado, senão ocorre o estouro da memória, que já foi programada para uma determinada quantidade, não havendo possibilidade de mudança após já se ter definido o total. Os primeiros que são inseridos são os últimos a serem retirados, e é possível inserir elementos em ambos os lados (tanto no seu início como no seu final) mesmo que desproporcionalmente, desde que não ultrapasse o limite máximo.
Pseudocódigo de exemplo
[editar | editar código-fonte]O algoritmo abaixo implementa genericamente um deque circular estático (de posições, indexadas de 0 até ).
Variáveis
[editar | editar código-fonte]INTEIRO N INTEIRO inicio = -1 INTEIRO fim = -1 TIPO VETOR deque[DE 0 ATÉ N] Verificar se o deque está cheio
[editar | editar código-fonte]FUNÇÃO cheio() RETORNA BOOLEANO SE ((fim + 1) % N = inicio) ENTÃO RETORNA VERDADEIRO SENÃO RETORNA FALSO FIM DO SE FIM DA FUNÇÃO Verificar se o deque está vazio
[editar | editar código-fonte]FUNÇÃO vazio() RETORNA BOOLEANO SE (inicio = -1) ENTÃO RETORNA VERDADEIRO SENÃO RETORNA FALSO FIM DO SE FIM DA FUNÇÃO Inserir no começo
[editar | editar código-fonte]PROCEDIMENTO inserirComeço(TIPO valor) SE cheio() ENTÃO ESCREVA "Deque cheio!" SENÃO SE vazio() ENTÃO inicio = 0 fim = 0 SENÃO SE (inicio = 0) ENTÃO inicio = N - 1 SENÃO inicio = inicio - 1 FIM DO SE FIM DO SE deque[inicio] = valor FIM DO SE FIM DO PROCEDIMENTO Inserir no final
[editar | editar código-fonte]PROCEDIMENTO inserirFinal(TIPO valor) SE cheio() ENTÃO ESCREVA "Deque cheio!" SENÃO SE vazio() ENTÃO inicio = 0 fim = 0 SENÃO SE (fim = N - 1) ENTÃO fim = 0 SENÃO fim = fim + 1 FIM DO SE FIM DO SE deque[fim] = valor FIM DO SE FIM DO PROCEDIMENTO Remover do começo
[editar | editar código-fonte]FUNÇÃO removerComeço() RETORNA TIPO SE vazio() ENTÃO RETORNA (TIPO) NULO SENÃO TIPO valor = deque[inicio] deque[inicio] = (TIPO) NULO SE (inicio = fim) ENTÃO inicio = -1 fim = -1 SENÃO SE (inicio = N - 1) ENTÃO INICIO = 0 SENÃO inicio = inicio + 1 FIM DO SE FIM DO SE RETORNA valor FIM DO SE FIM DA FUNÇÃO Remover do final
[editar | editar código-fonte]FUNÇÃO removerFinal() RETORNA TIPO SE vazio() ENTÃO RETORNA (TIPO) NULO SENÃO TIPO valor = deque[fim] deque[fim] = (TIPO) NULO SE (inicio = fim) ENTÃO inicio = -1 fim = -1 SENÃO SE (fim = 0) ENTÃO fim = N - 1 SENÃO fim = fim - 1 FIM DO SE FIM DO SE RETORNA valor FIM DO SE FIM DA FUNÇÃO Buscar valor no começo
[editar | editar código-fonte]FUNÇÃO buscarComeço() RETORNA TIPO SE vazio() ENTÃO RETORNA (TIPO) NULO SENÃO RETORNA deque[inicio] FIM DO SE FIM DA FUNÇÃO Buscar valor no fim
[editar | editar código-fonte]FUNÇÃO buscarFinal() RETORNA TIPO SE vazio() ENTÃO RETORNA (TIPO) NULO SENÃO RETORNA deque[fim] FIM DO SE FIM DA FUNÇÃO Referências
- ↑ Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
