Μία δομή καλείται ουρά FIFO (FIFO queue), όταν ικανοποιεί τις απαιτήσεις που θέτει ο ακόλουθος Αφηρημένος Τύπος Δεδομένων ΑΤΔ:
enqueue(x) Τοποθετεί το στοιχείο x στο τέλος της ουράς
dequeue() Επιστρέφει το κορυφαίο στοιχείο, αφαιρώντας το
Η ουρά FIFO, όπως εύκολα διαπιστώνει κανείς, αντιστοιχεί στη γνωστή μας ουρά αναμονής στις διάφορες υπηρεσίες. Στην ουρά FIFO πρέπει να παρατηρηθεί πως το μόνο που χρειαζόμαστε είναι δύο δείκτες head και rear προς το κορυφαίο και το τελευταίο, αντίστοιχα, στοιχείο της δομής. Η ουρά FIFO είναι στενή συγγενής της στοίβας, καθώς μία ουρά είναι μία συλλογή από αντικείμενα που εισάγονται και διαγράφονται με βάση την αρχή: Όποιο εισάγεται πρώτο, εξάγεται και πρώτο (FIFO-first-in-first-out). Δηλαδή, τα στοιχεία εισάγονται οποιαδήποτε στιγμή, αλλά το στοιχείο που διαγράφεται οποιαδήποτε στιγμή είναι αυτό που έχει παραμείνει τον περισσότερο χρόνο. Στην παρακάτω εικόνα αντικατοπτρίζεται η εισαγωγή στοιχείου σε μία FIFO:
Στην παρακάτω εικόνα φαίνεται η αφαίρεση του κορυφαίου στοιχείου από μία FIFO:
Προγραμματισρτικά η ουρά FIFO υλοποιείται όπως φαίνεται παρακάτω:
public class FIFO
{
private int numberElements; // Πλήθος των αποθηκευμένων κόμβων
private SNode head, rear; // Δείκτες προς κεφαλή και ουρά
public FIFO()
{
numberElements=0;
head=null; // Δημιουργία κεφαλής
rear=null; // Δημιουργία ουράς
}
public int size()
{
return numberElements;
}
public boolean isEmpty()
{
return (numberElements < 1);
}
public void enqueue(Item item) // Προσθήκη στο τέλος ενός νέου κόμβου
{
SNode x=new SNode(null, item);
if (isEmpty()) // Η ουρά είναι αρχικά άδεια
head=x;
else // Ο νέος κόμβος θα προστεθεί στο τέλος
rear.setNext(x);
rear=x; // Ενημέρωση της νέας ουράς
numberElements++; // Προσαρμογή μεγέθους
}
public Item dequeue() // Αφαίρεση του πρωτου κόμβου
{
SNode temp;
if (isEmpty())
{
System.out.println("Η ουρά είναι άδεια");
return null;
}
temp=head;
head=head.getNext();
temp.setNext(null);
numberElements--;
if (numberElements==0)
rear=null; // Η ουρά είναι πλέον άδεια
return temp.getItem();
}
public Item first() // Επιστροφή του κορυφαίου στοιχείου δίχως αφαίρεση του
{
if (isEmpty())
{
System.out.println("Η ουρά είναι άδεια");
return null;
}
return head.getItem();
}
} // Τέλος της κλάσης FIFO