1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Έτσι, αν έχετε
παρακολούθησαν το βίντεο σε στοίβα,

3
00:00:07,370 --> 00:00:09,870
αυτό κατά πάσα πιθανότητα θα αισθάνονται
σαν ένα μικρό κομμάτι του Deja Vu.

4
00:00:09,870 --> 00:00:13,850
Είναι πρόκειται να ένα πολύ παρόμοια ιδέα,
μόνο με μια μικρή συστροφή σε αυτό.

5
00:00:13,850 --> 00:00:15,530
Εμείς πάμε να μιλήσουμε τώρα για ουρές.

6
00:00:15,530 --> 00:00:19,350
Έτσι, μια ουρά, παρόμοια με μια στοίβα,
είναι ένα άλλο είδος δομής δεδομένων

7
00:00:19,350 --> 00:00:22,412
ότι μπορούμε να χρησιμοποιήσουμε για να διατηρήσει
δεδομένα με οργανωμένο τρόπο.

8
00:00:22,412 --> 00:00:24,120
Παρόμοια με μια στοίβα,
αυτό μπορεί να εφαρμοστεί

9
00:00:24,120 --> 00:00:27,000
ως μια σειρά ή μια συνδεδεμένη λίστα.

10
00:00:27,000 --> 00:00:30,320
Σε αντίθεση με μια στοίβα, οι κανόνες
ότι θα χρησιμοποιήσει για να καθορίσει

11
00:00:30,320 --> 00:00:34,210
όταν παίρνουν προστεθούν και να αφαιρεθούν από τα πράγματα
μια ουρά είναι λίγο διαφορετική.

12
00:00:34,210 --> 00:00:36,590
>> Σε αντίθεση με μια στοίβα, η οποία
είναι μια δομή LIFO,

13
00:00:36,590 --> 00:00:45,610
τελευταία in, first out, μια ουρά FIFO είναι
δομή, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Τώρα ουρές, ίσως
έχουν μια αναλογία με ουρές.

15
00:00:49,320 --> 00:00:52,820
Αν έχετε ποτέ στην ουρά
πάρκο ψυχαγωγίας ή σε μια τράπεζα,

16
00:00:52,820 --> 00:00:56,430
υπάρχει ένα είδος επιείκειας
δομή υλοποίησης.

17
00:00:56,430 --> 00:00:59,160
Το πρώτο πρόσωπο στη γραμμή στο
η τράπεζα είναι το πρώτο πρόσωπο

18
00:00:59,160 --> 00:01:00,760
που παίρνει για να μιλήσει με τον αφηγητή.

19
00:01:00,760 --> 00:01:03,522
>> Θα ήταν ένα είδος αγώνα
προς τα κάτω, αν ο μόνος τρόπος

20
00:01:03,522 --> 00:01:06,730
πήρατε να μιλήσετε με τον αφηγητή κατά τη
τράπεζα ήταν το τελευταίο πρόσωπο στη γραμμή.

21
00:01:06,730 --> 00:01:09,146
Όλοι θα θέλουν πάντα
να είναι το τελευταίο πρόσωπο στη γραμμή,

22
00:01:09,146 --> 00:01:12,580
και το πρόσωπο που ήταν εκεί πρώτα
που έχει να περιμένει για λίγο,

23
00:01:12,580 --> 00:01:14,715
θα μπορούσε να είναι εκεί για ώρες,
και ώρες, και ώρες

24
00:01:14,715 --> 00:01:17,590
προτού να έχει την ευκαιρία να πραγματικά
αποσύρουν χρήματα στην τράπεζα.

25
00:01:17,590 --> 00:01:22,510
Και έτσι ουρές είναι το είδος του
αμεροληψία δομή υλοποίησης.

26
00:01:22,510 --> 00:01:25,780
Αλλά αυτό δεν σημαίνει απαραίτητα
ότι στοίβες είναι ένα κακό πράγμα, απλά

27
00:01:25,780 --> 00:01:28,160
ότι οι ουρές είναι ένας άλλος τρόπος για να το κάνουμε.

28
00:01:28,160 --> 00:01:32,420
Έτσι και πάλι η ουρά είναι η πρώτη στην πρώτη
έξω, έναντι μιας στοίβας που διαρκούν σε,

29
00:01:32,420 --> 00:01:34,440
first out.

30
00:01:34,440 --> 00:01:36,190
Παρόμοια με μια στοίβα,
έχουμε δύο πράξεις

31
00:01:36,190 --> 00:01:38,470
ότι μπορούμε να εκτελέσουμε σε ουρές.

32
00:01:38,470 --> 00:01:43,910
Τα ονόματα είναι Τοποθέτηση στην ουρά, η οποία είναι να προσθέσει
ένα νέο στοιχείο με το άκρο της ουράς,

33
00:01:43,910 --> 00:01:47,330
και dequeue, η οποία είναι
για να αφαιρέσετε το παλαιότερο

34
00:01:47,330 --> 00:01:49,670
στοιχείου από το μπροστινό μέρος της ουράς.

35
00:01:49,670 --> 00:01:53,600
Έτσι θα πάμε να προσθέσετε στοιχεία
πάνω στο άκρο της ουράς,

36
00:01:53,600 --> 00:01:57,220
και θα πάμε για να καταργήσετε στοιχεία
από το μπροστινό μέρος της ουράς.

37
00:01:57,220 --> 00:02:00,790
Και πάλι, με τη στοίβα, ήμασταν προσθήκη
στοιχεία στην κορυφή της στοίβας

38
00:02:00,790 --> 00:02:03,380
και την άρση των στοιχείων
από την κορυφή της στοίβας.

39
00:02:03,380 --> 00:02:07,570
Έτσι, με Τοποθέτηση στην ουρά, είναι η προσθήκη σε
το τέλος, αφαιρώντας από το μέτωπο.

