Οδηγός για αρχάριους για την κατανόηση ουρών και ουρών προτεραιότητας

Ως προγραμματιστής, θα εργάζεστε με διαφορετικές δομές δεδομένων ανάλογα με το εύρος των έργων σας. Μια τέτοια έννοια είναι μια δομή δεδομένων ουράς. οι ουρές είναι απαραίτητες για τους μαθητές και χρησιμοποιούνται σε πολλούς σημαντικούς αλγόριθμους. Όπως και οι ουρές, έτσι και οι ουρές προτεραιότητας έχουν παρόμοια ιδέα αλλά έχουν μερικές θεμελιώδεις διαφορές.

Διαβάστε παρακάτω για να καταλάβετε τις ουρές και τις ουρές προτεραιότητας.

Τι είναι η ουρά;

Η ουρά είναι μια απλή δομή δεδομένων που έχει ποικιλία εφαρμογών σε έργα κωδικοποίησης πραγματικής ζωής. Οι δομές δεδομένων είναι εγγενώς αφηρημένες, αλλά για λόγους απλότητας, φανταζόμαστε ότι μια δομή δεδομένων ουράς έχει ένα γραμμικό σχήμα με δύο διαφορετικά άκρα.

Όσον αφορά την πολυπλοκότητα του χρόνου, μια ουρά επιτρέπει την εισαγωγή (enqueue) και τη διαγραφή (dequeue) σε χρόνο O (1). Λόγω της ασυμπτωτικής απόδοσής του, οι ουρές είναι αποτελεσματικές για μεγάλα σύνολα δεδομένων. Οι ουρές είναι από τη φύση της πρώτης προς την πρώτη έξοδο (FIFO), πράγμα που σημαίνει ότι ένα στοιχείο δεδομένων που εισάγεται πρώτο θα έχει πρώτα πρόσβαση. Αντίθετα, οι στοίβες έχουν χαρακτήρα τελευταίας-πρώτης-εξόδου (LIFO) και έχουν μόνο ένα ανοιχτό άκρο.

Φανταστείτε μια ουρά εισιτηρίων σε έναν κινηματογράφο. κάθε νέος πελάτης που φτάνει μπαίνει στην ουρά στο ένα άκρο. Ένας -ένας, κάθε πελάτης αγοράζει ένα εισιτήριο και αφήνει την ουρά από το μπροστινό μέρος. Η δομή δεδομένων ουράς λειτουργεί ακριβώς όπως κάθε ουρά πραγματικού κόσμου και τα δεδομένα εισάγονται (enqueue) στο ένα άκρο και αφαιρούνται (dequeue) στο άλλο άκρο. Τώρα μπορείτε να καταλάβετε το σκεπτικό γιατί οι ουρές ακολουθούν μια μεθοδολογία FIFO.

Μια ουρά έχει πολλές εφαρμογές κωδικοποίησης στην πραγματική ζωή. Χρησιμοποιείται συχνότερα σε εφαρμογές όπου τα δεδομένα δεν χρειάζονται άμεση επεξεργασία αλλά μάλλον με σειρά FIFO. Ο προγραμματισμός δίσκων, η ασύγχρονη μεταφορά δεδομένων, οι σηματοφόροι είναι μερικές τυπικές εφαρμογές. Οι εργασίες προγραμματισμού με σειρά προτεραιότητας, όπως η εκτύπωση εκτύπωσης ή τα buffer συσκευών εισαγωγής χρησιμοποιούν επίσης μια ουρά.

Τι είναι η ουρά προτεραιότητας;

Μια ουρά προτεραιότητας είναι παρόμοια με μια ουρά, αλλά έχει επιπλέον ιδιότητες. Όταν ένα στοιχείο δεδομένων ενσωματώνεται στην ουρά προτεραιότητας, του δίνεται ένας αριθμός προτεραιότητας. Σε αντίθεση με την αποβολή μιας τυπικής ουράς, τα στοιχεία δεδομένων με υψηλή προτεραιότητα αποκλείονται πριν από τα στοιχεία δεδομένων με χαμηλή προτεραιότητα. Η προτεραιότητα αντικαθιστά τη σειρά άφιξης σε ουρά προτεραιότητας, γι 'αυτό οι ουρές προτεραιότητας δεν έχουν συνεπή χαρακτήρα FIFO.

Σχετίζεται με: Αλγόριθμοι που πρέπει να γνωρίζει κάθε προγραμματιστής

Οι προγραμματιστές μπορούν να εφαρμόσουν μια ουρά προτεραιότητας με διάφορους τρόπους. Μια απλή εφαρμογή είναι η χρήση ενός πίνακα με ένα στοιχείο δεδομένων δομής/κλάσης και το στοιχείο δεδομένων θα περιέχει την προτεραιότητα κάθε στοιχείου δεδομένων και τα ίδια τα δεδομένα. Μια άλλη πρωτόγονη εφαρμογή ουράς προτεραιότητας είναι η χρήση μιας συνδεδεμένης λίστας. Οι ουρές προτεραιότητας που εφαρμόζονται μέσω συνδεδεμένων λιστών είναι λειτουργικές αλλά δεν είναι ιδανικές λόγω της απόδοσής τους.

Μπορείτε να εφαρμόσετε μια ουρά καλύτερης προτεραιότητας με έναν σωρό. Εάν θυμάστε, οι δυαδικοί σωροί δίνουν το μέγιστο ή το ελάχιστο στοιχείο σε 0 (1) χρόνο και η εισαγωγή διαρκεί μόνο 0 (logN) χρόνο. Με τη βοήθεια σωρών, οι ουρές προτεραιότητας δίνουν καλύτερη απόδοση ασυμπτωτικά σε σύγκριση με ουρές ή πίνακες.

Μια ουρά προτεραιότητας έχει επίσης μια ποικιλία βασικών εφαρμογών. Οι ουρές προτεραιότητας είναι ζωτικής σημασίας σε αλγόριθμους γραφημάτων, όπως το Prim’s Minimal Spanning Tree και ο αλγόριθμος Dijkstra's Shortest Path. Είναι επίσης ιδανικά για αλγορίθμους προγραμματισμού διαδικασιών μονάδας επεξεργασίας υπολογιστών (CPU).

Μάθετε δομές δεδομένων

Οι ουρές και οι ουρές προτεραιότητας είναι σημαντικές δομές δεδομένων για όλους τους αρχάριους. Είναι ζωτικής σημασίας οι μαθητές να αισθάνονται άνετα να εφαρμόζουν αυτές τις δομές δεδομένων και να τις χρησιμοποιούν σε διαφορετικά έργα.

Άλλες δομές δεδομένων όπως σωροί, στοίβες και δέντρα είναι εξίσου σημαντικές για μαθητές και επαγγελματίες. Είναι επίσης πολύ συχνό φαινόμενο οι συνεντευκτές να ρωτούν τους αιτούντες σχετικά με τις δομές δεδομένων.

Έχοντας διαβάσει αυτό το άρθρο, θα πρέπει τώρα να έχετε μια καλή ιδέα για το πώς λειτουργούν οι ουρές και οι ουρές προτεραιότητας. Εάν όλα φαίνονται ακόμα λίγο ασαφή, θα τα καταφέρετε καθώς αποκτάτε μεγαλύτερη εμπειρία στη χρήση τους.

Σωροί εναντίον Στοίβες: Τι τους χωρίζει;

Έχετε ακούσει για σωρούς και στοίβες, αλλά πότε πρέπει να χρησιμοποιήσετε το ένα πάνω στο άλλο;

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα