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:

        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:

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

Para o array:

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.

 

[souto]

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.

 

[jorgsh]

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

 

[napalm]

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.

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

 

[[knap]]

Porque não crias um vector de stacks? Em que cada stack representa uma torre, depois é só fazer push(), pop().

 

[jorgsh]

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.

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

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:

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

 

[napalm]

Bem hj até estou simpático

1. O código do IntQueueArray até está porreiro (foste tu que o fizeste?) com uma excepção:

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.

// 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.

 

[jorgsh]

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

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:

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

 

[napalm]

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.

 

[jorgsh]

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

 

[napalm]

Pa o mais dificil já está. Mas já estás a usar debug???

 

[jorgsh]

Não estou a usar debug, convém usar?

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

Obrigado

 

[napalm]

Não estou a usar debug, convém usar?

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

Obrigado

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.

 

[jorgsh]

Ok obrigado