Implementação de deque em c [RESOLVIDO]

marcos@marcos
(usa Ubuntu)

Enviado em 14/10/2012 - 16:45h

Caros colegas, estou meio perdido...
Preciso fazer um trabalho pra faculdade onde devo implementar uma fila dinamica na "mão", onde por meio de um menu o usuário possa selecionar:

1- inserção normal de elementos

2- após o primeiro elemento ser inserido normalmente, pode escolher por inserir no inicio da fila e o algoritmo reorganizará a fila

3- inserir diretamente no final da fila

4- desenfileirar os elementos na ordem em que forma enfileirados

5- desenfileirar de trás pra frente os elementos


Meu algoritmo já atende os passos de 1 a 4, mas o passo 5 é onde solicito algumas sugestões de vocês, pois não estou conseguindo implementar esta parte.

Provavelmente alguém vai me perguntar o porque de implementar na "mão" essa fila se já existe isso pronto... e já adianto que concordo plenamente que é como "reinventar a roda" mas o professor insiste que isso será importante pra nossa formação. Portanto, esse é o motivo.

julianjedi
(usa Arch Linux)

Enviado em 14/10/2012 - 22:27h

Amigo isto esta mais com cara de um deque... pois uma fila padrao seria fifo ... first in first out, porem se vc esta organizando os elementos podendo inserir e retirar tanto do começo quanto do fim da fila isso se torna um deque .. posta seu código ai pra galera te ajudar. sem uma base fica dificil .. pois tem que ver como vc definiu a TAD para poder trabalhar na implementação.

paulo1205
(usa Ubuntu)

Enviado em 16/10/2012 - 04:55h

Não seria a implementação mais eficiente do mundo, mas, para não perder tempo, eu faria uma lista duplamente encadeada (i.e. cada nó tem ponteiros para o nó anterior e para o próximo nó) e guardaria um ponteiro para o primeiro e outro para o último elemento. Com isso, fica fácil inserir ou remover elementos em qualquer das pontas da fila, que parece ser o que você quer.

marcos@marcos
(usa Ubuntu)

Enviado em 18/10/2012 - 23:59h

Pessoal vou postar as partes do código que fiz...

1- definição da estrutura:

struct tipocelula{

        int item;

	tipocelula *prox;

};

 

2- variáveis globais:

tipocelula *frente,*tras;

int contador;//indica qtde elementos

 

3- talvez nem seja muito utilizado, mas criei um método construtor:

void dequeConstrutor(){

	frente=tras=null;

	contador=0;

}

 

4- criei uma funçao para verificar se o deque está vazio

bool dequeVazio(){

	return frente==null;

}

 

5- agora criei a função que "deveria" remover de trás pra frente:

bool removeUltimo(int &elemento){

	tipocelula *aux;

	/*se o deque nao estiver vazio)*/

	if(!dequeVazio()){

		aux=frente;//aponta para o mesmo lugar que a primeira célula da fila

		elemento=tras->item;/*passar por referencia o valor que está armazenado no membro item  */

		if(frente==tras){

			frente=tras=null;//faz com que frente e tras apontem para nulo

			contador--;

			free(aux);//libera memória

			return true;

		}

		else{

			while(aux->prox!=tras){//dessa forma faço com a fila seja percorrida até o penúltimo elemento

				aux=aux->prox;//faço com que aux vá percorrendo a fila

			}

			tras=aux;//volto o ponteiro para a ultima posiçao válida da fila que é o endereço do ponteiro aux nesse momento

			aux=aux->prox;//movo o ponteiro aux para a ultima posição que então será excluída

			tras->prox=null;//tras-prox deve apontar pra nullo

			contador--;

			free(aux);//libera memória		

			return true;

		}

	}

	else

		return false;	

}

 

Aí o que vem acontecendo agora é consigo remover apenas um elemento do final, depóis é como se em algum momento o deque perdesse toda a referência, não consigo mais consultar qual é último nem o primeiro...

luisrcs
(usa Linux Mint)

Enviado em 19/10/2012 - 07:14h

Fazer uma fila extra e copiar os dados nos lugares certos, depois apagar a primeira.

marcos@marcos
(usa Ubuntu)

Enviado em 19/10/2012 - 11:31h

Caro colega, sem dúvida é uma opção também, mas está sendo solicitado que seja implementado na forma de "deque" e implementar conforme sugeriu eu não estaria atendendo a este requisito.

paulo1205
(usa Ubuntu)

Enviado em 19/10/2012 - 15:36h

Volto a sugerir tornar a lista duplamente encadeada, podendo ser percorrida nos dois sentido (i.e. cada nó tem ponteiro para o próximo e para o anterior). Com certeza é muito mais eficiente (O(n), tipicamente, para operações de inserção e remoção) do que o código postado aqui e a sugestão de criar outra lista a cada nó removido (ambas são O(n²)).

marcos@marcos
(usa Ubuntu)

Enviado em 21/10/2012 - 02:12h

Pessoal desde já obrigado pela força. Segui a sugestão do Paulo e implementei uma fila duplamente encadeada mesmo, está tudo funcionando perfeitamente agora.

Obrigado.