Διαφορά μεταξύ Stack και Heap

Stack vs Heap

Η στοίβα είναι μια λίστα με τις οποίες η εισαγωγή και διαγραφή των στοιχείων της λίστας μπορεί να γίνει μόνο στο ένα άκρο μπλουζα. Λόγω αυτού του λόγου, η στοίβα θεωρείται δομή δεδομένων LIFO (Last in First out). Το σωρό είναι μια ειδική δομή δεδομένων που βασίζεται σε δέντρα και ικανοποιεί μια ειδική ιδιότητα που ονομάζεται ιδιοκτησία σωρού. Επίσης, ένα σωρό είναι ένα πλήρες δέντρο, που σημαίνει ότι δεν υπάρχουν κενά μεταξύ των φύλλων του δέντρου i. μι. σε ένα ολοκληρωμένο δέντρο, κάθε επίπεδο συμπληρώνεται πριν προστεθεί ένα νέο επίπεδο στο δέντρο και οι κόμβοι σε ένα δεδομένο επίπεδο γεμίζονται από αριστερά προς τα δεξιά.

Τι είναι το Stack;

Όπως αναφέρθηκε προηγουμένως, η στοίβα είναι μια δομή δεδομένων στην οποία τα στοιχεία προστίθενται και αφαιρούνται από ένα μόνο άκρο που ονομάζεται κορυφή. Οι στοίβες επιτρέπουν μόνο δύο βασικές λειτουργίες που ονομάζονται push and pop. Η λειτουργία ώθησης προσθέτει ένα νέο στοιχείο στην κορυφή της στοίβας. Η λειτουργία pop καταργεί ένα στοιχείο από την κορυφή της στοίβας. Εάν η στοίβα είναι ήδη γεμάτη, όταν εκτελείται μια λειτουργία ώθησης, θεωρείται ως υπερχείλιση στοίβας. Αν μια λειτουργία pop εκτελείται σε μια ήδη κενή στοίβα, θεωρείται ως υποκόμη στοίβας. Λόγω του μικρού αριθμού λειτουργιών που θα μπορούσαν να εκτελεστούν σε μια στοίβα, θεωρείται ως περιορισμένη δομή δεδομένων. Επιπλέον, σύμφωνα με τον τρόπο που ορίζονται οι λειτουργίες push και pop, είναι σαφές ότι τα στοιχεία που προστέθηκαν τελευταία στη στοίβα βγαίνουν πρώτα από τη στοίβα. Συνεπώς, η στοίβα θεωρείται δομή δεδομένων LIFO.

Τι είναι το σωρό;

Όπως αναφέρθηκε προηγουμένως, ο σωρός είναι ένα πλήρες δέντρο που ικανοποιεί την ιδιότητα σωρού. Η ιδιότητα Heap δηλώνει ότι, εάν y είναι παιδί κόμβος x, τότε η τιμή που έχει αποθηκευτεί στον κόμβο x θα πρέπει να είναι μεγαλύτερη ή ίση με την τιμή που είναι αποθηκευμένη στον κόμβο y (δηλ. Τιμή (x) ≥ τιμή (y)). Αυτή η ιδιότητα υποδηλώνει ότι ο κόμβος με τη μεγαλύτερη τιμή θα τοποθετείται πάντα στη ρίζα. Ένας σωρός που κατασκευάζεται χρησιμοποιώντας αυτή την ιδιότητα ονομάζεται μέγιστος σωρός. Υπάρχει μια άλλη παραλλαγή της ιδιότητας σωρού που δηλώνει το αντίστροφο αυτής. (δηλ. τιμή (χ) ≤ τιμή (γ)). Αυτό σημαίνει ότι ο κόμβος με τη μικρότερη τιμή θα τοποθετείται πάντα στη ρίζα, ονομάζεται έτσι ένα min-σωρός. Υπάρχει ένα ευρύ φάσμα λειτουργιών που εκτελούνται σε σωρούς, όπως η εξεύρεση ελάχιστης (σε min-heaps) ή μέγιστης (σε max-heaps), διαγραφή ελάχιστου (σε min-σωρούς) ή μέγιστου (σε max-heaps) -κλειδιά) ή μείωση (σε min-σωρούς), κλπ.

Ποια είναι η διαφορά μεταξύ του Stack και του Heap;

Η κύρια διαφορά μεταξύ των στοίβων και των σωρών είναι ότι ενώ η στοίβα είναι γραμμική δομή δεδομένων, ο σωρός είναι μια μη γραμμική δομή δεδομένων. Η στοίβα είναι μια ταξινομημένη λίστα που ακολουθεί την ιδιότητα LIFO, ενώ ο σωρός είναι ένα πλήρες δέντρο που ακολουθεί την ιδιότητα σωρού.Επιπλέον, η στοίβα είναι μια περιορισμένη δομή δεδομένων που υποστηρίζει μόνο έναν περιορισμένο αριθμό λειτουργιών όπως push και pop, ενώ ο σωρός υποστηρίζει ένα ευρύ φάσμα λειτουργιών, όπως εύρεση και διαγραφή του ελάχιστου ή του μέγιστου, αύξηση ή μείωση του κλειδιού και συγχώνευση.