Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Listas Lineares Deques (Filas de duas Pontas)
Deques são filas que permitem tanto entrada quanto retirada em ambas extremidades. Neste caso não faz mais sentido falar em início e fim de fila, mas simplesmente início1 e início2.
Implementações estáticas e dinâmicas são possíveis, mas a dinâmica é mais comum, tirando proveito do encadeamento duplo para permitir acesso a ambas extremidades em tempo O(1).
typedef struct estrutura
{
TIPOCHAVE chave;
estrutura *prox;
estrutura *ant;
} NO;
typedef struct
{
NO* inicio1;
NO* inicio2;
} DEQUE;
// Inicialização do deque
void inicializarDeque(DEQUE *d)
{
d->inicio1 = NULL;
d->inicio2 = NULL;
}
// Quantos elementos existem
int tamanhoDeque(DEQUE d)
{
NO* p = d.inicio1;
int tam = 0;
while(p)
{
tam++;
p = p->prox;
}
return(tam);
}
// Inserir no inicio1 do deque
void entrarDeque1(TIPOCHAVE ch, DEQUE *d)
{
NO* novo = (NO*) malloc(sizeof(NO));
novo->chave = ch;
novo->ant = NULL;
novo->prox = d->inicio1;
if(d->inicio1) d->inicio1->ant = novo; // já contém dados
else d->inicio2 = novo; // 1a. inserção
d->inicio1 = novo;
}
// Retirar de inicio1 ou retornar -1 se vazio
TIPOCHAVE sairDeque1(DEQUE *d)
{
NO* aux;
if(!d->inicio1) return(-1);
aux = d->inicio1;
int ch = aux->chave;
d->inicio1 = d->inicio1->prox;
free(aux);
if(!d->inicio1) d->inicio2 = NULL;
else d->inicio1->ant = NULL;
return(ch);
}
// destruir deque dinâmico
void DestruirDeque(DEQUE *d)
{
while (d->inicio1) sairDeque1(d);
}
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.