[JAVA] Implementare una FIFO circolare

[Lasentinella]

Devo realizzare entro Martedì una FIFO che trovo particolarmente incasinata con un array..
per chi non sapesse come funziona, faccio un breve esempio (FIFO -> First In First Out, il primo che viene inserito è il primo ad essere estratto, come nella coda del supermercato)
Front e Back tengono traccia del punto di inizio e del punto finale della coda.

Inserisco il primo elemento (gli elementi vuoti sono null):

front=0 back=0
--------------------
| a | null | null |
--------------------

Ne inserisco un altro:

front=0 back=1
------------
| a | b | |
------------

tolgo il primo:

front=1 back=1
------------
| | b | |
------------

Ne metto due, siccome è una FIFO circolare il primo dei due elementi immessi verrà messo all'inizio e il secondo nel primo posto vuoto.

front=1 (punta a b) back=2 (punta a d)
------------
| c | b | d |
------------

Trovo la cosa molto complicata da gestire, ho provato a realizzare il programma ma ho parecchi problemi nell'estrazione di un elemento...
so che è un programma impegnativo, ma qualcuno avrebbe voglia di darci un'occhiata?

public class FIFO
{
	private String array[];
	private int front, back, num; //num tiene conto del numero di elementi presenti nella cosa
	public int max;    //lunghezza massima dell'array

	public FIFO(){
		max=0;
		front=0;
		back=0;
		num=0;
	}

	public FIFO(int maxElementi){
		array=new String[maxElementi];  //creo un array con grandezza data in input
		max=maxElementi;
	}

	public boolean insert(String s)
	{
		if((front==0)&&(back==0)&&(num!=0)) //se la coda è piena
			return false;

		if (back==max-1){ //se back è alla fine della coda
			array[back]=s;
			back=0;
		}

		if((array[back]==null)||(array[back]=="")){  //se si è su una cella vuota
                                                                //si può scrivere 
			array[back]=s;
			back++;
			num++;
		}

			num++;
			return true;
	}

	public String toString(){      //stampa la successione di elementi
	        String stringa="";

		if(num==0)
			System.out.println("La CODA e' vuota!");
		else
			if(front<back)
				for(int i=front;i<=back;i++)  
					stringa=stringa+array[i];
			else
			{

				for(int i=front;i<max;i++)
					stringa=stringa+array[i];
				for(int i=0;i<back;i++)
					stringa=stringa+array[i];
			}

         	return stringa;
	}


	public String extract()  //restituisce un elemento, cancellandolo dalla coda
	{
	
	if(num!=0){         //se ci sono elementi nella coda

		String estr= array[front];     
		if (front == max-1)   //se front è alla fine
		{
			array[front]="";        
			front=0;
		}
		else
			front++;
		num--;

			return estr;
         }
		return null;
	}

}

Chiunque avesse altri dubbi (e immagino ne avrà :P) chieda pure! Pubblicherò la classe che usa questa, la sto rifacendo perché avevo fatto qualche pasticcio
Grazie

[LeleFT]

Il confronto con oggetti non si fa con l'operatore = =, ma utilizzando il metodo equals().

Questo è un suggerimento che ti do dopo aver dato un'occhiata frettolosa al codice.

if((array[back]==null)||( array[back].equals("") ) ){  //se si è su una cella vuota

Ciao.

[aleliguori]

Dovrebbe essere semplice da capire... se ci sono dubbi fammi sapere!

public class FIFO
{
private String array[];
private int in; //prossima posizione in ingresso
private int out; //prossima posizione in uscita
private int count; //contatore posizioni piene
private final int DIM; //dimensione array

public FIFO(int dimensione)
{
DIM = dimensione;
in=0;
out=0;
count=0;
array = new String[DIM]; //crea l'array
}


public boolean insert(String s)
{
if(count==DIM) //se la coda è piena
return false;

array[in] = new String(s); //inserisce la stringa in posizione in

count++; //incrementa il contatore di elementi
in = (in+1)%DIM; //incrementa la posizione di ingresso in modo circolare

return true;
}

public String extract() //restituisce un elemento, cancellandolo dalla coda
{

if(count==0) //se la coda è vuota
return null;

String risp = new String(array[out]);

count--;
out = (out+1)%DIM;

return risp;
}

public String toString() //restituisce la successione di elementi senza estrarli dall'array
{
if(count==0)
{
System.out.println("La CODA e' vuota!");
return null;
}

String risp = "";
int pos;

for(int i=0; i<count; i++)
{
pos = (out+i)%DIM;
risp = new String(risp+array[pos]);
}

//se è necessario svuotare l'array basta togliere il commento dal codice
/*
in=0;
out=0;
count=0;
*/

return risp;
}
}

[Lasentinella]

Originariamente inviato da aleliguori
in = (in+1)%DIM; //incrementa la posizione di ingresso in modo circolare

Originariamente inviato da aleliguori
pos = (out+i)%DIM;

Non mi è chiaro il modo in cui usi la funzione %...scusa ma sono alle prime armi e ho visto % solo per il calcolo del resto!!!!
Grazie ancora, funziona perfettamente!!!!!

[aleliguori]

% è l'operatore resto esattamente per come dici tu...
E' comodo da usare in qesto contesto perchè permette di implementare la posizione 'circolare' nell'array senza fare controlli 'strani'...

Immagina un array di 3 posizioni 0 1 e 2. Inizialmente IN=0.

Effettuando sempre IN++ arrivi ad un certo punto che IN avrà un valore al di fuori dell'array (3) e qundi devi fare un controllo eslpicito per riportare IN a 0 del tipo if(IN==3) {IN=0;}

Utilizzando il resto ottieni direttamente il risultato voluto, infatti:
0%3=0 --> IN = 0
1%3=1 --> IN = 1
2%3=2 --> IN = 2
3%3=0 --> IN = 0

Spero di averti fatto capire!!

Ciao

[Lasentinella]

Originariamente inviato da aleliguori
% è l'operatore resto esattamente per come dici tu...
E' comodo da usare in qesto contesto perchè permette di implementare la posizione 'circolare' nell'array senza fare controlli 'strani'...

Immagina un array di 3 posizioni 0 1 e 2. Inizialmente IN=0.

Effettuando sempre IN++ arrivi ad un certo punto che IN avrà un valore al di fuori dell'array (3) e qundi devi fare un controllo eslpicito per riportare IN a 0 del tipo if(IN==3) {IN=0;}

Utilizzando il resto ottieni direttamente il risultato voluto, infatti:
0%3=0 --> IN = 0
1%3=1 --> IN = 1
2%3=2 --> IN = 2
3%3=0 --> IN = 0

Spero di averti fatto capire!!

Ciao

Ahhhhh !! Geniale! Complimenti per l'idea, non ci avrei mai pensato!
Grazie ancora per la disponibilità

[aleliguori]

Di nulla!