1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Interface Queue

Discussão em 'Programação' iniciada por jorgsh, 10 de Maio de 2009. (Respostas: 13; Visualizações: 1449)

  1. Olá,

    Gostaria que me ajudassem na implementação de um programa, que tem sido sinónimo de dores de cabeça:005:

    Por exemplo se eu tiver as 4 "torres" seguintes:
    Código:
            6
    1      7  
    2  4  8  
    3  5  9  10
    
    Eu quero fazer com que o programa retire um bloco do topo de cada torre e que ele repita a operação para as que ficam. Primeiro seriam retirados os blocos 1, 4, 6, 10, depois 2, 5, 7, depois o 3, 8 e finalmente o 9.
    O resultado no ecran seria então 1 4 6 10 2 5 7 3 8 9.

    Já tentei tanta coisa mas nada funciona correctamente:(

    Para a interface Queue, eu tenho:

    Código:
    public interface IntQueue 
    {
       public void put(int i);
       public int get();
       public boolean isEmpty();
    }
    Para o array:
    Código:
    public class IntQueueArray implements IntQueue 
    {
       private int[] queue;
       private int head, tail, size, maxN;
       
       public IntQueueArray(int capacity)
       {
          queue = new int[maxN];
          head = 0; 
          tail = 0;
          maxN = capacity;
       }
       public void put(int i){
          if (size < maxN) {
             queue[tail] = i; 
             tail = (tail+1) % maxN;
             ++size;
          }
       }
       
       public int get(){
          int i = queue[head];
          head = (head+1) % maxN;
          --size; 
          return i;
       }
       public boolean isEmpty() {
          return size == 0;
       }
    }
    Obrigado.
     
  2. souto

    souto To fold or to FOLD?

    Isso parece-me ser uma fila circular. Então para quê a verificação de tamanho em put() ?
    Aliás, essa variável size, é capaz de te dar mais problemas do que propriamente ajudar-te.
    Repensa bem se é uma fila circular que queres, pois isso complica-te as coisas.



    Pelo que entendi, tens uma fila por cada torre, é isso?

    Então, o algoritmo é percorrer todas as filas até estarem todas vazias, e para as que não estão vazias, obter o elemento à cabeça.
     
  3. Nesse exemplo tenho 4 torres, e penso que será preciso criar 4 filas e depois ir tirando o elemento do topo de cada uma para obter o resultado que indiquei no exemplo do meu primeiro post? Não sei como fazer. é complicado? Também queria que o numero de torres e o seu conteudo fosse escolhido pelo utilizador.

    Obrigado
     
  4. napalm

    napalm Power Member

    Tens de usar essa interface? Podes usar a interface Stack da API java que já vem feita.
    Vou dar uma achega sem testar, mas msm que não possas usar a Stack deve ser trivial adaptares este código para usar a tua IntQueue.
    Código:
    
    int colunas = 4;
    Stack[] pilhas = new Stack[colunas];
    
    // 1ª pilha
    Stack pilha = new Stack<Integer>();
    pilha.push(3);pilha.push(2);pilha.push(1);
    pilhas[0] = pilha;
    
    // 2ª pilha
    pilha = new Stack<Integer>();
    pilha.push(5);pilha.push(4);
    pilhas[1] = pilha;
    
    // 3ª pilha
    Stack pilha = new Stack<Integer>();
    pilha.push(9);pilha.push(8);pilha.push(7);pilha.push(6);
    pilhas[2] = pilha;
    
    // 4ª pilha
    pilha = new Stack<Integer>();
    pilha.push(10);
    pilhas[3] = pilha;
    
    // precisamos agora de percorrer até ao fim todas as pilhas
    
    while(true) { // termina-se o ciclo quando nenhuma das pilhas tiver elementos
      boolean encontrou = false;
      for(Stack pilha : pilhas) {
        if(!pilha.isEmpty()) {
          System.out.println(pilha.pop());
          encontrou = true;
        }
      }
      if(!encontrou) break;
    }
    
    
     
    Última edição: 11 de Maio de 2009
  5. [knap]

    [knap] Power Member

    Porque não crias um vector de stacks? Em que cada stack representa uma torre, depois é só fazer push(), pop().
     
  6. Olá a todos.
    Obrigado pelas respostas.

    napalm, tentei adaptar o teu código mas até agora sem sucesso, obtenho uma excepção...ArrayIndexOutOfBoundsException

    IntQueueArray.put (IntQueueArray.java)
    Torres.main (PercTorres.java)

    Aqui vai o código:

    Código:
    import java.io.*;
    
    public class PercTorres
    {
            public static void main(String[] args)
        {
            
            int torres = 4;
            IntQueueArray [] filas = new IntQueueArray[torres];
    
            // 1ª torre
            IntQueueArray fila = new IntQueueArray(3);
            fila.put(3); fila.put(2); fila.put(1);
            filas[0] = fila;
    
            // 2ª torre
            fila = new IntQueueArray(2);
            fila.put(5); fila.put(4);
            filas[1] = fila;
    
            // 3ª torre
            fila = new IntQueueArray(4);
            fila.put(9); fila.put(8); fila.put(7); fila.put(6);    
            filas[2] = fila;
    
            // 4ª torre
            fila = new IntQueueArray(1);
            fila.put(10);
            filas[3] = fila;
    
            
    
            while(true) 
            {     
                boolean encontrou = false;
                for(int i=0; i<filas.length; i++)
                {
                    if(!filas[i].isEmpty()) 
                    {
                        System.out.println(fila.get(i));
                        encontrou = true;
                    }
                }
                if(!encontrou) break;
                
            }    
        
        }
    }
    


    Não sei se estou a tentar mostrar o resultado no ecran de maneira errada....

    Podem me ajudar?

    Mais uma vez obrigado


     
  7. napalm

    napalm Power Member

    Bem hj até estou simpático :)

    1. O código do IntQueueArray até está porreiro (foste tu que o fizeste?) com uma excepção:
    Código:
    public IntQueueArray(int capacity) {
            queue = new int[maxN];
            head = 0;
            tail = 0;
            maxN = capacity;
    }
    
    Desta forma, o queue não terá o tamanho que estás à espera.

    2. Percebe a fila que fizeste, agora percebe que não estás a introduzir os elementos na ordem correcta. (deixa esta para último)

    3. Espero que o erro esteja claro neste código.
    Código:
    // 4ª torre
    fila = new IntQueueArray(1);
    fila.put(10);
    filas[3] = fila;
    .....
    System.out.println(fila.get(i));
    
    Tenho a solução aqui, se tiveres dúvidas apita.
     
  8. Olá!

    Em relação à interface, eu já tinha o algoritmo, foi meio caminho andado...
    Obrigado pelas pistas! Na interface pus capacity em vez de Nmax. Era isso que estava mal não era? Pus assim
    Código:
    queue = new int[capacity];
    Eu estava a utilisar sempre a mesma fila para todas as torres, logos os elementos estavam sempre a ser substituidos pelos da torre seguinte....agora cada torre tem a sua fila. Está certo, não está?
    O código não está muito bonito...pq só com 4 ifs é que consegui la chegar. Imagina se tivesse 40 torres..... É isso que me chateia. Como optimizá-lo?

    Aqui vão as minhas alterações:
    Código:
    
    import java.io.*;
    
    public class Torres
    {
        public static void main(String[] args)
        {
            
            int torres = 4;
            IntQueueArray [] filas = new IntQueueArray[torres];
    
            // 1ª torre
            IntQueueArray fila1 = new IntQueueArray(3);
            fila1.put(1); fila1.put(2); fila1.put(3);
            filas[0] = fila1;
    
            // 2ª torre
            IntQueueArray fila2 = new IntQueueArray(2);
            fila2.put(4); fila2.put(5);
            filas[1] = fila2;
    
            // 3ª torre
            IntQueueArray fila3 = new IntQueueArray(4);
            fila3.put(6); fila3.put(7); fila3.put(8); fila3.put(9);    
            filas[2] = fila3;
    
            // 4ª torre
            IntQueueArray fila4 = new IntQueueArray(1);
            fila4.put(10);
            filas[3] = fila4;
    
            
    
            while(true) 
            { 
                int n = filas.length;            
                boolean encontrou = false;
                for(int i=0; i<filas.length; i++)
                {
                    if(!filas[i].isEmpty()) 
                    {
                        if (i==0)
                        {
                            System.out.println(fila1.get());
                        }
                        if (i==1)
                        {
                            System.out.println(fila2.get());
                        }
                        if (i==2)
                        {
                            System.out.println(fila3.get());
                        }
                        if (i==3)
                        {
                            System.out.println(fila4.get());
                        }
                        encontrou = true;
                    }
                }
                if(!encontrou) break;
                
            }    
        
        }
    }
        
    Mais uma vez obrigado
     
    Última edição: 11 de Maio de 2009
  9. napalm

    napalm Power Member

    Mas já bule?
    Sobre a optimização não sei bem o que pretendes fazer de melhor. Esse código com 40000 com 40000 números cada um, resolve isso provavelmente em menos de 1s.
    Se é elegante isso já é outra questão.
     
  10. Olá eu queria dizer mais elegante, é a palavra certa.
    Estava agora aqui a tentar modificar o código para dar a possiblidade ao utilizador de introduzir o numero de torres e depois inserir os numeros em cada torre. Mas deixa de funcionar...:005:
     
  11. napalm

    napalm Power Member

    Pa o mais dificil já está. Mas já estás a usar debug???
     
  12. Não estou a usar debug, convém usar? :confused:

    O mais difcil já está feito é verdade :p Mas quero modificar para nao ficar limtado a 4 torres e aos mesmos numeros. Vamos ver se consigo modificar isto :D

    Obrigado
     
  13. napalm

    napalm Power Member

    Claro! Debug é fundamental se estás a programar. Não admira que andes a bater com a cabeça na parede :)
    Investe ai um tempito a trabalhar com o Eclipse ou Netbeans. A tua produtividade vai aumentar substancialmente.

    Bom trab.
     

Partilhar esta Página