DOUG LLOYD: Έτσι, αν έχετε παρακολούθησαν το βίντεο σε στοίβα,
αυτό κατά πάσα πιθανότητα θα αισθάνονται σαν ένα μικρό κομμάτι του Deja Vu.
Είναι πρόκειται να ένα πολύ παρόμοια ιδέα, μόνο με μια μικρή συστροφή σε αυτό.
Εμείς πάμε να μιλήσουμε τώρα για ουρές.
Έτσι, μια ουρά, παρόμοια με μια στοίβα, είναι ένα άλλο είδος δομής δεδομένων
ότι μπορούμε να χρησιμοποιήσουμε για να διατηρήσει δεδομένα με οργανωμένο τρόπο.
Παρόμοια με μια στοίβα, αυτό μπορεί να εφαρμοστεί
ως μια σειρά ή μια συνδεδεμένη λίστα.
Σε αντίθεση με μια στοίβα, οι κανόνες ότι θα χρησιμοποιήσει για να καθορίσει
όταν παίρνουν προστεθούν και να αφαιρεθούν από τα πράγματα μια ουρά είναι λίγο διαφορετική.
>> Σε αντίθεση με μια στοίβα, η οποία είναι μια δομή LIFO,
τελευταία in, first out, μια ουρά FIFO είναι δομή, FIFO, first in, first out.
Τώρα ουρές, ίσως έχουν μια αναλογία με ουρές.
Αν έχετε ποτέ στην ουρά πάρκο ψυχαγωγίας ή σε μια τράπεζα,
υπάρχει ένα είδος επιείκειας δομή υλοποίησης.
Το πρώτο πρόσωπο στη γραμμή στο η τράπεζα είναι το πρώτο πρόσωπο
που παίρνει για να μιλήσει με τον αφηγητή.
>> Θα ήταν ένα είδος αγώνα προς τα κάτω, αν ο μόνος τρόπος
πήρατε να μιλήσετε με τον αφηγητή κατά τη τράπεζα ήταν το τελευταίο πρόσωπο στη γραμμή.
Όλοι θα θέλουν πάντα να είναι το τελευταίο πρόσωπο στη γραμμή,
και το πρόσωπο που ήταν εκεί πρώτα που έχει να περιμένει για λίγο,
θα μπορούσε να είναι εκεί για ώρες, και ώρες, και ώρες
προτού να έχει την ευκαιρία να πραγματικά αποσύρουν χρήματα στην τράπεζα.
Και έτσι ουρές είναι το είδος του αμεροληψία δομή υλοποίησης.
Αλλά αυτό δεν σημαίνει απαραίτητα ότι στοίβες είναι ένα κακό πράγμα, απλά
ότι οι ουρές είναι ένας άλλος τρόπος για να το κάνουμε.
Έτσι και πάλι η ουρά είναι η πρώτη στην πρώτη έξω, έναντι μιας στοίβας που διαρκούν σε,
first out.
Παρόμοια με μια στοίβα, έχουμε δύο πράξεις
ότι μπορούμε να εκτελέσουμε σε ουρές.
Τα ονόματα είναι Τοποθέτηση στην ουρά, η οποία είναι να προσθέσει ένα νέο στοιχείο με το άκρο της ουράς,
και dequeue, η οποία είναι για να αφαιρέσετε το παλαιότερο
στοιχείου από το μπροστινό μέρος της ουράς.
Έτσι θα πάμε να προσθέσετε στοιχεία πάνω στο άκρο της ουράς,
και θα πάμε για να καταργήσετε στοιχεία από το μπροστινό μέρος της ουράς.
Και πάλι, με τη στοίβα, ήμασταν προσθήκη στοιχεία στην κορυφή της στοίβας
και την άρση των στοιχείων από την κορυφή της στοίβας.
Έτσι, με Τοποθέτηση στην ουρά, είναι η προσθήκη σε το τέλος, αφαιρώντας από το μέτωπο.
Έτσι, το παλαιότερο πράγμα εκεί είναι πάντα το επόμενο πράγμα
να βγει, αν προσπαθήσουμε και dequeue κάτι.
>> Έτσι και πάλι, με ουρές, μπορούμε βασισμένη σε πίνακα εφαρμογών
και συνδέεται κατάλογο βάσει εφαρμογές.
Θα ξεκινήσουμε πάλι με array-based υλοποιήσεις.
Ο ορισμός δομή φαίνεται αρκετά παρόμοια.
Έχουμε μια άλλη σειρά υπάρχει αξίας τύπο δεδομένων,
έτσι ώστε να μπορεί να κρατήσει αυθαίρετα τύπους δεδομένων.
Είμαστε και πάλι πρόκειται να χρησιμοποιήσετε ακέραιοι σε αυτό το παράδειγμα.
>> Και ακριβώς όπως με μας βασισμένη σε πίνακα υλοποίηση στοίβας,
επειδή είμαστε χρησιμοποιώντας ένα σειρά, αναγκαστικά θα
έχουν αυτό το περιορισμό ότι το είδος C της επιβάλλει σε μας, το οποίο είναι εμείς
δεν έχουν το δυναμισμό μας ικανότητα να αναπτύσσονται και να συρρικνωθεί το φάσμα.
Πρέπει να αποφασίσουμε στην αρχή τι είναι ο μέγιστος αριθμός των πραγμάτων
ότι μπορούμε να βάλουμε σε αυτό ουρά, και σε αυτή την περίπτωση,
ικανότητας θα ήταν κάποια λίβρα ορίζεται σταθερά στον κώδικά μας.
Και για τους σκοπούς του παρόντος βίντεο, χωρητικότητα θα είναι 10.
>> Πρέπει να παρακολουθείτε το μπροστινό της ουράς
έτσι ώστε να γνωρίζουν ποιο είναι το στοιχείο θέλουμε να dequeue,
και θα πρέπει επίσης να παρακολουθείτε κάτι else-- τον αριθμό των στοιχείων
ότι έχουμε στην ουρά μας.
Παρατηρήστε δεν είμαστε παρακολούθηση από το τέλος της ουράς, μόλις
το μέγεθος της ουράς.
Και ο λόγος γι 'αυτό ελπίζουμε ότι θα γίνει λίγο πιο σαφής σε μια στιγμή.
Μόλις έχουμε ολοκληρώσει Ο ορισμός αυτός ο τύπος,
έχουμε ένα νέο τύπο δεδομένων που ονομάζεται ουρά, το οποίο μπορούμε τώρα
δηλώνουν τις μεταβλητές αυτού του τύπου δεδομένων.
Και κάπως συγκεχυμένα, έχω αποφασίσει για να καλέσετε αυτήν την ουρά q, η επιστολή
q αντί του τύπου δεδομένων q.
>> Τόσο εδώ είναι η ουρά μας.
Είναι μια δομή.
Περιέχει τρία μέλη ή τρεις πεδία, ένας πίνακας μεγέθους χωρητικότητας.
Σε αυτή την περίπτωση, η ικανότητα είναι 10.
Και αυτή η συστοιχία είναι πρόκειται να κρατήσει ακέραιοι.
Στο πράσινο είναι η ουρά μπροστά από μας, η επόμενο στοιχείο να αφαιρεθεί, και το κόκκινο
θα είναι το μέγεθος της ουράς, πόσα στοιχεία είναι σήμερα
υπάρχοντα στην ουρά.
Έτσι, αν πούμε q.front ίσων 0, και το μέγεθος q.size ισούται 0--
βάζουμε 0s σε αυτούς τους τομείς.
Και σε αυτό το σημείο, είμαστε λίγο πολύ έτοιμα να αρχίσουν να εργάζονται με ουρά μας.
>> Έτσι, η πρώτη πράξη μπορούμε εκτελέσει είναι να Τοποθέτηση στην ουρά κάτι,
για να προσθέσετε ένα νέο στοιχείο στο το άκρο της ουράς.
Λοιπόν, τι χρειαζόμαστε για να κάνει στη γενική περίπτωση;
Λοιπόν αυτή η λειτουργία Τοποθέτηση στην ουρά ανάγκες να αποδεχθεί ένα δείκτη για την ουρά μας.
Και πάλι, αν είχαμε δηλώσει ουρά μας σε παγκόσμιο επίπεδο,
δεν θα χρειαστεί να το κάνετε αυτό απαραίτητα, αλλά σε γενικές γραμμές, μπορούμε
Πρέπει να αποδεχτείτε τους δείκτες σε δομές δεδομένων
όπως αυτό, διότι διαφορετικά, είμαστε περνώντας από value-- είμαστε
περνώντας σε αντίγραφα της ουράς, και έτσι δεν είμαστε πραγματικά αλλάζει
η ουρά που θέλουμε να αλλάξουμε.
>> Το άλλο πράγμα που πρέπει να κάνει είναι να αποδεχθεί ένα στοιχείο δεδομένων του κατάλληλου τύπου.
Και πάλι, σε αυτή την περίπτωση, είναι πρόκειται να είναι ακέραιοι,
αλλά θα μπορούσε αυθαίρετα δηλώνει το είδος των δεδομένων ως τιμή
και να χρησιμοποιήσετε αυτό γενικότερα.
Αυτό είναι το στοιχείο που θέλουμε να Τοποθέτηση στην ουρά, θέλουμε να προσθέσουμε στο τέλος της ουράς.
Στη συνέχεια, θέλουμε πραγματικά να τοποθετήστε τα δεδομένα στην ουρά.
Σε αυτήν την περίπτωση, η τοποθέτηση σε σωστή θέση του πίνακα μας,
και, στη συνέχεια, θέλουμε να αλλάξουμε το μέγεθος της ουράς, πόσα στοιχεία μας
Αυτήν τη στιγμή έχετε.
>> Οπότε ας ξεκινήσουμε.
Εδώ είναι, και πάλι, ότι η γενική Δήλωση λειτουργία μορφή
Τοποθέτηση στην ουρά για το τι μπορεί να μοιάζει.
Και εδώ πηγαίνουμε.
Ας Τοποθέτηση στην ουρά του αριθμού 28 στην ουρά.
Λοιπόν, τι θα κάνουμε;
Λοιπόν, η ουρά μπροστά μας είναι στο μηδέν, και το μέγεθος της ουράς μας
είναι στο 0, και έτσι πιθανόν να θέλετε να βάλετε ο αριθμός 28 στην συστοιχία του αριθμού στοιχείου
0, σωστά;
Έτσι έχουμε τώρα τοποθετείται ότι εκεί μέσα.
Έτσι, τώρα τι πρέπει να αλλάξουμε;
Δεν θέλουμε να αλλάξουμε το μπροστινό μέρος της ουράς,
επειδή θέλουμε να γνωρίζουμε τι στοιχείο μπορεί να χρειαστεί να dequeue αργότερα.
Έτσι, ο λόγος που έχουμε μπροστά εκεί Είναι το είδος του δείκτη για το τι είναι
το παλαιότερο πράγμα στον πίνακα.
Καλά το παλαιότερο πράγμα στον array-- σε Πράγματι, το μόνο πράγμα στον πίνακα δεξιά
now-- είναι 28, η οποία είναι σε θέση πίνακα 0.
Γι 'αυτό και δεν θέλουμε να αλλάξετε ότι το πράσινο αριθμό,
γιατί αυτό είναι το παλαιότερο στοιχείο.
Αντίθετα, θέλουμε να αλλάξουμε το μέγεθος.
Έτσι, σε αυτή την περίπτωση, θα αυξήσετε το μέγεθος σε 1.
>> Τώρα, μια γενική ιδέα για το είδος του, όπου η επόμενο στοιχείο πρόκειται να πάει σε μια ουρά
είναι να προσθέσετε αυτούς τους δύο αριθμούς μαζί, εμπρός και το μέγεθος,
και ότι θα σας πω, όπου το επόμενο στοιχείου στην ουρά πρόκειται να πάει.
Έτσι τώρα ας Τοποθέτηση στην ουρά έναν άλλο αριθμό.
Ας Τοποθέτηση στην ουρά 33.
Έτσι, 33 πρόκειται να πάει σε θέση πίνακα 0 και 1.
Έτσι, στην περίπτωση αυτή, πρόκειται να μπω σε θέση πίνακα 1,
και τώρα το μέγεθος της ουράς μας είναι 2.
>> Και πάλι, δεν είμαστε αλλαγή η ουρά μπροστά από μας,
28 επειδή εξακολουθεί να είναι η αρχαιότερο στοιχείο, και εμείς
Θέλετε to-- όταν τελικά πάρει να dequeuing, απομακρύνοντας στοιχεία
από αυτήν την ουρά, θέλουμε να γνωρίζουμε όπου το παλαιότερο στοιχείο είναι.
Και γι 'αυτό πρέπει πάντα να διατηρήσουν κάποια ένδειξη για το πού είναι αυτό.
Έτσι, αυτό είναι ό, τι το 0 είναι εκεί για.
Αυτό είναι ό, τι υπάρχει μπροστά για.
>> Ας Τοποθέτηση στην ουρά σε ένα ακόμη στοιχείο, 19.
Είμαι βέβαιος ότι μπορείτε να μαντέψετε όπου 19 πρόκειται να πάει.
Δεν πρόκειται να μπω σε συστοιχία αριθμός θέσης 2.
Αυτό είναι 0 συν 2.
Και τώρα το μέγεθος της ουράς μας είναι 3.
Έχουμε 3 στοιχεία σε αυτό.
Έτσι, αν ήμασταν σε αυτά, και εμείς δεν πρόκειται προς τα δεξιά τώρα, Τοποθέτηση στην ουρά και ένα άλλο στοιχείο,
θα μπω σε θέση πίνακα αριθμός 3, και το μέγεθος της ουράς μας
θα είναι 4.
Έτσι έχουμε αρκετά στοιχεία enqueued τώρα.
Ας αρχίσουμε να τα αφαιρέσετε.
Ας τους dequeue από την ουρά.
>> Έτσι, παρόμοια με ποπ, η οποία είναι είδος του αναλόγου αυτού για τις στοίβες,
dequeue πρέπει να δεχτεί μια δείκτη στο queue-- και πάλι,
εάν δεν έχει δηλωθεί σε παγκόσμιο επίπεδο.
Τώρα θέλουμε να αλλάξουμε την τοποθεσία του στο μπροστινό μέρος της ουράς.
Αυτό είναι όπου το είδος του έρχεται στο παιχνίδι, ότι μπροστά μεταβλητή,
γιατί όταν θα αφαιρέσει ένα στοιχείο, που θέλουμε
για να προχωρήσουμε στο επόμενο αρχαιότερο στοιχείο.
>> Στη συνέχεια, θέλουμε να μειωθεί το μέγεθος της ουράς,
και, στη συνέχεια, θέλουμε να επιστρέψουμε την τιμή ότι αφαιρέθηκε από την ουρά.
Και πάλι, δεν θέλουμε να το απορρίψει μόνο.
Είμαστε πιθανώς τα εξόρυξη το από το queue-- είμαστε
dequeuing επειδή νοιαζόμαστε γι 'αυτό.
Έτσι θέλουμε αυτή τη λειτουργία για να επιστρέψει ένα στοιχείο δεδομένων της αξίας του τύπου.
Και πάλι, στην περίπτωση αυτή, η τιμή είναι ακέραιος.
>> Έτσι τώρα ας dequeue κάτι.
Ας αφαιρέσετε ένα στοιχείο από την ουρά.
Αν πούμε int x ισούται & Q, σύμβολο q-- και πάλι ότι είναι ένας δείκτης σε αυτά τα δεδομένα q
structure-- ποιο στοιχείο πρόκειται να dequeued;
Σε αυτή την περίπτωση, επειδή αυτό είναι ένα πρώτο in, first out δομή δεδομένων, FIFO,
το πρώτο πράγμα που βάζουμε σε αυτό ουρά ήταν 28, και στην προκειμένη περίπτωση,
θα πάμε για να πάρει 28 από η ουρά, δεν 19, το οποίο είναι αυτό
θα κάναμε αν αυτό ήταν μια στοίβα.
Εμείς πάμε για να πάρει 28 από την ουρά.
>> Παρόμοια με αυτό που κάναμε με μια στοίβα, δεν είμαστε στην πραγματικότητα
πρόκειται να διαγράψει 28 από την ίδια την ουρά,
είμαστε ακριβώς πρόκειται να είδος της προσποιούμαστε ότι δεν υπάρχει.
Έτσι πρόκειται να μείνει εκεί στη μνήμη, αλλά είμαστε μόνο
πρόκειται να το είδος του να αγνοήσει κινώντας οι άλλοι δύο πεδία δεδομένων q μας
δομή.
Εμείς πάμε για να αλλάξει το μέτωπο.
Q.front τώρα πρόκειται να είναι 1, γιατί αυτό είναι τώρα
το παλαιότερο στοιχείο που έχουμε σε μας ουρά, γιατί έχουμε ήδη αφαιρέσει 28,
ο οποίος ήταν ο πρώην αρχαιότερο στοιχείο.
>> Και τώρα, θέλουμε να αλλάξουμε το μέγεθος της ουράς
σε δύο στοιχεία αντί για τρεις.
Τώρα θυμάμαι είπα νωρίτερα, όταν θέλετε να προσθέσετε στοιχεία στην ουρά,
το βάζουμε σε μία θέση πίνακα που είναι το άθροισμα των εμπρόσθιων και μεγέθους.
Έτσι, σε αυτή την περίπτωση, είμαστε ακόμα βάζοντας αυτό, το επόμενο στοιχείο στην ουρά,
σε θέση πίνακα 3, και θα δούμε ότι σε ένα δευτερόλεπτο.
>> Έτσι έχουμε τώρα dequeued μας πρώτο στοιχείο από την ουρά.
Ας το κάνουμε ξανά.
Ας αφαιρέσει ένα άλλο στοιχείο από την ουρά.
Στην περίπτωση αυτή, η τρέχουσα παλαιότερα στοιχείο είναι η τοποθεσία πίνακα 1.
Αυτό είναι ό, τι q.front μας λέει.
Αυτό το πράσινο κουτί μας λέει ότι ότι είναι το παλαιότερο στοιχείο.
Και έτσι, θα καταστεί x 33.
Θα ακριβώς το είδος του ξεχάσω ότι υπάρχει 33 στη συστοιχία,
και θα πω ότι τώρα, η νέα αρχαιότερο στοιχείο στην ουρά
είναι στη θέση πίνακα 2, και το μέγεθος του της ουράς, ο αριθμός των στοιχείων
έχουμε στην ουρά, είναι 1.
Τώρα ας Τοποθέτηση στην ουρά κάτι, και εγώ είδος της έδωσε αυτό μακριά πριν από ένα δευτερόλεπτο,
αλλά αν θέλουμε να θέσει σε 40 η ουρά, όπου είναι 40 πρόκειται να πάει;
Λοιπόν έχουμε θέτοντάς στην ουρά q.front συν μέγεθος,
και έτσι είναι λογικό να πραγματικά να βάλει 40 εδώ.
Τώρα παρατηρούμε ότι σε κάποια στιγμή, θα πάμε
για να φτάσετε στο τέλος της σειρά μας εντός του q,
αλλά ότι έσβησε 28 και 33-- από όπου και αν στην πραγματικότητα, τεχνικά
ανοιχτούς χώρους, έτσι δεν είναι;
Και έτσι, μπορούμε να eventually-- ο κανόνας της προσθήκης
αυτά τα δύο μπορεί τελικά together-- μας Πρέπει να mod από το μέγεθος της ικανότητας
έτσι ώστε να μπορεί να τυλιχτεί γύρω.
>> Έτσι, αν έχουμε την ευκαιρία να στοιχείου αριθμός 10, αν είμαστε
αντικαθιστώντας το στοιχείο του αριθμού 10, είχαμε πραγματικά να το θέσω σε θέση πίνακα 0.
Και αν επρόκειτο να συστοιχία location-- Με συγχωρείτε,
αν θέλουμε να προστίθενται μαζί, και πήραμε τον αριθμό
11 θα είναι όταν θα πρέπει να θέσει αυτό, το οποίο δεν υπάρχει σε αυτό το array--
θα πρέπει να βγείτε έξω από τα όρια.
Θα μπορούσαμε να mod από 10 και να θέσει το σε θέση πίνακα 1.
Έτσι, αυτό είναι το πώς λειτουργούν ουρές.
Θα πρόκειται πάντα για να πάει από αριστερά προς τα δεξιά και, ενδεχομένως, τυλίξτε γύρω.
Και ξέρετε ότι είναι πλήρους εάν το μέγεθος, το κόκκινο κουτί,
γίνεται ίση με την ικανότητα.
Και έτσι αφού έχουμε προσθέσει 40 έως το ουρά, και τι πρέπει να κάνουμε;
Λοιπόν, το παλαιότερο στοιχείο στην ουρά εξακολουθεί να είναι 19,
έτσι δεν θέλουμε να αλλάξουμε το μπροστινό μέρος της ουράς,
αλλά τώρα έχουμε δύο στοιχεία στην ουρά,
και έτσι θέλουμε να αυξήσουμε μέγεθός μας 1 - 2.
>> Αυτό είναι λίγο πολύ αυτό με σε συνεργασία με σειρά που βασίζεται σε ουρές,
και παρόμοια με στοίβα, υπάρχει επίσης ένας τρόπος
να εφαρμόσει μια ουρά ως συνδεδεμένη λίστα.
Τώρα αν αυτό το είδος δομής δεδομένων φαίνεται γνωστά σε σας, είναι.
Δεν είναι απλά συνδεδεμένη λίστα, είναι μια διπλά συνδεδεμένη λίστα.
Και τώρα, ως ένα μέρος, είναι πράγματι δυνατό να εφαρμοστεί
μια ουρά ως μεμονωμένα συνδεδεμένη λίστα, αλλά Νομίζω ότι από την άποψη της απεικόνισης,
και θα μπορούσε πραγματικά να βοηθήσει να δείτε αυτό ως διπλά συνδεδεμένη λίστα.
Αλλά είναι σίγουρα δυνατό να το κάνουμε αυτό ως μεμονωμένα συνδεδεμένη λίστα.
>> Έτσι, ας ρίξουμε μια ματιά ό, τι αυτό μπορεί να μοιάζει.
Αν θέλουμε να enquue-- έτσι και τώρα, πάλι είμαστε
τη μετάβαση σε μια συνδεδεμένη λίστα με βάση το μοντέλο εδώ.
Αν θέλουμε να Τοποθέτηση στην ουρά, θέλουμε για να προσθέσετε ένα νέο στοιχείο, και
Τι πρέπει να κάνουμε;
Λοιπόν, πρώτα απ 'όλα, επειδή προσθέτουμε στο τέλος
και την αφαίρεση από το αρχίζουν, πιθανότατα
θέλουν να διατηρήσουν τους δείκτες τόσο για την κεφάλι και η ουρά του συνδεδεμένη λίστα;
Ουρά είναι άλλος όρος για το τέλος του συνδεδεμένη λίστα,
το τελευταίο στοιχείο της συνδεδεμένης λίστας.
Και αυτά θα είναι πιθανώς, πάλι, να είναι επωφελής για εμάς
αν είναι καθολικές μεταβλητές.
Αλλά τώρα, αν θέλουμε να προσθέσουμε ένα νέο στοιχείου τι πρέπει να κάνουμε;
Αυτό που μόλις [? malak?] ή δυναμικά διαθέσει νέο κόμβο μας για τους εαυτούς μας.
Και τότε, όπως ακριβώς όταν προσθέσουμε οποιοδήποτε στοιχείο σε μια διπλά συνδεδεμένη λίστα μας,
Απλά πρέπει να ταξινομήσετε of-- αυτά τα τρία τελευταία βήματα εδώ
είναι μόνο τα πάντα για τη μετακίνηση του δείκτες με το σωστό τρόπο
έτσι ώστε το στοιχείο παίρνει προστίθεται σε η αλυσίδα χωρίς σπάσιμο της αλυσίδας
ή να κάνει κάποια λάθος ή έχουν κάποιο είδος του ατυχήματος
σύμφωνα με την οποία θα συμβεί κατά λάθος ορφανά ορισμένα στοιχεία της ουράς μας.
Εδώ είναι ό, τι αυτό μπορεί να μοιάζει.
Θέλουμε να προσθέσετε το στοιχείο 10 στο τέλος αυτής της ουράς.
Έτσι, το παλαιότερο στοιχείο εδώ αντιπροσωπεύεται από το κεφάλι.
Αυτό είναι το πρώτο πράγμα που βάλαμε σε αυτήν την υποθετική ουρά εδώ.
Και ουρά, 13, είναι η πιο πρόσφατα πρόσθετο στοιχείο.
Και έτσι αν θέλουμε να Τοποθέτηση στην ουρά σε 10 Η ουρά αυτή, θέλουμε να το πούμε μετά από 13.
Και έτσι θα πάμε να δυναμικά διατεθεί χώρος για ένα νέο κόμβο
και ελέγξτε για null για να βεβαιωθείτε δεν έχουμε μια βλάβη στη μνήμη.
Στη συνέχεια θα πάμε να τοποθετήστε 10 σε αυτόν τον κόμβο,
και τώρα πρέπει να είμαστε προσεκτικοί σχετικά με το πώς θα οργανώσουμε δείκτες
έτσι ώστε να μην σπάσει η αλυσίδα.
>> Μπορούμε να δημιουργήσει προηγούμενο πεδίο 10 του το σημείο πίσω στην παλιά ουρά,
και επειδή '10 θα είναι η νέα ουρά σε κάποιο σημείο
από τη στιγμή που όλα αυτά τα Οι αλυσίδες συνδέονται,
τίποτα δεν πρόκειται να έρθει μετά από 10 τώρα.
Και έτσι το επόμενο δείκτη του 10 Θα επισημάνω σε null,
και στη συνέχεια, μετά το κάνουμε αυτό, αφού έχουμε 10 συνδέεται προς τα πίσω με την αλυσίδα,
μπορούμε να πάρουμε το παλιό κεφάλι, ή, δικαιολογία μένα, το παλιό ουρά της ουράς.
Το παλιό τέλος της ουράς, 13, και να καταστήσει το σημείο 10.
Και τώρα, σε αυτό το σημείο, έχουμε enqueued τον αριθμό 10 σε αυτήν την ουρά.
Το μόνο που χρειάζεται να κάνουμε τώρα είναι απλά μετακινήστε το ουρά να δείχνουν 10 αντί για 13.
>> Dequeuing είναι στην πραγματικότητα πολύ παρόμοια με το σκάσιμο
από μια στοίβα που είναι υλοποιείται ως συνδεδεμένη λίστα
αν έχετε δει το βίντεο στοίβες.
Το μόνο που χρειάζεται να κάνετε είναι να ξεκινήσετε με το αρχίζει, βρείτε το δεύτερο στοιχείο,
απελευθερώσει το πρώτο στοιχείο, και, στη συνέχεια, μετακινήστε το κεφάλι
στο σημείο με το δεύτερο στοιχείο.
Μάλλον καλύτερα να απεικονίσει ακριβώς για να είναι extra clear γι 'αυτό.
Έτσι, εδώ είναι και πάλι ουρά μας.
12 είναι το παλαιότερο στοιχείο στην ουρά μας, το κεφάλι.
10 είναι το νεότερο στοιχείο στην ουρά μας, την ουρά μας.
>> Και έτσι όταν θέλουμε να dequeue ένα στοιχείο,
θέλουμε να αφαιρέσετε το αρχαιότερο στοιχείο.
Λοιπόν, τι θα κάνουμε;
Καλά θέσαμε ένα δείκτη διάσχιση ότι ξεκινά από το κεφάλι,
και εμείς θα προχωρήσουμε, έτσι ώστε να επισημαίνει το δεύτερο στοιχείο
αυτό queue-- κάτι λέγοντας Trav ισούται trav βέλος δίπλα, για παράδειγμα,
θα κινηθεί Trav εκεί για να επισημάνω 15, το οποίο, αφού dequeue 12,
ή μετά αφαιρούμε 12, θα γίνει ο τότε αρχαιότερο στοιχείο.
>> Τώρα έχουμε μια λαβή για το πρώτο στοιχείο μέσω του δείκτη κεφάλι
και το δεύτερο στοιχείο μέσω του δείκτη trav.
Μπορούμε τώρα δωρεάν το κεφάλι, και τότε μπορούμε να λένε τίποτα δεν έρχεται πριν από 15 πια.
Έτσι, μπορούμε να αλλάξουμε το προηγούμενο 15 δείκτη ώστε να δείχνει σε null,
και εμείς απλά μετακινήστε το πάνω από το κεφάλι.
Και εκεί θα πάμε.
Τώρα έχουμε επιτυχία dequeued 12, και τώρα
έχουν μια άλλη ουρά των 4 στοιχείων.
Αυτό είναι λίγο πολύ όλα Είναι εκεί για να ουρές,
τόσο βασισμένη σε πίνακα και να συνδέεται κατάλογο βάσει.
Είμαι ο Νταγκ Lloyd.
Αυτό είναι το CS 50.