40
00:02:07,570 --> 00:02:10,639
Έτσι, το παλαιότερο πράγμα εκεί
είναι πάντα το επόμενο πράγμα

41
00:02:10,639 --> 00:02:13,620
να βγει, αν προσπαθήσουμε
και dequeue κάτι.

42
00:02:13,620 --> 00:02:18,330
>> Έτσι και πάλι, με ουρές, μπορούμε
βασισμένη σε πίνακα εφαρμογών

43
00:02:18,330 --> 00:02:20,110
και συνδέεται κατάλογο βάσει εφαρμογές.

44
00:02:20,110 --> 00:02:24,620
Θα ξεκινήσουμε πάλι με
array-based υλοποιήσεις.

45
00:02:24,620 --> 00:02:27,070
Ο ορισμός δομή
φαίνεται αρκετά παρόμοια.

46
00:02:27,070 --> 00:02:30,720
Έχουμε μια άλλη σειρά
υπάρχει αξίας τύπο δεδομένων,

47
00:02:30,720 --> 00:02:32,690
έτσι ώστε να μπορεί να κρατήσει αυθαίρετα τύπους δεδομένων.

48
00:02:32,690 --> 00:02:35,570
Είμαστε και πάλι πρόκειται να χρησιμοποιήσετε
ακέραιοι σε αυτό το παράδειγμα.

49
00:02:35,570 --> 00:02:39,830
>> Και ακριβώς όπως με μας
βασισμένη σε πίνακα υλοποίηση στοίβας,

50
00:02:39,830 --> 00:02:42,340
επειδή είμαστε χρησιμοποιώντας ένα
σειρά, αναγκαστικά θα

51
00:02:42,340 --> 00:02:46,850
έχουν αυτό το περιορισμό ότι το είδος C
της επιβάλλει σε μας, το οποίο είναι εμείς

52
00:02:46,850 --> 00:02:51,670
δεν έχουν το δυναμισμό μας
ικανότητα να αναπτύσσονται και να συρρικνωθεί το φάσμα.

53
00:02:51,670 --> 00:02:55,710
Πρέπει να αποφασίσουμε στην αρχή
τι είναι ο μέγιστος αριθμός των πραγμάτων

54
00:02:55,710 --> 00:02:59,300
ότι μπορούμε να βάλουμε σε αυτό
ουρά, και σε αυτή την περίπτωση,

55
00:02:59,300 --> 00:03:02,070
ικανότητας θα ήταν κάποια λίβρα
ορίζεται σταθερά στον κώδικά μας.

56
00:03:02,070 --> 00:03:05,430
Και για τους σκοπούς του παρόντος
βίντεο, χωρητικότητα θα είναι 10.

57
00:03:05,430 --> 00:03:07,690
>> Πρέπει να παρακολουθείτε
το μπροστινό της ουράς

58
00:03:07,690 --> 00:03:11,160
έτσι ώστε να γνωρίζουν ποιο είναι το στοιχείο
θέλουμε να dequeue,

59
00:03:11,160 --> 00:03:15,070
και θα πρέπει επίσης να παρακολουθείτε
κάτι else-- τον αριθμό των στοιχείων

60
00:03:15,070 --> 00:03:16,690
ότι έχουμε στην ουρά μας.

61
00:03:16,690 --> 00:03:19,360
Παρατηρήστε δεν είμαστε παρακολούθηση
από το τέλος της ουράς, μόλις

62
00:03:19,360 --> 00:03:21,150
το μέγεθος της ουράς.

63
00:03:21,150 --> 00:03:24,310
Και ο λόγος γι 'αυτό ελπίζουμε ότι θα
γίνει λίγο πιο σαφής σε μια στιγμή.

64
00:03:24,310 --> 00:03:26,143
Μόλις έχουμε ολοκληρώσει
Ο ορισμός αυτός ο τύπος,

65
00:03:26,143 --> 00:03:29,080
έχουμε ένα νέο τύπο δεδομένων
που ονομάζεται ουρά, το οποίο μπορούμε τώρα

66
00:03:29,080 --> 00:03:30,630
δηλώνουν τις μεταβλητές αυτού του τύπου δεδομένων.

67
00:03:30,630 --> 00:03:35,350
Και κάπως συγκεχυμένα, έχω αποφασίσει
για να καλέσετε αυτήν την ουρά q, η επιστολή

68
00:03:35,350 --> 00:03:38,090
q αντί του τύπου δεδομένων q.

69
00:03:38,090 --> 00:03:39,600
>> Τόσο εδώ είναι η ουρά μας.

70
00:03:39,600 --> 00:03:40,700
Είναι μια δομή.

71
00:03:40,700 --> 00:03:45,730
Περιέχει τρία μέλη ή τρεις
πεδία, ένας πίνακας μεγέθους χωρητικότητας.

72
00:03:45,730 --> 00:03:47,340
Σε αυτή την περίπτωση, η ικανότητα είναι 10.

73
00:03:47,340 --> 00:03:49,580
Και αυτή η συστοιχία είναι
πρόκειται να κρατήσει ακέραιοι.

74
00:03:49,580 --> 00:03:55,240
Στο πράσινο είναι η ουρά μπροστά από μας, η
επόμενο στοιχείο να αφαιρεθεί, και το κόκκινο

75
00:03:55,240 --> 00:03:58,610
θα είναι το μέγεθος της ουράς,
πόσα στοιχεία είναι σήμερα

76
00:03:58,610 --> 00:04:01,190
υπάρχοντα στην ουρά.

77
00:04:01,190 --> 00:04:05,300
Έτσι, αν πούμε q.front ίσων
0, και το μέγεθος q.size ισούται 0--

