• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

brunomoniz

[Resolvido] Priority Queue

6 mensagens neste tópico

Boas.. eu tenho que fazer uma classe Priority Queue derivada de uma classe Queue onde já tenho todos os métodos necessários para uma Queue funcionar.

Eu sei que já existe funções no C++ para implementar isto mas não as posso usar.

O que me está neste momento a "moer" o juizo é como vou ordenar as prioridades na queue... alguém tem algum algoritmo para isto? Ou alguma ideia? Basicamente é fazer um método "ordenar" para ordenar a queue... e é este método que me falta fazer...

Ideias?  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas, uma priority QUEUE nao e mt diferente duma QUEUE normal, numa QUEUE normal o que acontece é k todos os elementos tem igual prioridade, logo ao inserires um elemento inseres no fim.Numa P QUEUE diferentes elementos vao ter diferentes prioridades, logo precisas de uma funcao que dado um objecto da queue te diga a prioridade dele (de preferencia a prioridade será um numero). Desta forma o algoritmo para inserir numa PQUEUE é meter o objecto no fim e depois ir puxando o gajo (em direccao ao principio) até encontrares um elemento que tenha uma prioridade maior ou igual que ele, e nesse caso pára.

Imagina que tens uma fila de supermercado e que tens 2 tipos de pessoas , "normais" e grávidas. Imagina ainda que neste supermercado tá la a dizer que as gravidas podem passar a frente das pessoas "normais", pronto, o que se tá a passar é que a funcao que devolve a prioridade consoante a pessoa atribui uma prioridade maior  a uma gravida do que a uma pessoa nao gravida, logo, se tiveres uma fila com pessoas e xegar uma gravida no fim, ela vai passando a frente das pessoas uma a uma e só para quando atingir o principio da fila ou quando à frente dela estiver outra grávida.

É exactamente o mesmo algoritmo que tens de fazer.

Outra questao que nao posso deixar de salientar é que nao concordo do ponto de vista teorico(ie, boa programacao) que uma PQ derive de uma QUEUE, devia ser o contrário porque uma QUEUE normal é um caso particular de uma PQ onde a funcao de prioridade devolve sempre o mesmo valor independentemente do objecto.

Abraco []

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu já tenho o algoritmo  para ordenar a Queue, tornando-a numa PriorityQueue mas agora estou com um problema... o campo prioridade.

Não estou a ver bem onde vou definir o campo...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nao estou a ver para que precisas de ordenar a queue... a unica diferenca entre a Q e a PQ é na funcao insere, pois o insere da PQ deve ter um ciclo ( ou mecanismo semelhante ) a puxar o elemento para a sua posicao correcta.

A funcao que retorna a prioridade é o cliente da PQ que define pois ele é que sabe que objectos vai meter na tua QUEUE e como calcular a sua prioridade.. tas a ver?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

percebi o que queres dizer mas não estou a ver como o implementar...

eu sei que a diferença está na função insere, ou seja, a função insere da PQ leva mais um parametro para indicar a prioridade do objecto. O meu problema está em definir essa prioridade dentro das classes e como definir uma prioridade para cada objecto da queue...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, já resolvi o problema. Às vezes a !"#$%&/ dos enunciados não explicam bem o que pretendem...

a prioridade é definida no elemento T que vai estar na fila...

Obrigado na mesma pela ajuda e atenção  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora