Inserção e remoção em Deques

Aprenda como inserir e remover pela esquerda e pela direita em um deque.

Por | @nmuller99 Programação
Olá caro leitor.

Hoje vou demonstrar como inserir e remover pela esquerda e pela direita em um deque (uma estrutura de dados).

Deque


Um deque (“Double-Ended QUEue”) é uma lista linear onde as operações de inserção e remoção podem ser efetuadas tanto no início quanto no final da lista linear.

Portanto:
- A inserção de um elemento pode torná-lo o primeiro ou o último da lista linear
- O elemento retirado na remoção é o primeiro ou o último elemento da lista


Fiz um programa em C que faz a inserção e remoção em deques, tanto pela entrada (esquerda) quanto pela saída (direita).

Segue o código:
#include
#include

int v[10];
int op, k, i, f, ptr_dir, ptr_esq;
int total = 10;
int valor;


void exibeTecla(void)
{
    k = i;
    while(k <= f)
    {
        printf("
POS[%d] = %d",k,v[k]);
        k++;
    }

    printf("

PRECIONE QUALQUER TECLA PARA CONTINUAR");
    getch();
}


void inserirDequeDireita(void)
{
    if(ptr_dir == f)
    {
        printf("
---OVERFLOW---
");
        exibeTecla();
    }
    else
    {
        printf("
DIGITE O VALOR A SER INSERIDO A DIREITA: ");
        scanf("%d",&valor);
        ptr_dir++;
        //printf("

%d

",valor);
        v[ptr_dir] = valor;
        exibeTecla();
    }
}

void inserirDequeEsquerda(void)
{
    if(ptr_esq == i)
    {
        printf("
---OVERFLOW---
");
        exibeTecla();
    }
    else
    {
        printf("
DIGITE O VALOR A SER INSERIDO A ESQUERDA: ");
        scanf("%d",&valor);
        ptr_esq--;
        v[ptr_esq] = valor;
        exibeTecla();
    }
}

void removerDequeDireita(void)
{
    if(ptr_dir < ptr_esq)
    {
        printf("
---UNDERFLOW---
");
        exibeTecla();
    }
    else
    {
        v[ptr_dir] = 0;
        ptr_dir--;
        exibeTecla();
    }
}

void removerDequeEsquerda(void)
{
    if(ptr_dir < ptr_esq)
    {
        printf("
---UNDERFLOW---
");
        exibeTecla();
    }
    else
    {
        v[ptr_esq] = 0;
        ptr_esq++;
        exibeTecla();
    }
}

//FUNCAO PRINCIPAL
void main(void)
{
    //inicializacao das variaveis
    op = 0;
    f  = total;
    i  = 0;
    //deque
    ptr_esq = (i + f) / 2;
    ptr_dir = ptr_esq - 1;


    while(op != 9)
    {
        clrscr();
        printf("
PRINCIPIO DA FILA SIMPLES
");
        printf("1 - INSERIR LADO DIREITO
");
        printf("2 - INSERIR LADO ESQUERDO
");
        printf("3 - REMOVER LADO DIREITO
");
        printf("4 - REMOVER LADO ESQUERDO
");

        printf("9 - SAIR
");
        printf("OPCAO: ");
        scanf("%d",&op);

        if(op == 1)
            inserirDequeDireita();

        if(op == 2)
            inserirDequeEsquerda();

        if(op == 3)
            removerDequeDireita();

        if(op == 4)
            removerDequeEsquerda();
    }
}


A variável f é o final do deque, a variável i é o início do deque.
Ao iniciar o programa fazemos com que o deque tenha seus ponteiros inicializados na metade do tamanho do deque, ou seja, o PTR_ESQ vai ser a metade do deque, e o PTR_DIR vai ser a metade do deque - 1. Fazemos isto para poder adicionar o primeiro registro sem ocorrer problemas e para que o deque trabalhe de forma correta, sempre que adicionamos ou removemos algum registro estes ponteiros serão movidos (incrementado ou decrementado). Copie o código acima em um script .c salve seu arquivo e compile-o, verás que funciona corretamente.

Mais sobre: c deque estrutura de dados
Share Tweet
Comentários
Carregar comentários
Destaquesver tudo