78
00:04:05,300 --> 00:04:07,120
βάζουμε 0s σε αυτούς τους τομείς.

79
00:04:07,120 --> 00:04:11,070
Και σε αυτό το σημείο, είμαστε λίγο πολύ
έτοιμα να αρχίσουν να εργάζονται με ουρά μας.

80
00:04:11,070 --> 00:04:14,140
>> Έτσι, η πρώτη πράξη μπορούμε
εκτελέσει είναι να Τοποθέτηση στην ουρά κάτι,

81
00:04:14,140 --> 00:04:16,860
για να προσθέσετε ένα νέο στοιχείο στο
το άκρο της ουράς.

82
00:04:16,860 --> 00:04:19,089
Λοιπόν, τι χρειαζόμαστε για να
κάνει στη γενική περίπτωση;

83
00:04:19,089 --> 00:04:23,690
Λοιπόν αυτή η λειτουργία Τοποθέτηση στην ουρά ανάγκες
να αποδεχθεί ένα δείκτη για την ουρά μας.

84
00:04:23,690 --> 00:04:26,370
Και πάλι, αν είχαμε δηλώσει
ουρά μας σε παγκόσμιο επίπεδο,

85
00:04:26,370 --> 00:04:29,490
δεν θα χρειαστεί να το κάνετε αυτό
απαραίτητα, αλλά σε γενικές γραμμές, μπορούμε

86
00:04:29,490 --> 00:04:32,330
Πρέπει να αποδεχτείτε τους δείκτες
σε δομές δεδομένων

87
00:04:32,330 --> 00:04:35,040
όπως αυτό, διότι διαφορετικά,
είμαστε περνώντας από value-- είμαστε

88
00:04:35,040 --> 00:04:38,140
περνώντας σε αντίγραφα της ουράς,
και έτσι δεν είμαστε πραγματικά αλλάζει

89
00:04:38,140 --> 00:04:41,050
η ουρά που θέλουμε να αλλάξουμε.

90
00:04:41,050 --> 00:04:44,860
>> Το άλλο πράγμα που πρέπει να κάνει είναι να αποδεχθεί
ένα στοιχείο δεδομένων του κατάλληλου τύπου.

91
00:04:44,860 --> 00:04:46,818
Και πάλι, σε αυτή την περίπτωση, είναι
πρόκειται να είναι ακέραιοι,

92
00:04:46,818 --> 00:04:49,330
αλλά θα μπορούσε αυθαίρετα
δηλώνει το είδος των δεδομένων ως τιμή

93
00:04:49,330 --> 00:04:51,160
και να χρησιμοποιήσετε αυτό γενικότερα.

94
00:04:51,160 --> 00:04:56,030
Αυτό είναι το στοιχείο που θέλουμε να Τοποθέτηση στην ουρά,
θέλουμε να προσθέσουμε στο τέλος της ουράς.

95
00:04:56,030 --> 00:04:58,573
Στη συνέχεια, θέλουμε πραγματικά να
τοποθετήστε τα δεδομένα στην ουρά.

96
00:04:58,573 --> 00:05:01,490
Σε αυτήν την περίπτωση, η τοποθέτηση σε
σωστή θέση του πίνακα μας,

97
00:05:01,490 --> 00:05:05,040
και, στη συνέχεια, θέλουμε να αλλάξουμε το μέγεθος
της ουράς, πόσα στοιχεία μας

98
00:05:05,040 --> 00:05:07,050
Αυτήν τη στιγμή έχετε.

99
00:05:07,050 --> 00:05:07,990
>> Οπότε ας ξεκινήσουμε.

100
00:05:07,990 --> 00:05:10,890
Εδώ είναι, και πάλι, ότι η γενική
Δήλωση λειτουργία μορφή

101
00:05:10,890 --> 00:05:13,980
Τοποθέτηση στην ουρά για το τι μπορεί να μοιάζει.

102
00:05:13,980 --> 00:05:14,910
Και εδώ πηγαίνουμε.

103
00:05:14,910 --> 00:05:18,335
Ας Τοποθέτηση στην ουρά του αριθμού
28 στην ουρά.

104
00:05:18,335 --> 00:05:19,460
Λοιπόν, τι θα κάνουμε;

105
00:05:19,460 --> 00:05:23,390
Λοιπόν, η ουρά μπροστά μας είναι
στο μηδέν, και το μέγεθος της ουράς μας

106
00:05:23,390 --> 00:05:29,680
είναι στο 0, και έτσι πιθανόν να θέλετε να βάλετε
ο αριθμός 28 στην συστοιχία του αριθμού στοιχείου

107
00:05:29,680 --> 00:05:31,124
0, σωστά;

108
00:05:31,124 --> 00:05:32,540
Έτσι έχουμε τώρα τοποθετείται ότι εκεί μέσα.

109
00:05:32,540 --> 00:05:34,820
Έτσι, τώρα τι πρέπει να αλλάξουμε;

110
00:05:34,820 --> 00:05:37,090
Δεν θέλουμε να αλλάξουμε
το μπροστινό μέρος της ουράς,

111
00:05:37,090 --> 00:05:40,850
επειδή θέλουμε να γνωρίζουμε τι στοιχείο
μπορεί να χρειαστεί να dequeue αργότερα.

112
00:05:40,850 --> 00:05:44,020
Έτσι, ο λόγος που έχουμε μπροστά εκεί
Είναι το είδος του δείκτη για το τι είναι

113
00:05:44,020 --> 00:05:46,439
το παλαιότερο πράγμα στον πίνακα.

114
00:05:46,439 --> 00:05:49,730
Καλά το παλαιότερο πράγμα στον array-- σε
Πράγματι, το μόνο πράγμα στον πίνακα δεξιά

