Στοίβα (δομή δεδομένων)
Η στοίβα είναι μία από τις πιο σημαντικές δομές δεδομένων στην επιστήμη των υπολογιστών. Για να καταλάβετε πώς λειτουργεί μια στοίβα, σκεφτείτε μια τράπουλα με κλειστά χαρτιά. Μπορούμε να έχουμε εύκολη πρόσβαση μόνο στο χαρτί που βρίσκεται στην κορυφή. Όταν θέλουμε να δούμε την κορυφαία κάρτα, υπάρχουν δύο πράγματα που μπορούμε να κάνουμε: μπορούμε να την κρυφοκοιτάξουμε, αλλά να την αφήσουμε στη στοίβα, ή μπορούμε να την πετάξουμε από τη στοίβα. Όταν βγάζουμε το κορυφαίο αντικείμενο, το αφαιρούμε από τη στοίβα. Αν θέλουμε να προσθέσουμε μια άλλη κάρτα στην κορυφή της στοίβας, την σπρώχνουμε.
Η στοίβα ονομάζεται συλλογή με τη σειρά που εμφανίζεται πρώτη φορά (last-in-first-out, LIFO). Αυτό σημαίνει ότι το τελευταίο πράγμα που προσθέσαμε (pushed) είναι το πρώτο πράγμα που αφαιρείται (popped). Αν το τελευταίο χαρτί που βάλαμε στη στοίβα μας ήταν ένας άσος, τότε το πρώτο χαρτί που βγάλαμε από την κορυφή είναι ο ίδιος άσος.
Δύο ενέργειες σε μια στοίβα: push και pop.
Ιστορία
Η στοίβα προτάθηκε για πρώτη φορά το 1955 και στη συνέχεια κατοχυρώθηκε με δίπλωμα ευρεσιτεχνίας το 1957 από τον Γερμανό Friedrich L. Bauer. Η ίδια ιδέα αναπτύχθηκε ανεξάρτητα, την ίδια περίπου εποχή, από τον Αυστραλό Charles Leonard Hamblin.
Άλλες λειτουργίες
Στις σύγχρονες γλώσσες υπολογιστών, η στοίβα υλοποιείται συνήθως με περισσότερες λειτουργίες από τις "push" και "pop". Ορισμένες υλοποιήσεις έχουν μια συνάρτηση που επιστρέφει το τρέχον μήκος της στοίβας. Μια άλλη τυπική βοηθητική λειτουργία είναι η "top" (επίσης γνωστή ως "peek"), η οποία μπορεί να επιστρέψει το τρέχον κορυφαίο στοιχείο της στοίβας χωρίς να το αφαιρέσει. Μια άλλη συνηθισμένη λειτουργία είναι η "dup", η οποία δημιουργεί ένα αντίγραφο του στοιχείου που βρίσκεται στην κορυφή της στοίβας.
Σχετικές σελίδες
- Μηχανή στοίβαξης
