Stack vs Heap
Η Στοίβα είναι μια ταξινομημένη λίστα στην οποία η εισαγωγή και η διαγραφή των στοιχείων της λίστας μπορούν να γίνουν μόνο στο ένα άκρο που ονομάζεται κορυφή. Για αυτόν τον λόγο, η στοίβα θεωρείται ως δομή δεδομένων Last in First out (LIFO). Το Heap είναι μια ειδική δομή δεδομένων που βασίζεται σε δέντρα και ικανοποιεί μια ειδική ιδιότητα που ονομάζεται ιδιότητα σωρού. Επίσης, ένας σωρός είναι ένα πλήρες δέντρο, που σημαίνει ότι δεν υπάρχουν κενά μεταξύ των φύλλων του δέντρου, δηλαδή σε ένα πλήρες δέντρο κάθε επίπεδο συμπληρώνεται πριν από την προσθήκη ενός νέου επιπέδου στο δέντρο και οι κόμβοι σε ένα δεδομένο επίπεδο συμπληρώνονται από από αριστερά προς τα δεξιά.
Τι είναι το Stack;
Όπως αναφέρθηκε προηγουμένως, η στοίβα είναι μια δομή δεδομένων στην οποία προστίθενται και αφαιρούνται στοιχεία μόνο από το ένα άκρο που ονομάζεται κορυφή. Οι στοίβες επιτρέπουν μόνο δύο βασικές λειτουργίες που ονομάζονται push και pop. Η λειτουργία ώθησης προσθέτει ένα νέο στοιχείο στην κορυφή της στοίβας. Η λειτουργία pop αφαιρεί ένα στοιχείο από την κορυφή της στοίβας. Εάν η στοίβα είναι ήδη γεμάτη, όταν εκτελείται μια λειτουργία ώθησης, θεωρείται ως υπερχείλιση στοίβας. Εάν μια λειτουργία pop εκτελείται σε μια ήδη άδεια στοίβα, θεωρείται ως υποροή στοίβας. Λόγω του μικρού αριθμού λειτουργιών που θα μπορούσαν να εκτελεστούν σε μια στοίβα, θεωρείται ως μια περιορισμένη δομή δεδομένων. Επιπλέον, σύμφωνα με τον τρόπο με τον οποίο ορίζονται οι λειτουργίες push και pop, είναι σαφές ότι τα στοιχεία που προστέθηκαν τελευταία στη στοίβα βγαίνουν πρώτα από τη στοίβα. Επομένως, η στοίβα θεωρείται ως δομή δεδομένων LIFO.
Τι είναι το Heap;
Όπως αναφέρθηκε προηγουμένως, το heap είναι ένα πλήρες δέντρο που ικανοποιεί την ιδιότητα heap. Η ιδιότητα σωρού δηλώνει ότι, εάν το y είναι θυγατρικός κόμβος του x, τότε η τιμή που είναι αποθηκευμένη στον κόμβο x θα πρέπει να είναι μεγαλύτερη ή ίση με την τιμή που είναι αποθηκευμένη στον κόμβο y (δηλαδή τιμή(x) ≥ τιμή(y)). Αυτή η ιδιότητα υποδηλώνει ότι ο κόμβος με τη μεγαλύτερη τιμή θα τοποθετείται πάντα στη ρίζα. Ένας σωρός που κατασκευάζεται χρησιμοποιώντας αυτήν την ιδιότητα ονομάζεται max-heap. Υπάρχει μια άλλη παραλλαγή της ιδιότητας heap που δηλώνει το αντίστροφο. (δηλαδή τιμή(x) ≤ τιμή(y)). Αυτό σημαίνει ότι ο κόμβος με τη μικρότερη τιμή θα τοποθετείται πάντα στη ρίζα, και έτσι ονομάζεται min-heap. Υπάρχει ένα ευρύ φάσμα λειτουργιών που εκτελούνται σε σωρούς όπως η εύρεση του ελάχιστου (σε ελάχιστα σωρούς) ή του μέγιστου (σε μέγιστους σωρούς), η διαγραφή του ελάχιστου (σε ελάχιστες σωρούς) ή του μέγιστου (σε μέγιστους σωρούς), η αύξηση (σε μέγ. -σωρούς) ή μειούμενο (σε ελάχιστα σωρεία) κλειδί, κ.λπ.
Ποια είναι η διαφορά μεταξύ Stack και Heap;
Η κύρια διαφορά μεταξύ στοίβων και σωρών είναι ότι ενώ η στοίβα είναι μια γραμμική δομή δεδομένων, η στοίβα είναι μια μη γραμμική δομή δεδομένων. Η στοίβα είναι μια ταξινομημένη λίστα που ακολουθεί την ιδιότητα LIFO, ενώ ο σωρός είναι ένα πλήρες δέντρο που ακολουθεί την ιδιότητα heap. Επιπλέον, η στοίβα είναι μια περιορισμένη δομή δεδομένων που υποστηρίζει μόνο έναν περιορισμένο αριθμό λειτουργιών ως push και pop, ενώ το heap υποστηρίζει ένα ευρύ φάσμα λειτουργιών όπως εύρεση και διαγραφή του ελάχιστου ή μέγιστου, αύξηση ή μείωση του κλειδιού και συγχώνευση.