115
00:05:49,730 --> 00:05:53,540
now-- είναι 28, η οποία είναι
σε θέση πίνακα 0.

116
00:05:53,540 --> 00:05:56,160
Γι 'αυτό και δεν θέλουμε να
αλλάξετε ότι το πράσινο αριθμό,

117
00:05:56,160 --> 00:05:57,910
γιατί αυτό είναι το παλαιότερο στοιχείο.

118
00:05:57,910 --> 00:06:00,510
Αντίθετα, θέλουμε να αλλάξουμε το μέγεθος.

119
00:06:00,510 --> 00:06:04,110
Έτσι, σε αυτή την περίπτωση, θα
αυξήσετε το μέγεθος σε 1.

120
00:06:04,110 --> 00:06:08,430
>> Τώρα, μια γενική ιδέα για το είδος του, όπου η
επόμενο στοιχείο πρόκειται να πάει σε μια ουρά

121
00:06:08,430 --> 00:06:12,310
είναι να προσθέσετε αυτούς τους δύο αριθμούς
μαζί, εμπρός και το μέγεθος,

122
00:06:12,310 --> 00:06:16,390
και ότι θα σας πω, όπου το επόμενο
στοιχείου στην ουρά πρόκειται να πάει.

123
00:06:16,390 --> 00:06:18,130
Έτσι τώρα ας Τοποθέτηση στην ουρά έναν άλλο αριθμό.

124
00:06:18,130 --> 00:06:20,250
Ας Τοποθέτηση στην ουρά 33.

125
00:06:20,250 --> 00:06:24,480
Έτσι, 33 πρόκειται να πάει σε
θέση πίνακα 0 και 1.

126
00:06:24,480 --> 00:06:26,840
Έτσι, στην περίπτωση αυτή, πρόκειται
να μπω σε θέση πίνακα 1,

127
00:06:26,840 --> 00:06:29,500
και τώρα το μέγεθος της ουράς μας είναι 2.

128
00:06:29,500 --> 00:06:31,840
>> Και πάλι, δεν είμαστε αλλαγή
η ουρά μπροστά από μας,

129
00:06:31,840 --> 00:06:34,730
28 επειδή εξακολουθεί να είναι η
αρχαιότερο στοιχείο, και εμείς

130
00:06:34,730 --> 00:06:38,220
Θέλετε to-- όταν τελικά πάρει
να dequeuing, απομακρύνοντας στοιχεία

131
00:06:38,220 --> 00:06:43,300
από αυτήν την ουρά, θέλουμε να γνωρίζουμε
όπου το παλαιότερο στοιχείο είναι.

132
00:06:43,300 --> 00:06:48,620
Και γι 'αυτό πρέπει πάντα να διατηρήσουν
κάποια ένδειξη για το πού είναι αυτό.

133
00:06:48,620 --> 00:06:50,410
Έτσι, αυτό είναι ό, τι το 0 είναι εκεί για.

134
00:06:50,410 --> 00:06:52,910
Αυτό είναι ό, τι υπάρχει μπροστά για.

135
00:06:52,910 --> 00:06:55,022
>> Ας Τοποθέτηση στην ουρά σε ένα ακόμη στοιχείο, 19.

136
00:06:55,022 --> 00:06:56,980
Είμαι βέβαιος ότι μπορείτε να μαντέψετε
όπου 19 πρόκειται να πάει.

137
00:06:56,980 --> 00:06:59,860
Δεν πρόκειται να μπω σε
συστοιχία αριθμός θέσης 2.

138
00:06:59,860 --> 00:07:01,570
Αυτό είναι 0 συν 2.

139
00:07:01,570 --> 00:07:03,199
Και τώρα το μέγεθος της ουράς μας είναι 3.

140
00:07:03,199 --> 00:07:04,240
Έχουμε 3 στοιχεία σε αυτό.

141
00:07:04,240 --> 00:07:08,490
Έτσι, αν ήμασταν σε αυτά, και εμείς δεν πρόκειται
προς τα δεξιά τώρα, Τοποθέτηση στην ουρά και ένα άλλο στοιχείο,

142
00:07:08,490 --> 00:07:11,370
θα μπω σε θέση πίνακα
αριθμός 3, και το μέγεθος της ουράς μας

143
00:07:11,370 --> 00:07:13,160
θα είναι 4.

144
00:07:13,160 --> 00:07:15,279
Έτσι έχουμε αρκετά στοιχεία enqueued τώρα.

145
00:07:15,279 --> 00:07:16,570
Ας αρχίσουμε να τα αφαιρέσετε.

146
00:07:16,570 --> 00:07:19,450
Ας τους dequeue από την ουρά.

147
00:07:19,450 --> 00:07:23,340
>> Έτσι, παρόμοια με ποπ, η οποία είναι είδος
του αναλόγου αυτού για τις στοίβες,

148
00:07:23,340 --> 00:07:26,180
dequeue πρέπει να δεχτεί μια
δείκτη στο queue-- και πάλι,

149
00:07:26,180 --> 00:07:28,140
εάν δεν έχει δηλωθεί σε παγκόσμιο επίπεδο.

150
00:07:28,140 --> 00:07:31,610
Τώρα θέλουμε να αλλάξουμε την τοποθεσία
του στο μπροστινό μέρος της ουράς.

151
00:07:31,610 --> 00:07:35,050
Αυτό είναι όπου το είδος του έρχεται
στο παιχνίδι, ότι μπροστά μεταβλητή,

152
00:07:35,050 --> 00:07:37,310
γιατί όταν θα αφαιρέσει
ένα στοιχείο, που θέλουμε

153
00:07:37,310 --> 00:07:40,720
για να προχωρήσουμε στο επόμενο αρχαιότερο στοιχείο.

