[Powered by Google Translate] [Ουρά] [Chris Gerber, Πανεπιστήμιο Χάρβαρντ] Αυτό είναι CS50, CS50.TV] Μία χρήσιμη δομή δεδομένων για την αποθήκευση μια διατεταγμένη συλλογή των στοιχείων είναι μια ουρά. Χρησιμοποιείται όταν τα στοιχεία πρέπει να αφαιρεθούν με την ίδια σειρά όπως προστέθηκαν. Η έννοια αυτή αναφέρεται ως FIFO, που είναι ένα αρκτικόλεξο για το πρώτο μέσα, πρώτο έξω. Για να βοηθήσει απεικονίσει αυτό, μπορεί να είναι χρήσιμο στην εικόνα μια γραμμή ολοκλήρωση της παραγγελίας σε ένα κατάστημα. Καθώς οι άνθρωποι φτάνουν, περιμένουν στο πίσω μέρος της γραμμής. Το ταμείο παίρνει στροφές στη συνέχεια, την εξυπηρέτηση των πελατών στο μπροστινό μέρος, ο οποίος στη συνέχεια, κλείστε την μία γραμμή κάθε φορά. Στην επιστήμη των υπολογιστών, αναφερόμαστε στο μπροστινό μέρος της ουράς και το κεφάλι και το πίσω σαν την ουρά. Ένα παράδειγμα, όταν μπορούμε να χρησιμοποιήσουμε αυτό σε μια εφαρμογή είναι μια λίστα αναμονής για εγγραφές τάξη. Καθώς θέσεις καταστούν διαθέσιμα στην τάξη, το άτομο που είναι επικεφαλής της λίστας αναμονής παρέχεται η δυνατότητα να εγγραφούν στην τάξη. 

Μια ουρά μπορεί να κατασκευαστεί χρησιμοποιώντας οποιαδήποτε συλλογή που αποθηκεύει δεδομένα σε σειρά, όπως μια συστοιχία ή μια συνδεδεμένη λίστα. Μαζί με τη συλλογή για να αποθηκεύσετε τα στοιχεία στην ουρά, χρειαζόμαστε επίσης μια μέθοδο για να προσθέσετε στοιχεία στο τέλος της ουράς, το οποίο καλείται enqueuing, και άλλο να καταργήσετε ένα στοιχείο από την κεφαλή της ουράς, το οποίο καλείται dequeuing. Είναι συχνά χρήσιμο να συμπεριλάβει μια άλλη μέθοδο για να επιστρέψει το τρέχον μήκος της ουράς καθώς και μια μέθοδο για να ελέγξει εάν η ουρά είναι άδεια. Ας δούμε πώς μπορούμε να εφαρμόσει μια ουρά ακεραίων σε C, χρησιμοποιώντας μια σειρά για τη συλλογή των στοιχείων. Πρώτον, έχουμε δημιουργήσει μια δομή που ονομάζεται ουρά για να κρατήσει τις μεταβλητές μας. Θα χρησιμοποιήσουμε ένα πίνακα σταθερού μεγέθους 0 δείκτης των ακεραίων για την αποθήκευση των στοιχείων. Θα περιλαμβάνει επίσης μια μεταβλητή που ονομάζεται κεφάλι ότι αποθηκεύει το δείκτη του στοιχείου που είναι σήμερα στην κορυφή της ουράς. Μια τρίτη μεταβλητή, που ονομάζεται μήκος, θα χρησιμοποιηθεί να παρακολουθεί τον αριθμό των στοιχείων στη συστοιχία. Ως εναλλακτική λύση, θα μπορούσε να εξετάσει τη χρήση μια μεταβλητή που ονομάζεται ουρά ώστε να οδηγεί το τελευταίο στοιχείο πεδίου στη συστοιχία. Πριν γράφουμε πια κώδικα, Ας δοκιμάσουμε το σχεδιασμό μας. Ας ξεκινήσουμε με μια κενή σειρά του μήκους 0, με το κεφάλι οριστεί σε 0. Τώρα enqueue 4 τιμές ας - 6, 2, 3, και 1. Το μήκος θα είναι τώρα 4, και το κεφάλι θα παραμείνει στο 0. 

