Mostrar código-fonte de Deque (estruturas de dados)

{{mais fontes|data=dezembro de 2020}}
Em [[ciência da computação]], uma '''fila duplamente terminada''' (frequentemente abreviada como '''DEQUE''', do inglês '''D'''ouble '''E'''nded '''Que'''ue) é 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).<ref>[[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&ndash;243.</ref> 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 [[FIFO|filas]] duplamente ligadas, isto é, filas com algum tipo de prioridade. Por exemplo, [[Computação distribuída|sistemas distribuídos]] sempre necessitam que algum tipo de [[processador|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 é:

<syntaxhighlight lang="cpp">
#define MAXDEQUE <tamanho máximo deque>
struct deque {
  tipo itens[MAXDEQUE];
  int inicio_esq, inicio_dir;
};
</syntaxhighlight>

                           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 ==
O algoritmo abaixo implementa genericamente um deque circular estático (de <math>N</math> posições, indexadas de 0 até <math>N - 1</math>).

=== Variáveis ===
<syntaxhighlight lang="text">
INTEIRO N
INTEIRO inicio = -1
INTEIRO fim = -1

TIPO VETOR deque[DE 0 ATÉ N]
</syntaxhighlight>

=== Verificar se o deque está cheio ===
<syntaxhighlight lang="text">
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
</syntaxhighlight>

=== Verificar se o deque está vazio ===
<syntaxhighlight lang="text">
FUNÇÃO vazio() RETORNA BOOLEANO

    SE (inicio = -1) ENTÃO
    
        RETORNA VERDADEIRO
    
    SENÃO
        
        RETORNA FALSO
    
    FIM DO SE

FIM DA FUNÇÃO
</syntaxhighlight>

=== Inserir no começo ===
<syntaxhighlight start="1" lang="text">
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
</syntaxhighlight>

=== Inserir no final ===
<syntaxhighlight lang="text">
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
</syntaxhighlight>

=== Remover do começo ===
<syntaxhighlight lang="text">
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
</syntaxhighlight>

=== Remover do final ===
<syntaxhighlight lang="text">
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
</syntaxhighlight>

=== Buscar valor no começo ===
<syntaxhighlight lang="text">
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
</syntaxhighlight>

=== Buscar valor no fim ===
<syntaxhighlight lang="text">
FUNÇÃO buscarFinal() RETORNA TIPO

    SE vazio() ENTÃO
    
        RETORNA (TIPO) NULO
    
    SENÃO
        
        RETORNA deque[fim]
    
    FIM DO SE

FIM DA FUNÇÃO
</syntaxhighlight>{{Referências}}

{{esboço-programação}}
{{Estrutura de dados}}

[[Categoria:Estruturas de dados]]
[[Categoria:Tipos abstratos de dados]]