154
00:07:40,720 --> 00:07:44,180
>> Στη συνέχεια, θέλουμε να μειωθεί
το μέγεθος της ουράς,

155
00:07:44,180 --> 00:07:47,130
και, στη συνέχεια, θέλουμε να επιστρέψουμε την τιμή
ότι αφαιρέθηκε από την ουρά.

156
00:07:47,130 --> 00:07:48,921
Και πάλι, δεν θέλουμε να το απορρίψει μόνο.

157
00:07:48,921 --> 00:07:51,170
Είμαστε πιθανώς τα εξόρυξη
το από το queue-- είμαστε

158
00:07:51,170 --> 00:07:54,170
dequeuing επειδή νοιαζόμαστε γι 'αυτό.

159
00:07:54,170 --> 00:08:01,080
Έτσι θέλουμε αυτή τη λειτουργία για να επιστρέψει
ένα στοιχείο δεδομένων της αξίας του τύπου.

160
00:08:01,080 --> 00:08:04,360
Και πάλι, στην περίπτωση αυτή, η τιμή είναι ακέραιος.

161
00:08:04,360 --> 00:08:05,670
>> Έτσι τώρα ας dequeue κάτι.

162
00:08:05,670 --> 00:08:09,310
Ας αφαιρέσετε ένα στοιχείο από την ουρά.

163
00:08:09,310 --> 00:08:15,970
Αν πούμε int x ισούται & Q, σύμβολο q--
και πάλι ότι είναι ένας δείκτης σε αυτά τα δεδομένα q

164
00:08:15,970 --> 00:08:20,177
structure-- ποιο στοιχείο
πρόκειται να dequeued;

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
Σε αυτή την περίπτωση, επειδή αυτό είναι ένα πρώτο
in, first out δομή δεδομένων, FIFO,

167
00:08:29,480 --> 00:08:33,690
το πρώτο πράγμα που βάζουμε σε αυτό
ουρά ήταν 28, και στην προκειμένη περίπτωση,

168
00:08:33,690 --> 00:08:37,245
θα πάμε για να πάρει 28 από
η ουρά, δεν 19, το οποίο είναι αυτό

169
00:08:37,245 --> 00:08:38,870
θα κάναμε αν αυτό ήταν μια στοίβα.

170
00:08:38,870 --> 00:08:42,220
Εμείς πάμε για να πάρει 28 από την ουρά.

171
00:08:42,220 --> 00:08:44,960
>> Παρόμοια με αυτό που κάναμε με
μια στοίβα, δεν είμαστε στην πραγματικότητα

172
00:08:44,960 --> 00:08:47,345
πρόκειται να διαγράψει 28
από την ίδια την ουρά,

173
00:08:47,345 --> 00:08:49,470
είμαστε ακριβώς πρόκειται να είδος
της προσποιούμαστε ότι δεν υπάρχει.

174
00:08:49,470 --> 00:08:51,678
Έτσι πρόκειται να μείνει εκεί
στη μνήμη, αλλά είμαστε μόνο

175
00:08:51,678 --> 00:08:57,820
πρόκειται να το είδος του να αγνοήσει κινώντας
οι άλλοι δύο πεδία δεδομένων q μας

176
00:08:57,820 --> 00:08:58,830
δομή.

177
00:08:58,830 --> 00:09:00,230
Εμείς πάμε για να αλλάξει το μέτωπο.

178
00:09:00,230 --> 00:09:04,290
Q.front τώρα πρόκειται να
είναι 1, γιατί αυτό είναι τώρα

179
00:09:04,290 --> 00:09:07,740
το παλαιότερο στοιχείο που έχουμε σε μας
ουρά, γιατί έχουμε ήδη αφαιρέσει 28,

180
00:09:07,740 --> 00:09:10,460
ο οποίος ήταν ο πρώην αρχαιότερο στοιχείο.

181
00:09:10,460 --> 00:09:13,540
>> Και τώρα, θέλουμε να αλλάξουμε
το μέγεθος της ουράς

182
00:09:13,540 --> 00:09:15,780
σε δύο στοιχεία αντί για τρεις.

183
00:09:15,780 --> 00:09:20,450
Τώρα θυμάμαι είπα νωρίτερα, όταν
θέλετε να προσθέσετε στοιχεία στην ουρά,

184
00:09:20,450 --> 00:09:26,000
το βάζουμε σε μία θέση πίνακα
που είναι το άθροισμα των εμπρόσθιων και μεγέθους.

185
00:09:26,000 --> 00:09:29,050
Έτσι, σε αυτή την περίπτωση, είμαστε ακόμα βάζοντας
αυτό, το επόμενο στοιχείο στην ουρά,

186
00:09:29,050 --> 00:09:33,360
σε θέση πίνακα 3, και
θα δούμε ότι σε ένα δευτερόλεπτο.

187
00:09:33,360 --> 00:09:35,730
>> Έτσι έχουμε τώρα dequeued μας
πρώτο στοιχείο από την ουρά.

188
00:09:35,730 --> 00:09:36,480
Ας το κάνουμε ξανά.

189
00:09:36,480 --> 00:09:38,696
Ας αφαιρέσει ένα άλλο
στοιχείο από την ουρά.

190
00:09:38,696 --> 00:09:42,400
Στην περίπτωση αυτή, η τρέχουσα παλαιότερα
στοιχείο είναι η τοποθεσία πίνακα 1.

191
00:09:42,400 --> 00:09:44,220
Αυτό είναι ό, τι q.front μας λέει.

192
00:09:44,220 --> 00:09:46,980
Αυτό το πράσινο κουτί μας λέει ότι
ότι είναι το παλαιότερο στοιχείο.

193
00:09:46,980 --> 00:09:49,310
Και έτσι, θα καταστεί x 33.

