Oficina da Net

Assine nosso RSS - Assine o RSS e receba as novidades do site em seu leitor.

Oficina da Net » Programação » C / C++

Inserção e remoção em Deques

Publicado em: 06/04/2008 | C / C++ | Visualizações: 861 | 1 Comentário(s)

Versão para

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<stdio.h>

#include<conio.h>



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("nPOS[%d] = %d",k,v[k]);

        k++;

    }



    printf("nnPRECIONE QUALQUER TECLA PARA CONTINUAR");

    getch();

}





void inserirDequeDireita(void)

{

    if(ptr_dir == f)

    {

        printf("n---OVERFLOW---n");

        exibeTecla();

    }

    else

    {

        printf("nDIGITE O VALOR A SER INSERIDO A DIREITA: ");

        scanf("%d",&valor);

        ptr_dir++;

        //printf("nn%dnn",valor);

        v[ptr_dir] = valor;

        exibeTecla();

    }

}



void inserirDequeEsquerda(void)

{

    if(ptr_esq == i)

    {

        printf("n---OVERFLOW---n");

        exibeTecla();

    }

    else

    {

        printf("nDIGITE 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("n---UNDERFLOW---n");

        exibeTecla();

    }

    else

    {

        v[ptr_dir] = 0;

        ptr_dir--;

        exibeTecla();

    }

}



void removerDequeEsquerda(void)

{

    if(ptr_dir < ptr_esq)

    {

        printf("n---UNDERFLOW---n");

        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("nPRINCIPIO DA FILA SIMPLESn");

        printf("1 - INSERIR LADO DIREITOn");

        printf("2 - INSERIR LADO ESQUERDOn");

        printf("3 - REMOVER LADO DIREITOn");

        printf("4 - REMOVER LADO ESQUERDOn");



        printf("9 - SAIRn");

        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.

compartilhe

Dica: Confira todo nosso conteúdo de C / C++ no site.

Links patrocinados

Últimos artigos do editor

13º EWD: Um evento para n.
No dia 11 de outubro de 2008.

A falta de estrutura dos .
Por que sites e sistemas são.

Tudo sobre o iPhone 3G no.
iPhone é um smartphone desen.

Como assinar um RSS
RSS é um formato de distribu.

Quando reciclagem digital.
Vejam o que vocês podem faze.

Energia elétrica via Wire.
Recentemente a Intel introdu.

> clique aqui para comentar

Opinião do leitor:

1 Comentário(s)

Joe comentou:

Olá meu amigo, teu site está bombando, d+; em matéria de informática e conteúdo. Porém, como utiliza o nosso bom e velho PTBR para se comunicar, seria interessante, talvez, passar um dicionário pelo texto antes de efetivar a publicação. Assim detectarias detalhes minimalistas, como a grafia da palavra "PRECIONE". Ela deveria ter sido grafada com dois ésses (SS): "PRESSIONE". Nós, que não temos nenhum presidente de STF para nos proteger, que temos noção de que se roubarmos poderemos ser algemados - pois não somos nenhuma celebridade monetária, política ou eclesiástica (lembrando que ser escoltado algemado gera uma má impressão, calúnia, é feio, etc. e roubar, estorquir, desviar, ..., ah isso não!), devemos dar o exemplo em TUDO, incluindo na simples grafia de palavras do nosso bom e velho PTBR. Estamos beirando ao absurdo. Em breve veremos os postes mijando nos cachorros, cavalos montando os peões, mouses mordiscando as mãos dos operadores. PARABÉNS pelo teu trabalho. Saúde e paz, Abraço, JOE

Publicado em: 19/08/2008 - 19:01

Acesso restrito

Destaques

Peixe Grande 2008
O Oficina da Net está este ano participando do Projeto Peixe Grande 2008 na categoria de Blog. Ajude-nos vote!

13º Encontro de Webdesgin
Cobertura do evento - 13º Encontro de Webdesgin na cidade de Porto Alegre

Galaxy 7 - O Smartphone da Asus
Imagens e especulações sobre o Smartphone da empresa foram publicadas na internet

Links patrocinados

Autor

Nícolas Müller

Site do colunista