Deque (estruturas de dados)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde setembro de 2010).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

Deque em estrutura de dados 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.

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 mesmo que desproporcionalmente, desde que não ultrapasse o limite máximo.


Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.