194
00:09:49,310 --> 00:09:52,130
Θα ακριβώς το είδος του ξεχάσω
ότι υπάρχει 33 στη συστοιχία,

195
00:09:52,130 --> 00:09:55,100
και θα πω ότι τώρα, η
νέα αρχαιότερο στοιχείο στην ουρά

196
00:09:55,100 --> 00:09:58,900
είναι στη θέση πίνακα 2, και το μέγεθος του
της ουράς, ο αριθμός των στοιχείων

197
00:09:58,900 --> 00:10:02,152
έχουμε στην ουρά, είναι 1.

198
00:10:02,152 --> 00:10:05,110
Τώρα ας Τοποθέτηση στην ουρά κάτι, και εγώ
είδος της έδωσε αυτό μακριά πριν από ένα δευτερόλεπτο,

199
00:10:05,110 --> 00:10:10,340
αλλά αν θέλουμε να θέσει σε 40 η
ουρά, όπου είναι 40 πρόκειται να πάει;

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Λοιπόν έχουμε θέτοντάς
στην ουρά q.front συν μέγεθος,

202
00:10:17,730 --> 00:10:20,850
και έτσι είναι λογικό να
πραγματικά να βάλει 40 εδώ.

203
00:10:20,850 --> 00:10:22,840
Τώρα παρατηρούμε ότι σε
κάποια στιγμή, θα πάμε

204
00:10:22,840 --> 00:10:27,980
για να φτάσετε στο τέλος της
σειρά μας εντός του q,

205
00:10:27,980 --> 00:10:32,010
αλλά ότι έσβησε 28 και 33--
από όπου και αν στην πραγματικότητα, τεχνικά

206
00:10:32,010 --> 00:10:33,300
ανοιχτούς χώρους, έτσι δεν είναι;

207
00:10:33,300 --> 00:10:36,040
Και έτσι, μπορούμε να eventually--
ο κανόνας της προσθήκης

208
00:10:36,040 --> 00:10:40,390
αυτά τα δύο μπορεί τελικά together-- μας
Πρέπει να mod από το μέγεθος της ικανότητας

209
00:10:40,390 --> 00:10:41,410
έτσι ώστε να μπορεί να τυλιχτεί γύρω.

210
00:10:41,410 --> 00:10:43,620
>> Έτσι, αν έχουμε την ευκαιρία να στοιχείου
αριθμός 10, αν είμαστε

211
00:10:43,620 --> 00:10:48,790
αντικαθιστώντας το στοιχείο του αριθμού 10, είχαμε
πραγματικά να το θέσω σε θέση πίνακα 0.

212
00:10:48,790 --> 00:10:50,997
Και αν επρόκειτο να
συστοιχία location-- Με συγχωρείτε,

213
00:10:50,997 --> 00:10:53,080
αν θέλουμε να προστίθενται μαζί,
και πήραμε τον αριθμό

214
00:10:53,080 --> 00:10:56,330
11 θα είναι όταν θα πρέπει να θέσει
αυτό, το οποίο δεν υπάρχει σε αυτό το array--

215
00:10:56,330 --> 00:10:58,200
θα πρέπει να βγείτε έξω από τα όρια.

216
00:10:58,200 --> 00:11:03,367
Θα μπορούσαμε να mod από 10 και να θέσει
το σε θέση πίνακα 1.

217
00:11:03,367 --> 00:11:04,450
Έτσι, αυτό είναι το πώς λειτουργούν ουρές.

218
00:11:04,450 --> 00:11:08,540
Θα πρόκειται πάντα για να πάει από αριστερά
προς τα δεξιά και, ενδεχομένως, τυλίξτε γύρω.

219
00:11:08,540 --> 00:11:11,280
Και ξέρετε ότι είναι
πλήρους εάν το μέγεθος, το κόκκινο κουτί,

220
00:11:11,280 --> 00:11:13,710
γίνεται ίση με την ικανότητα.

221
00:11:13,710 --> 00:11:16,720
Και έτσι αφού έχουμε προσθέσει 40 έως το
ουρά, και τι πρέπει να κάνουμε;

222
00:11:16,720 --> 00:11:19,890
Λοιπόν, το παλαιότερο στοιχείο
στην ουρά εξακολουθεί να είναι 19,

223
00:11:19,890 --> 00:11:21,990
έτσι δεν θέλουμε να αλλάξουμε
το μπροστινό μέρος της ουράς,

224
00:11:21,990 --> 00:11:23,820
αλλά τώρα έχουμε δύο
στοιχεία στην ουρά,

225
00:11:23,820 --> 00:11:28,710
και έτσι θέλουμε να αυξήσουμε
μέγεθός μας 1 - 2.

226
00:11:28,710 --> 00:11:31,820
>> Αυτό είναι λίγο πολύ αυτό με
σε συνεργασία με σειρά που βασίζεται σε ουρές,

227
00:11:31,820 --> 00:11:33,630
και παρόμοια με στοίβα,
υπάρχει επίσης ένας τρόπος

228
00:11:33,630 --> 00:11:36,450
να εφαρμόσει μια ουρά ως συνδεδεμένη λίστα.

229
00:11:36,450 --> 00:11:40,150
Τώρα αν αυτό το είδος δομής δεδομένων
φαίνεται γνωστά σε σας, είναι.

230
00:11:40,150 --> 00:11:43,780
Δεν είναι απλά συνδεδεμένη λίστα,
είναι μια διπλά συνδεδεμένη λίστα.

231
00:11:43,780 --> 00:11:46,790
Και τώρα, ως ένα μέρος, είναι
πράγματι δυνατό να εφαρμοστεί

232
00:11:46,790 --> 00:11:50,160
μια ουρά ως μεμονωμένα συνδεδεμένη λίστα, αλλά
Νομίζω ότι από την άποψη της απεικόνισης,