Τι θα συμβεί αν dequeue μια τιμή; Θα μειώσει το μήκος έως 3, ρυθμίσετε το κεφάλι προς 1, και επιστρέφει την τιμή 6. Ο κώδικας μπορεί να μοιάζει με αυτό. Εδώ έχουμε την dequeue λειτουργία, η οποία λαμβάνει ένα δείκτη στην ουρά - q - και ένα δείκτη στο στοιχείο, η οποία είναι μια τύπου int. Πρώτα ελέγξτε το μήκος της ουράς για να βεβαιωθείτε ότι είναι περισσότερο από 0, για να εξασφαλιστεί ότι υπάρχει ένα στοιχείο που πρέπει να dequeued. Στη συνέχεια, κοιτάμε στον πίνακα στοιχεία, επικεφαλής θέση, και να ορίσετε την αξία του στοιχείου είναι η αξία σε αυτή τη θέση. Στη συνέχεια αλλάζουμε το κεφάλι να είναι ο επόμενος δείκτης % Της χωρητικότητας. Εμείς στη συνέχεια μειώνουν το μήκος της ουράς από 1. Τέλος, θα επιστρέψει αλήθεια για να δείξει ότι η dequeue ήταν επιτυχής. Αν dequeue πάλι, το μήκος θα γίνει 2, το κεφάλι θα γίνει επίσης 2, και η επιστρεφόμενη τιμή θα είναι 2. 

Τι θα συμβεί αν enqueue άλλη αξία, όπως το 7; Όπως ήταν στο τέλος της ουράς, θα χρειαστεί να τυλίξει γύρω από και να αποθηκεύσει την τιμή σε μηδέν στοιχείο του πίνακα. Μαθηματικώς, αυτή μπορεί να παρασταθεί με την προσθήκη του μήκους με τον δείκτη της κεφαλής και την εκτέλεση ενός συντελεστή χρησιμοποιώντας την ικανότητα ουράς. Εδώ δηλαδή 2 +2, που είναι 4% 4, η οποία είναι 0. Μεταφράζοντας αυτή την ιδέα για να κωδικοποιήσει έχουμε αυτή τη λειτουργία. Εδώ βλέπουμε την enqueue λειτουργία, η οποία λαμβάνει ένα δείκτη στην ουρά - q - και λαμβάνει το στοιχείο που πρέπει να enqueued, η οποία είναι ένας ακέραιος. Είμαστε δίπλα ελέγξτε για να βεβαιωθείτε ότι η χωρητικότητα της ουράς εξακολουθεί να είναι μεγαλύτερη από την τρέχουσα μήκος της ουράς. Στη συνέχεια, το στοιχείο φυλάσσεται στη συστοιχία στοιχείων στο δείκτη η οποία καθορίζεται από την κεφαλή +% μήκους η ικανότητα της ουράς. Θα αυξηθεί τότε το μήκος ουράς από 1, και στη συνέχεια επιστρέφουν αλήθεια για να δείξει ότι η enqueue λειτουργία ήταν επιτυχής. 

Εκτός από τις δύο λειτουργίες έχουμε αναφέρει, υπάρχουν δύο πρόσθετες λειτουργίες. Πρώτη είναι η λειτουργία IsEmpty, η οποία λαμβάνει ένα δείκτη στην ουρά και επαληθεύει ότι το μήκος είναι 0. Η δεύτερη είναι η συνάρτηση μήκους, η οποία λαμβάνει επίσης ένα δείκτη στην ουρά και επιστρέφει το τρέχον μήκος από το struct. Αυτή η σύντομη επισκόπηση έδειξε μια πιθανή εφαρμογή ενός ουρά. Ένας από τους περιορισμούς στην παρούσα υλοποίηση είναι ότι η ουρά έχει ένα σταθερό μέγιστο μέγεθος. Αν προσπαθήσετε να προσθέσετε περισσότερα στοιχεία από ό, τι η ουρά μπορεί να κρατήσει, μπορεί να χρειαστεί να αγνοήσει το αίτημα και να ρίξει το στοιχείο, ή μπορούμε να προτιμούν να επιστρέψουν κάποιο είδος του λάθους. Χρησιμοποιώντας μια συνδεδεμένη λίστα αντί μία συστοιχία θα καταστήσει ευκολότερη την δυναμικά το μέγεθος της ουράς. Ωστόσο, δεδομένου ότι δεν έχουμε άμεση πρόσβαση στα στοιχεία μιας συνδεδεμένη λίστα, αν δεν παρακολουθείτε της ουράς, θα πρέπει να σαρώσει το σύνολο συνδεδεμένη λίστα για να φτάσετε στο τέλος κάθε χρόνου. Θα μπορούσαμε επίσης να εξετάσουν τη χρήση μια σειρά από άλλου τύπου στοιχεία, όπως structs, να δημιουργήσει ουρές των πιο πολύπλοκα στοιχεία. Ανακαλώντας στη μνήμη μας παράδειγμα μιας κατηγορίας λίστα αναμονής, οι δομές αυτές θα μπορούσαν να αποτελέσουν τα επιμέρους φοιτητές. 

Το όνομά μου είναι Chris Gerber, και αυτό είναι CS50. [CS50.TV] Και επιστρέφει - >> Ένας περισσότερος χρόνος. Και αλήθεια να επιστρέψει δείχνουν ότι - η ουρά ήταν επιτυχής. -% Η ικανότητα της ουράς - Είναι πρόκειται να είναι διασκέδαση σε επεξεργασία. [Γέλια]