Nije ovo ništa teško kao što ti misliš. Ovi algoritmi koje si nabrojao se koriste u operacijskom sustavu prilikom straničenja (paging-a) i svaki od njih ima svoju karakterističnu brzinu izvođenja. Mogu se na netu naći barem u pseudo kodu pa ti zato neću sve pisati.
Ono što ću ti objasniti jest FIFO metoda. Može se realizirati poljem, listom ili u datoteci. Mislim da će ti biti puno korisnija ova metoda sa listom pošto vjerujem da je riječ o paging-u... a za ostalo se sam malo potrudi :-)
Kada se red (FIFO struktura) realizira listom nije potrebno paziti na cirkularnost jer ne može doći do preljeva i nedostatka mjesta u redu. Jedina greška koja može nastati jest da nema dosta memorije za kreiranje novog elementa. Npr. da imaš strukturu...
Code:
struct zapis {
int element;
struct zapis *sljed;
};
typedef struct zapis lista;
Dodavanje elementa se vrši na ulazu u red.
Code:
int dodaj(lista **ulaz, lista **izlaz, int element) {
lista *ubaci;
if((ubaci = (lista*)malloc(sizeof(lista)))!=NULL) {
ubaci->element = element;
ubaci->sljed = NULL;
if(*izlaz == NULL) *izlaz = ubaci;
else (*ulaz)->sljed = ubaci;
*ulaz = ubaci;
return 1;
}
return 0;
}
Pokazivač ulaz sada pokazuje na zadnji element u listi, koji je prethodno pokazivačima spojen sa ostalim elementima u redu. Zadnji element u redu ima također svoj pokazivač na novi element u listi. Taj pokazivač se postavlja na vrijednost NULL.
Code:
int skini(lista **ulaz, lista **izlaz, int *element) {
lista *temp;
if(*izlaz) {
*element = (*izlaz)->element;
temp = *izlaz;
*izlaz = (*izlaz)->sljed;
free(temp);
if(*izlaz == NULL) *ulaz = NULL;
return 1;
}
return 0;
}
Operacija skidanja elemenata iz reda realiziranog listom je puno jednostavnija. Potrebno je pokazivač izlaz preusmjeriti na sljedeći element u redu, a onaj element koji se skida se sprema u varijablu čija je adresa predana kao argument funkciji (ako ti taj element treba u pozivajućem programu). Konačno, oslobađa se memorija koja je bila potrebna za dodavanje tog elementa redu i funkcija vraća 1. Funkcija će vratiti nulu samo u slučaju ako je izlaz NULL pokazivač.
Implementacija algoritama: LRU, FIFO , Optimalni i Random