233
00:11:50,160 --> 00:11:53,350
και θα μπορούσε πραγματικά να βοηθήσει να δείτε
αυτό ως διπλά συνδεδεμένη λίστα.

234
00:11:53,350 --> 00:11:56,850
Αλλά είναι σίγουρα δυνατό να
το κάνουμε αυτό ως μεμονωμένα συνδεδεμένη λίστα.

235
00:11:56,850 --> 00:12:00,110
>> Έτσι, ας ρίξουμε μια ματιά
ό, τι αυτό μπορεί να μοιάζει.

236
00:12:00,110 --> 00:12:02,750
Αν θέλουμε να enquue--
έτσι και τώρα, πάλι είμαστε

237
00:12:02,750 --> 00:12:05,360
τη μετάβαση σε μια συνδεδεμένη λίστα
με βάση το μοντέλο εδώ.

238
00:12:05,360 --> 00:12:08,420
Αν θέλουμε να Τοποθέτηση στην ουρά, θέλουμε
για να προσθέσετε ένα νέο στοιχείο, και

239
00:12:08,420 --> 00:12:09,730
Τι πρέπει να κάνουμε;

240
00:12:09,730 --> 00:12:12,770
Λοιπόν, πρώτα απ 'όλα, επειδή
προσθέτουμε στο τέλος

241
00:12:12,770 --> 00:12:15,520
και την αφαίρεση από το
αρχίζουν, πιθανότατα

242
00:12:15,520 --> 00:12:20,050
θέλουν να διατηρήσουν τους δείκτες τόσο για την
κεφάλι και η ουρά του συνδεδεμένη λίστα;

243
00:12:20,050 --> 00:12:22,660
Ουρά είναι άλλος όρος για
το τέλος του συνδεδεμένη λίστα,

244
00:12:22,660 --> 00:12:24,496
το τελευταίο στοιχείο της συνδεδεμένης λίστας.

245
00:12:24,496 --> 00:12:26,620
Και αυτά θα είναι πιθανώς,
πάλι, να είναι επωφελής για εμάς

246
00:12:26,620 --> 00:12:28,477
αν είναι καθολικές μεταβλητές.

247
00:12:28,477 --> 00:12:31,060
Αλλά τώρα, αν θέλουμε να προσθέσουμε ένα νέο
στοιχείου τι πρέπει να κάνουμε;

248
00:12:31,060 --> 00:12:35,262
Αυτό που μόλις [? malak?] ή δυναμικά
διαθέσει νέο κόμβο μας για τους εαυτούς μας.

249
00:12:35,262 --> 00:12:38,220
Και τότε, όπως ακριβώς όταν προσθέσουμε οποιοδήποτε
στοιχείο σε μια διπλά συνδεδεμένη λίστα μας,

250
00:12:38,220 --> 00:12:40,410
Απλά πρέπει να ταξινομήσετε of--
αυτά τα τρία τελευταία βήματα εδώ

251
00:12:40,410 --> 00:12:43,330
είναι μόνο τα πάντα για τη μετακίνηση του
δείκτες με το σωστό τρόπο

252
00:12:43,330 --> 00:12:46,710
έτσι ώστε το στοιχείο παίρνει προστίθεται σε
η αλυσίδα χωρίς σπάσιμο της αλυσίδας

253
00:12:46,710 --> 00:12:49,580
ή να κάνει κάποια λάθος
ή έχουν κάποιο είδος του ατυχήματος

254
00:12:49,580 --> 00:12:54,505
σύμφωνα με την οποία θα συμβεί κατά λάθος
ορφανά ορισμένα στοιχεία της ουράς μας.

255
00:12:54,505 --> 00:12:55,880
Εδώ είναι ό, τι αυτό μπορεί να μοιάζει.

256
00:12:55,880 --> 00:13:00,980
Θέλουμε να προσθέσετε το στοιχείο
10 στο τέλος αυτής της ουράς.

257
00:13:00,980 --> 00:13:03,380
Έτσι, το παλαιότερο στοιχείο εδώ
αντιπροσωπεύεται από το κεφάλι.

258
00:13:03,380 --> 00:13:06,800
Αυτό είναι το πρώτο πράγμα που βάλαμε
σε αυτήν την υποθετική ουρά εδώ.

259
00:13:06,800 --> 00:13:10,430
Και ουρά, 13, είναι η πιο
πρόσφατα πρόσθετο στοιχείο.

260
00:13:10,430 --> 00:13:17,030
Και έτσι αν θέλουμε να Τοποθέτηση στην ουρά σε 10
Η ουρά αυτή, θέλουμε να το πούμε μετά από 13.

261
00:13:17,030 --> 00:13:19,860
Και έτσι θα πάμε να δυναμικά
διατεθεί χώρος για ένα νέο κόμβο

262
00:13:19,860 --> 00:13:23,280
και ελέγξτε για null για να βεβαιωθείτε
δεν έχουμε μια βλάβη στη μνήμη.

263
00:13:23,280 --> 00:13:27,040
Στη συνέχεια θα πάμε να
τοποθετήστε 10 σε αυτόν τον κόμβο,

264
00:13:27,040 --> 00:13:30,030
και τώρα πρέπει να είμαστε προσεκτικοί
σχετικά με το πώς θα οργανώσουμε δείκτες

265
00:13:30,030 --> 00:13:32,180
έτσι ώστε να μην σπάσει η αλυσίδα.

266
00:13:32,180 --> 00:13:38,910
>> Μπορούμε να δημιουργήσει προηγούμενο πεδίο 10 του
το σημείο πίσω στην παλιά ουρά,

