Σε όλες τις εκφάνσεις της καθημερινής μας ζωής, βιώνουμε την εμπειρία να είμαστε μέλη ουράς (queue), λόγου χάριν, όταν περιμένουμε να εξυπηρετηθούμε από το ταμείο μίας τράπεζας ή να κάνουμε χρήση ουράς για παράδειγμα σε φυλλομετρητή (browser), όπου ο φυλλομετρητής έχει κάποιο κουμπί back, που μας μεταφέρει σε προηγούμενες σελίδες του διαδικτύου. Τώρα θα ασχοληθούμε με το πρώτο βασικό είδος ουρών, τη στοίβα.
Μία δομή καλείται στοίβα (stack) ή ουρά LIFO (Last in First out queue), όταν ικανοποιεί τις απαιτήσεις που θέτει ο ακόλουθος Αφηρημένος Τύπος Δεδομένων (ATΔ):
isEmpty() Επιστρέφει true εάν η στοίβα μας είναι άδεια, αλλιώς false
push(x) Ενθέτει το στοιχείο x στην κορυφή της στοίβας
pop() Επιστρέφει το κορυφαίο στοιχείο της στοίβας, διαγράφοντας το από τη στοίβα
top() Επιστρέφει το κορυφαίο στοιχείο της στοίβας, χωρίς να το σβήσει
Παρατηρήστε πως πρώτον η πρόσβαση είναι δυνατή μόνο στο κορυφαίο στοιχείο της ακολουθίας και δεύτερον τα στοιχεία εξέρχονται της δομής με σειρά αντίθετη από τη σειρά εισαγωγής (οι έσχατοι έσονται πρώτοι).
Το κουμπί back ενός φυλλομετρητή (browser) ουσιαστικά εκτελεί pop σε μία στοίβα ήδη ανακτημένων σελίδων ενώ η θήκη για τα κέρματα (τα κέρματα είναι το ένα επάνω στο άλλο) αποτελεί ένα απλό παράδειγμα στοίβας, ιδιαίτερα χρήσιμης στις καθημερινές συναλλαγές μας. Ο ΑΤΔ δύναται να υλοποιηθεί με τη βοήθεια μίας λίστας.
Η υλοποίηση με απλή λίστα είναι εξαιρετικά απλή. Χρησιμοποιείται μία απλή διασυνδεδεμένη λίστα κόμβων, διαθέτουσα κεφαλής top, αλλά όχι ουρά. Οπότε, η πράξη της push ανάγεται σε εισαγωγή στην κορυφή της λίστας ενώ αυτή της pop ιασοδυναμεί με απόσβεση της κορυφής και επιστροφή του στεγαζόμενου στοιχείου. Στο παρακάτω σχήμα θα δούμε τα στιγμιότυπα της push και της pop σε διασυνδεδεμένη λίστα:
Προγραμματιστικά η υλοποίηση της στοίβας είναι η παρακάτω:
public class Stack
{
private SNode top; // Αναφορά προς τον κορυφαίο κόμβο
private int size; // Πλήθος κόμβων της στοίβας
public Stack() // Αρχικοποίηση μίας άδειας στοίβας
{
top=null;
size=0;
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size < 1);
}
public void push(Item item)
{
SNode x=new SNode(top, item); // Δημιουργία του νέου κόμβου
top=x;
size++;
}
public Item pop()
{
SNode oldTop;
if (isEmpty())
{
System.out.println("Η στοίβα είναι άδεια");
return null;
}
oldTop=top;
top=top.getNext(); // Το νέο στοιχείο
oldTop.setNext(null); // Γείωση
size--;
return oldTop.getItem(); // Επιστροφή του στοιχείου της παλιάς κορυφής
}
public Item top()
{
if (isEmpty())
{
System.out.println("Η στοίβα είναι άδεια");
return null;
}
return top.getItem();
}
} // Τέλος της Stack