Interface Queue

[jorgsh]

Olá,

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

Por exemplo se eu tiver as 4 "torres" seguintes:

Código: Seleccionar todos

        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: Seleccionar todos

public interface IntQueue
{
   public void put(int i);
   public int get();
   public boolean isEmpty();
}

Para o array:

Código: Seleccionar todos

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.

[_tribal_]

Essas torres são geradas como? Ou seja, em que te baseias para meteres e formares esses valores? Se postares código, melhor

[jorgsh]

Olá

Utilizo a abstração de dados fila onde os elementos são extraídos na ordem em que foram inseridos e para isso uma possiblidade é utilizar a interface queue que é o que estou a tentar fazer mas até agora nada.

Se me puderem dar uma pista ou um pequeno exemplo que me ajude a chegar a esse resultado, não hesitem. A minima ajuda será certamente bastante util.

Obrigado.

[_tribal_]

Olá

Utilizo a abstração de dados fila onde os elementos são extraídos na ordem em que foram inseridos e para isso uma possiblidade é utilizar a interface queue que é o que estou a tentar fazer mas até agora nada.

Se me puderem dar uma pista ou um pequeno exemplo que me ajude a chegar a esse resultado, não hesitem. A minima ajuda será certamente bastante util.

Obrigado.

Não sou grande programador mas, explica-me então porquê que há 'torres' mais pequenas que outras?

[vamosAeles]

Boas,

cada torre é suposto ser uma IntQueue, ou todas as torres estão na mesma IntQueue?

É que se for a segunda opcão, não estou a ver o conceito de torre implementado na IntQueue.

O put e get é suposto ser um pilha tipo FIFO ?

Partindo do exmplo inicial q deste, é relevante a altura de um número da torre, ie, aquele 7 é um única torre, faz parte da 5 6, e ficou mal identado?

[jorgsh]

Olá,

Obrigado pelas respostas. Aquele 7 assim como o 6 fazem parte da terceira torre, ficou foi mal identado. (1a Torre : 1 2 3, 2a Torre: 4 5, 3a Torre:6 7 8 9, 4aTorre: 10)

Eu quero dar a possibilidade ao utilizador de escolher o número de torres assim como os números que cada uma irá conter. Mas para começar tentei só para as 4 torres conforme o exemplo que vos dei para ver se funciona.

Aqui vai o que consegui até agora:

Código: Seleccionar todos

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;
         
      }   
   
   }
}


Quando compilo dá uma excepçao...ArrayIndexOutOfBoundsException em

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

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

Obrigado.

[_tribal_]

Desconheço as InQueue do java, mas esse erro significa que estás a aceder a uma posição do array que não existe, i.e, tens uma array de 5 posições e estás a aceder a posição 6 (exemplo)

[vamosAeles]

Boas, partindo do código da Intqueu num posto acima o problema está em:

Código: Seleccionar todos

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;
      }
   }


Se repares quando fazes "queue = new int[maxN]", maxN têm o valor 0. Apenas fica com o 3 na última instrução do construtor, e depois quando acedes ao "queue[tail] = i", rebenta pois o array não tenha nenhuma posição.

Substitui "queue = new int[maxN]" por ""queue = new int[capacity]""

Cumps,
[[]]

[jorgsh]

Olá! Já substitui, muito obrigado pela ajuda.

Fiz algumas modificações na minha classe Torres e já funciona correctamento. Obtenho o resultado que esperava, ou seja 1 4 6 10 2 5 7 3 8 9.
Aqui vai o meu código:

Código: Seleccionar todos


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;
           
        }   
   
    }
}
   


Bom, fiz isto já com o numero de torres a 4 e os numeros incluidos no código porque achei mais simples para começar.
Mas o que eu queria mesmo era não ficar limitado a 4 torres e aos mesmos numeros. Ou seja, quero dar a possiblidade ao utilizador de introduzir o numero de torres e depois inserir os numeros em cada torre.
A primeira vista parecia me bastante simples fazer esta modificação, mas a verdade é que não estou a conseguir.

Alguém pode me ajudar?

Obrigado.

[vamosAeles]

Boas,

Uma solução simples passa por 'perguntar' primeiro ao utilizador quantas torres ele quer, e depois os número de cada torre:

Código: Seleccionar todos


import java.io.*;

public class Torres
{
   
    private static IntQueueArray [] leTorres(){
       IntQueueArray [] res;
       int num;
      String numeros;
      System.out.println("Quantas torres?");
       // ... Le do teclado um inteiro para a variavel num
       //...
       res = new  IntQueueArray [num] ;
       for(int i = 0; i<  num;i++){
          System.out.println("Números da torre " + (i + 1) + "(separados por espaço)");
        //... Le do teclado uma linha com os números para a variavel numeros
        //....
        String []ln = numeros.split(" ");
        IntQueueArray q = new IntQueueArray (ln.lenght);
        res[i] = q;
        for(String s : ln){
          q.put(Integer.parseInt(s));
        }

       }
   
     return res;         
   
    }

    public static void main(String[] args)
    {
       
       
        IntQueueArray [] filas = leTorres();
         int torres =  filas.lenght;

        while(true)
        {
            int n = filas.length;           
            boolean encontrou = false;
            for(int i=0; i<filas.length; i++)
            {
                if(!filas[i].isEmpty())
                {
                    System.out.println(fila[i].get());
                   
                    encontrou = true;
                }
            }
            if(!encontrou) break;
           
        }   
   
    }
}


Não está completa (falta ler do teclado), depois completa-a e testa a ver se funca


Cumps,
[[]]

[jorgsh]

Funciona! Muito obrigado!

Aqui vai:

Código: Seleccionar todos

import java.io.*;

public class Torres1
{
   
   public static IntQueueArray [] leTorres() throws IOException
   {
      BufferedReader tecl = new BufferedReader(new InputStreamReader(System.in));
     
   
      IntQueueArray [] res;
      int num;
      String numeros;
      
      System.out.println("Quantas torres?");
      String f = tecl.readLine();
      num = Integer.parseInt(f);
      
      res = new  IntQueueArray [num];
         
      for(int i = 0; i<  num; i++)
      {
         System.out.println("Números da torre " + (i + 1) + " (separados por espaço)");
         numeros = tecl.readLine();
         
         String []ln = numeros.split(" ");
         IntQueueArray q = new IntQueueArray (ln.length);
         res[i] = q;
       
         for(String s : ln)
         {
            q.put(Integer.parseInt(s));
         }   
      }
         return res;
   }
         

   public static void main(String[] args) throws IOException
   {
       
      IntQueueArray [] filas = leTorres();
      int torres =  filas.length;

      System.out.print("Resultat ");
      while(true)
      {
         int n = filas.length;           
         boolean encontrou = false;
           
         for(int i=0; i<filas.length; i++)
         {
            if(!filas[i].isEmpty())
            {
               System.out.print(+filas[i].get()+ " ");
                   
               encontrou = true;
            }
         }
         if(!encontrou) break;
      }   
   }
}

Mais uma vez obrigado!