267
00:13:38,910 --> 00:13:41,620
και επειδή '10 θα είναι η
νέα ουρά σε κάποιο σημείο

268
00:13:41,620 --> 00:13:44,459
από τη στιγμή που όλα αυτά τα
Οι αλυσίδες συνδέονται,

269
00:13:44,459 --> 00:13:46,250
τίποτα δεν πρόκειται να έρθει
μετά από 10 τώρα.

270
00:13:46,250 --> 00:13:49,880
Και έτσι το επόμενο δείκτη του 10
Θα επισημάνω σε null,

271
00:13:49,880 --> 00:13:53,580
και στη συνέχεια, μετά το κάνουμε αυτό, αφού έχουμε
10 συνδέεται προς τα πίσω με την αλυσίδα,

272
00:13:53,580 --> 00:13:57,780
μπορούμε να πάρουμε το παλιό κεφάλι, ή, δικαιολογία
μένα, το παλιό ουρά της ουράς.

273
00:13:57,780 --> 00:14:02,980
Το παλιό τέλος της ουράς,
13, και να καταστήσει το σημείο 10.

274
00:14:02,980 --> 00:14:08,220
Και τώρα, σε αυτό το σημείο, έχουμε
enqueued τον αριθμό 10 σε αυτήν την ουρά.

275
00:14:08,220 --> 00:14:14,740
Το μόνο που χρειάζεται να κάνουμε τώρα είναι απλά μετακινήστε το
ουρά να δείχνουν 10 αντί για 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing είναι στην πραγματικότητα
πολύ παρόμοια με το σκάσιμο

277
00:14:17,630 --> 00:14:21,710
από μια στοίβα που είναι
υλοποιείται ως συνδεδεμένη λίστα

278
00:14:21,710 --> 00:14:24,040
αν έχετε δει το βίντεο στοίβες.

279
00:14:24,040 --> 00:14:27,280
Το μόνο που χρειάζεται να κάνετε είναι να ξεκινήσετε με το
αρχίζει, βρείτε το δεύτερο στοιχείο,

280
00:14:27,280 --> 00:14:30,480
απελευθερώσει το πρώτο στοιχείο,
και, στη συνέχεια, μετακινήστε το κεφάλι

281
00:14:30,480 --> 00:14:32,930
στο σημείο με το δεύτερο στοιχείο.

282
00:14:32,930 --> 00:14:37,920
Μάλλον καλύτερα να απεικονίσει
ακριβώς για να είναι extra clear γι 'αυτό.

283
00:14:37,920 --> 00:14:39,230
Έτσι, εδώ είναι και πάλι ουρά μας.

284
00:14:39,230 --> 00:14:42,600
12 είναι το παλαιότερο στοιχείο
στην ουρά μας, το κεφάλι.

285
00:14:42,600 --> 00:14:46,210
10 είναι το νεότερο στοιχείο
στην ουρά μας, την ουρά μας.

286
00:14:46,210 --> 00:14:49,310
>> Και έτσι όταν θέλουμε
να dequeue ένα στοιχείο,

287
00:14:49,310 --> 00:14:52,202
θέλουμε να αφαιρέσετε το αρχαιότερο στοιχείο.

288
00:14:52,202 --> 00:14:52,910
Λοιπόν, τι θα κάνουμε;

289
00:14:52,910 --> 00:14:55,243
Καλά θέσαμε ένα δείκτη διάσχιση
ότι ξεκινά από το κεφάλι,

290
00:14:55,243 --> 00:14:57,840
και εμείς θα προχωρήσουμε, έτσι ώστε να
επισημαίνει το δεύτερο στοιχείο

291
00:14:57,840 --> 00:15:02,290
αυτό queue-- κάτι λέγοντας Trav
ισούται trav βέλος δίπλα, για παράδειγμα,

292
00:15:02,290 --> 00:15:07,170
θα κινηθεί Trav εκεί για να επισημάνω
15, το οποίο, αφού dequeue 12,

293
00:15:07,170 --> 00:15:13,030
ή μετά αφαιρούμε 12, θα
γίνει ο τότε αρχαιότερο στοιχείο.

294
00:15:13,030 --> 00:15:16,360
>> Τώρα έχουμε μια λαβή για το πρώτο
στοιχείο μέσω του δείκτη κεφάλι

295
00:15:16,360 --> 00:15:19,440
και το δεύτερο στοιχείο
μέσω του δείκτη trav.

296
00:15:19,440 --> 00:15:25,170
Μπορούμε τώρα δωρεάν το κεφάλι, και τότε μπορούμε να
λένε τίποτα δεν έρχεται πριν από 15 πια.

297
00:15:25,170 --> 00:15:29,990
Έτσι, μπορούμε να αλλάξουμε το προηγούμενο 15
δείκτη ώστε να δείχνει σε null,

298
00:15:29,990 --> 00:15:31,874
και εμείς απλά μετακινήστε το πάνω από το κεφάλι.

299
00:15:31,874 --> 00:15:32,540
Και εκεί θα πάμε.

300
00:15:32,540 --> 00:15:35,840
Τώρα έχουμε επιτυχία
dequeued 12, και τώρα

301
00:15:35,840 --> 00:15:39,180
έχουν μια άλλη ουρά των 4 στοιχείων.

302
00:15:39,180 --> 00:15:41,700
Αυτό είναι λίγο πολύ όλα
Είναι εκεί για να ουρές,

303
00:15:41,700 --> 00:15:45,810
τόσο βασισμένη σε πίνακα και να συνδέεται κατάλογο βάσει.

304
00:15:45,810 --> 00:15:46,860
Είμαι ο Νταγκ Lloyd.

305
00:15:46,860 --> 00:15:49,100
Αυτό είναι το CS 50.

306
00:15:49,100 --> 00:15:50,763