1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Εντάξει,
τόσο από αυτό το σημείο είστε

3
00:00:05,990 --> 00:00:09,020
πιθανώς αρκετά εξοικειωμένοι
με πίνακες και συνδεδεμένες λίστες

4
00:00:09,020 --> 00:00:10,950
το οποίο είναι το δύο κύριες
δομές δεδομένων έχουμε

5
00:00:10,950 --> 00:00:16,810
μίλησε για την τήρηση σύνολα
δεδομένων των παρόμοιων τύπων δεδομένων που διοργανώνονται.

6
00:00:16,810 --> 00:00:19,080
>> Τώρα θα πάμε να μιλήσουμε
για ένα ζευγάρι των μεταβολών

7
00:00:19,080 --> 00:00:20,330
σε συστοιχίες και συνδεδεμένες λίστες.

8
00:00:20,330 --> 00:00:22,362
Σε αυτό το βίντεο θα πάμε
για να μιλήσουμε για στοίβες.

9
00:00:22,362 --> 00:00:25,320
Συγκεκριμένα θα πάμε να μιλήσουμε
περίπου μια δομή δεδομένων που ονομάζεται μια στοίβα.

10
00:00:25,320 --> 00:00:28,510
Ανάκληση από προηγούμενες συζητήσεις
σχετικά με τους δείκτες και τη μνήμη,

11
00:00:28,510 --> 00:00:32,060
ότι η στοίβα είναι επίσης η
όνομα για ένα τμήμα της μνήμης

12
00:00:32,060 --> 00:00:34,980
όπου δηλώνεται στατικά
memory-- μνήμης που

13
00:00:34,980 --> 00:00:38,730
όνομα, μεταβλητές που αναφέρουμε, κ.ά.
κουφώματα και τα λοιπά και η λειτουργία των οποίων επίσης

14
00:00:38,730 --> 00:00:41,000
Υπάρχουν κλήση πλαίσια στοίβα.

15
00:00:41,000 --> 00:00:45,421
Έτσι, αυτό είναι μια δομή δεδομένων στοίβας
όχι ένα τμήμα της στοίβας μνήμης.

16
00:00:45,421 --> 00:00:45,920
ΕΝΤΆΞΕΙ.

17
00:00:45,920 --> 00:00:46,890
>> Αλλά αυτό είναι μια στοίβα;

18
00:00:46,890 --> 00:00:49,220
Γι 'αυτό είναι λίγο πολύ ένα
ιδιαίτερο είδος της δομής

19
00:00:49,220 --> 00:00:51,190
που διατηρεί τα δεδομένα με οργανωμένο τρόπο.

20
00:00:51,190 --> 00:00:53,760
Και υπάρχουν δύο πολύ
κοινούς τρόπους για την εφαρμογή

21
00:00:53,760 --> 00:00:57,380
στοίβες χρησιμοποιώντας δύο δομές δεδομένων
ότι είμαστε ήδη εξοικειωμένοι με,

22
00:00:57,380 --> 00:01:00,340
πίνακες και συνδεδεμένες λίστες.

23
00:01:00,340 --> 00:01:04,430
Τι κάνει μια ειδική στοίβα είναι η
τρόπος με τον οποίο μπορούμε να βάλουμε την πληροφορία

24
00:01:04,430 --> 00:01:08,200
σε στοίβα, και τον τρόπο που
αφαιρέσει τις πληροφορίες από τη στοίβα.

25
00:01:08,200 --> 00:01:11,600
Ιδίως με στοίβες
ο κανόνας είναι μόνο το πιο

26
00:01:11,600 --> 00:01:15,830
προστέθηκε πρόσφατα στοιχείο μπορεί να αφαιρεθεί.

27
00:01:15,830 --> 00:01:17,660
>> Έτσι σκεφτείτε το σαν να είναι μια στοίβα.

28
00:01:17,660 --> 00:01:21,170
Είμαστε συσσωρεύονται πληροφορίες
πάνω από μόνη της,

29
00:01:21,170 --> 00:01:24,271
και μόνο το πράγμα στην κορυφή
του πασσάλου μπορεί να αφαιρείται.

30
00:01:24,271 --> 00:01:27,020
Εμείς δεν μπορεί να αφαιρέσει το πράγμα κάτω
γιατί οτιδήποτε άλλο θα

31
00:01:27,020 --> 00:01:28,020
καταρρεύσει και να πέσει πάνω.

32
00:01:28,020 --> 00:01:32,580
Γι 'αυτό και πραγματικά χτίζουμε μια στοίβα που
Στη συνέχεια, πρέπει να αφαιρέσετε το κομμάτι από το κομμάτι.

33
00:01:32,580 --> 00:01:36,590
Εξαιτίας αυτού που συνήθως αναφέρονται
σε μια στοίβα ως δομή LIFO,

34
00:01:36,590 --> 00:01:38,940
τελευταία in, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, τελευταία in, first out.

36
00:01:42,290 --> 00:01:45,635
>> Έτσι, εξαιτίας αυτού του περιορισμού για
πώς οι πληροφορίες μπορούν να προστεθούν σε

37
00:01:45,635 --> 00:01:49,080
και απομακρύνεται από το σωρό, δεν υπάρχει πραγματικά
μόνο δύο πράγματα που μπορούμε να κάνουμε με μια στοίβα.

38
00:01:49,080 --> 00:01:52,010
Μπορούμε να ωθήσει, το οποίο είναι το
όρος που χρησιμοποιούμε για την προσθήκη

39
00:01:52,010 --> 00:01:55,130
ένα νέο στοιχείο στην κορυφή της
στοίβα, ή εάν η στοίβα δεν υπάρχει

40
00:01:55,130 --> 00:01:58,550
και είμαστε αυτό δημιουργεί από το μηδέν,
δημιουργώντας τη στοίβα στην πρώτη θέση

41
00:01:58,550 --> 00:02:00,110
θα πρέπει να πιέζει.

42
00:02:00,110 --> 00:02:04,990
Και τότε ποπ, αυτό είναι το είδος του CS
όρος που χρησιμοποιούμε για να αφαιρέσετε τον πιο πρόσφατο

43
00:02:04,990 --> 00:02:08,330
πρόσθετο στοιχείο από την κορυφή της στοίβας.

44
00:02:08,330 --> 00:02:11,130
>> Έτσι θα πάμε να δούμε τόσο
υλοποιήσεις, τόσο με βάση σειρά

45
00:02:11,130 --> 00:02:13,120
και συνδεδεμένη λίστα βασίζεται.

46
00:02:13,120 --> 00:02:14,870
Και θα πάμε να
ξεκινήστε με σειρά που βασίζεται.

47
00:02:14,870 --> 00:02:19,990
Έτσι, εδώ είναι η βασική ιδέα του τι
η δομή δεδομένων στοίβας σειρά με βάση

48
00:02:19,990 --> 00:02:21,140
θα μοιάζουν.

49
00:02:21,140 --> 00:02:23,740
Έχουμε έναν ορισμό δακτυλογραφημένη εδώ.

50
00:02:23,740 --> 00:02:27,790
Μέσα από ότι έχουμε δύο μέλη
ή τα πεδία της δομής.

51
00:02:27,790 --> 00:02:29,880
Έχουμε μια σειρά.

52
00:02:29,880 --> 00:02:32,400
Και πάλι είμαι με τη χρήση του
αυθαίρετη τιμή τύπο δεδομένων.

53
00:02:32,400 --> 00:02:35,180
>> Έτσι, αυτό θα μπορούσε να είναι οποιουδήποτε τύπου δεδομένων,
int char ή κάποια άλλα δεδομένα

54
00:02:35,180 --> 00:02:37,080
Τύπος δημιουργήσατε προηγουμένως.

55
00:02:37,080 --> 00:02:39,861
Έτσι, έχουμε μια σειρά μεγέθους χωρητικότητας.

56
00:02:39,861 --> 00:02:44,010
Χωρητικότητα είναι ένα κιλό ορίζεται σταθερά,
ίσως κάπου αλλού στο αρχείο μας.

57
00:02:44,010 --> 00:02:47,550
Έτσι παρατηρήσετε ήδη με το συγκεκριμένο
εφαρμογή που οριοθετούν

58
00:02:47,550 --> 00:02:49,800
τους εαυτούς μας ως ήταν τυπικά
η περίπτωση με συστοιχίες,

59
00:02:49,800 --> 00:02:53,170
το οποίο δεν μπορούμε να αλλάξετε το μέγεθος δυναμικά,
όπου υπάρχει ένας ορισμένος αριθμός

60
00:02:53,170 --> 00:02:55,450
των στοιχείων μέγιστο που
μπορούμε να θέσουμε σε στοίβα μας.

61
00:02:55,450 --> 00:02:57,930
Σε αυτή την περίπτωση είναι τα στοιχεία ικανότητας.

62
00:02:57,930 --> 00:03:00,310
>> Κρατάμε επίσης παρακολουθείτε
η κορυφή της στοίβας.

63
00:03:00,310 --> 00:03:04,350
Τι στοιχείο είναι η πιο
προστέθηκε πρόσφατα στη στοίβα;

64
00:03:04,350 --> 00:03:07,470
Και έτσι μπορούμε να παρακολουθείτε ότι
σε μια μεταβλητή που ονομάζεται κορυφή.

65
00:03:07,470 --> 00:03:11,692
Και όλα αυτά παίρνει πλανώνται
σε ένα νέο τύπο δεδομένων που ονομάζεται μια στοίβα.

66
00:03:11,692 --> 00:03:13,400
Και μόλις είμαστε δημιουργούνται
αυτό το νέο τύπο δεδομένων

67
00:03:13,400 --> 00:03:15,410
μπορούμε να την αντιμετωπίσουμε σαν
κάθε άλλο τύπο δεδομένων.

68
00:03:15,410 --> 00:03:20,970
Μπορούμε να δηλώσουμε στοίβα s, όπως ακριβώς
θα μπορούσαμε να κάνουμε int x, y ή char.

69
00:03:20,970 --> 00:03:22,990
Και όταν λέμε στοίβα
s, καλά τι συμβαίνει

70
00:03:22,990 --> 00:03:26,420
Είναι έχουμε ένα σύνολο
μνήμης που προορίζεται για εμάς.

71
00:03:26,420 --> 00:03:28,770
>> Στην περίπτωση αυτή, ικανότητα
Έχω προφανώς αποφάσισε

72
00:03:28,770 --> 00:03:33,470
είναι 10, γιατί έχω ένα
μόνο μεταβλητή του τύπου στοίβας

73
00:03:33,470 --> 00:03:35,320
το οποίο περιέχει δύο πεδία ανακαλέσουν.

74
00:03:35,320 --> 00:03:38,330
Μια σειρά, σε αυτή την περίπτωση πρόκειται
να είναι μια σειρά ακεραίων

75
00:03:38,330 --> 00:03:40,440
όπως συμβαίνει στην πλειονότητα των παραδειγμάτων μου.

76
00:03:40,440 --> 00:03:43,996
Και μια άλλη μεταβλητή ακέραιο
ικανή να αποθηκεύει την κορυφή,

77
00:03:43,996 --> 00:03:45,870
πιο πρόσφατα προστέθηκε
στοιχείο στη στοίβα.

78
00:03:45,870 --> 00:03:50,290
Έτσι, ένα ενιαίο στοίβα από ό, τι
ακριβώς ορίζεται μοιάζει με αυτό.

79
00:03:50,290 --> 00:03:53,190
Είναι ένα κουτί που περιέχει
μια σειρά από 10 τι

80
00:03:53,190 --> 00:03:57,280
θα είναι ακέραιοι σε αυτήν την περίπτωση και
άλλη μεταβλητή ακεραίου εκεί στο πράσινο

81
00:03:57,280 --> 00:04:00,010
για να δείχνει την κορυφή της στοίβας.

82
00:04:00,010 --> 00:04:02,600
>> Για να ρυθμίσετε το πάνω μέρος του
στοίβα απλά λέμε s.top.

83
00:04:02,600 --> 00:04:04,890
Αυτό είναι το πώς θα αποκτήσετε πρόσβαση σε ένα
πεδίο μιας δομής ανάκληση.

84
00:04:04,890 --> 00:04:10,460
s.top ισούται με 0 αποτελεσματικά
κάνει αυτό σε στοίβα μας.

85
00:04:10,460 --> 00:04:12,960
Έτσι και πάλι έχουμε δύο πράξεις
ότι μπορούμε να εκτελέσουμε τώρα.

86
00:04:12,960 --> 00:04:14,270
Μπορούμε να ωθήσει και μπορούμε να σκάσει.

87
00:04:14,270 --> 00:04:15,635
Ας αρχίσουμε με το πάτημα.

88
00:04:15,635 --> 00:04:18,260
Και πάλι, ωθώντας είναι η προσθήκη μιας νέας
στοιχείο στην κορυφή της στοίβας.

89
00:04:18,260 --> 00:04:21,460
>> Έτσι, αυτό που χρειαζόμαστε για να κάνουμε
αυτή η συστοιχία εφαρμογή που βασίζεται;

90
00:04:21,460 --> 00:04:23,210
Καλά σε γενικές γραμμές η
λειτουργία ώθησης πρόκειται

91
00:04:23,210 --> 00:04:26,160
να πρέπει να αποδεχθεί μια
pointer στη στοίβα.

92
00:04:26,160 --> 00:04:28,610
Τώρα πάρτε ένα δευτερόλεπτο και να το σκεφτώ.

93
00:04:28,610 --> 00:04:32,840
Γιατί να θέλουμε να το δεχτούμε
ένας δείκτης στη στοίβα;

94
00:04:32,840 --> 00:04:36,830
Ανάκληση από την προηγούμενη βίντεο για
εμβέλεια των μεταβλητών και δεικτών,

95
00:04:36,830 --> 00:04:42,350
τι θα συμβεί αν απλώς αποστέλλονται
στοίβα, s μάλλον ως παράμετρος;

96
00:04:42,350 --> 00:04:45,770
Τι πραγματικά θα περάσει εκεί μέσα;

97
00:04:45,770 --> 00:04:49,430
Θυμηθείτε ότι δημιουργείτε ένα αντίγραφο
όταν θα το περάσει σε μια συνάρτηση

98
00:04:49,430 --> 00:04:51,160
εκτός και αν χρησιμοποιούμε δείκτες.

99
00:04:51,160 --> 00:04:55,380
Και έτσι αυτή η λειτουργία ωθήσει ανάγκες
να δεχθεί ένα δείκτη σε στοίβα

100
00:04:55,380 --> 00:04:59,160
έτσι ώστε να είμαστε πραγματικά αλλάζει
η στοίβα σκοπεύουμε να αλλάξουμε.

101
00:04:59,160 --> 00:05:03,060
>> Το άλλο πράγμα ώθηση θέλει πιθανώς να
αποδέχονται είναι ένα στοιχείο δεδομένων της αξίας του τύπου.

102
00:05:03,060 --> 00:05:06,970
Σε αυτή την περίπτωση, πάλι, ότι ένας ακέραιος
θα πάμε για να προσθέσετε στην κορυφή της στοίβας.

103
00:05:06,970 --> 00:05:08,680
Έτσι έχουμε δύο παραμέτρους μας.

104
00:05:08,680 --> 00:05:11,310
Τι θα πάμε να
τώρα κάνουμε μέσα ώθησης;

105
00:05:11,310 --> 00:05:14,860
Λοιπόν, απλά, είμαστε ακριβώς πρόκειται να προσθέσει
ότι το στοιχείο στην κορυφή της στοίβας

106
00:05:14,860 --> 00:05:22,860
και στη συνέχεια να αλλάξετε όπου η κορυφή του
η στοίβα είναι, ότι s dot κορυφαία αξία.

107
00:05:22,860 --> 00:05:25,639
Έτσι, αυτό είναι ό, τι μια λειτουργία
δήλωση για την ώθηση

108
00:05:25,639 --> 00:05:27,680
μπορεί να μοιάζει σε ένα
βασισμένη σε πίνακα εφαρμογής.

109
00:05:27,680 --> 00:05:30,967
>> Και πάλι αυτό δεν είναι ένα σκληρό και απαράβατο κανόνα
ότι θα μπορούσε να αλλάξει αυτό και να έχουν

110
00:05:30,967 --> 00:05:32,050
ποικίλλουν σε διαφορετικούς τρόπους.

111
00:05:32,050 --> 00:05:33,840
Ίσως s έχει κηρυχθεί σε παγκόσμιο επίπεδο.

112
00:05:33,840 --> 00:05:36,180
Και έτσι δεν χρειάζεται καν
για να περάσει είναι σαν μια παράμετρο.

113
00:05:36,180 --> 00:05:39,125
Αυτό είναι και πάλι μόνο ένα
γενική περίπτωση για την ώθηση.

114
00:05:39,125 --> 00:05:41,000
Και υπάρχουν διαφορετικοί
τους τρόπους εφαρμογής της.

115
00:05:41,000 --> 00:05:42,810
Αλλά στην περίπτωση αυτή μας
ώθηση πρόκειται να πάρει

116
00:05:42,810 --> 00:05:48,540
δύο επιχειρήματα, ένας δείκτης σε μια στοίβα και
ένα στοιχείο δεδομένων της αξίας του τύπου, ακέραια

117
00:05:48,540 --> 00:05:49,840
σε αυτήν την περίπτωση.

118
00:05:49,840 --> 00:05:52,100
>> Γι 'αυτό και κήρυξε s, εμείς
είπε s.top ισούται με 0.

119
00:05:52,100 --> 00:05:55,969
Τώρα ας ωθήσει το
αριθμός 28 πάνω στη στοίβα.

120
00:05:55,969 --> 00:05:57,010
Λοιπόν, τι σημαίνει αυτό;

121
00:05:57,010 --> 00:05:59,600
Λοιπόν σήμερα
κορυφή της στοίβας είναι 0.

122
00:05:59,600 --> 00:06:01,350
Και ναι, ποιο είναι βασικά
πρόκειται να συμβεί είναι

123
00:06:01,350 --> 00:06:05,820
θα πάμε να κολλήσει τον αριθμό
28 σε θέση πίνακα 0.

124
00:06:05,820 --> 00:06:09,540
Αρκετά απλό, σωστά, ότι
ήταν η κορυφαία και τώρα είμαστε καλοί να πάτε.

125
00:06:09,540 --> 00:06:12,910
Και τότε θα πρέπει να αλλάξουμε ό, τι
η κορυφή της στοίβας θα είναι.

126
00:06:12,910 --> 00:06:15,130
Έτσι ώστε την επόμενη φορά
πιέζουμε ένα στοιχείο σε,

127
00:06:15,130 --> 00:06:18,017
θα πάμε να το αποθηκεύσετε σε
θέση πίνακα, κατά πάσα πιθανότητα δεν είναι 0.

128
00:06:18,017 --> 00:06:20,100
Δεν θέλουμε να αντικαταστήσετε
τι μπορούμε απλά βάλτε εκεί.

129
00:06:20,100 --> 00:06:23,510
Και έτσι θα προχωρήσουμε μόνο την κορυφή προς 1.

130
00:06:23,510 --> 00:06:24,890
Αυτό ίσως έχει νόημα.

131
00:06:24,890 --> 00:06:28,940
>> Τώρα, αν θέλουμε να θέσουμε ένα ακόμη στοιχείο
στη στοίβα, λέμε ότι θέλουμε να πιέσουμε 33,

132
00:06:28,940 --> 00:06:33,190
και τώρα είμαστε ακριβώς πρόκειται να λάβει 33
και το βάζουμε σε σειρά αριθμός θέσης

133
00:06:33,190 --> 00:06:37,580
1, και στη συνέχεια να αλλάξετε το επάνω μέρος μας
στοίβα να είναι συστοιχία αριθμό θέσης δύο.

134
00:06:37,580 --> 00:06:40,650
Έτσι, αν την επόμενη φορά που θέλουμε να
ωθήσει ένα στοιχείο στη στοίβα,

135
00:06:40,650 --> 00:06:43,087
αυτό θα πρέπει να τεθεί σε θέση πίνακα 2.

136
00:06:43,087 --> 00:06:44,420
Και ας το κάνουμε αυτό για μια ακόμη φορά.

137
00:06:44,420 --> 00:06:45,753
Θα πιέσει 19 ανοικτά από τις στοίβες.

138
00:06:45,753 --> 00:06:48,940
Θα βάλει 19 σε θέση πίνακα 2
και να αλλάξετε την κορυφή της στοίβας μας

139
00:06:48,940 --> 00:06:51,220
να είναι θέση πίνακα 3
Έτσι, αν η επόμενη φορά που θα

140
00:06:51,220 --> 00:06:54,780
πρέπει να κάνει μια ώθηση είμαστε καλοί να πάτε.

141
00:06:54,780 --> 00:06:56,980
>> Εντάξει, έτσι ώστε να είναι πιέζει με λίγα λόγια.

142
00:06:56,980 --> 00:06:57,830
Τι γίνεται με το σκάσιμο;

143
00:06:57,830 --> 00:07:00,240
Έτσι σκασίματος είναι το είδος του
ομόλογό του να πιέζει.

144
00:07:00,240 --> 00:07:02,720
Είναι το πώς θα καταργήσετε δεδομένα από τη στοίβα.

145
00:07:02,720 --> 00:07:04,610
Και σε γενικές γραμμές τις ανάγκες ποπ
να κάνετε τα εξής.

146
00:07:04,610 --> 00:07:07,600
Πρέπει να δεχθεί ένα δείκτη προς το
στοίβα, και πάλι στη γενική περίπτωση.

147
00:07:07,600 --> 00:07:10,480
Σε κάποια άλλη περίπτωση ίσως
έχουν δηλώσει τη στοίβα σε παγκόσμιο επίπεδο,

148
00:07:10,480 --> 00:07:13,910
στην οποία περίπτωση δεν χρειάζεται να το περάσετε
σε επειδή έχει ήδη πρόσβαση σε αυτό

149
00:07:13,910 --> 00:07:15,541
ως καθολική μεταβλητή.

150
00:07:15,541 --> 00:07:17,040
Αλλά τότε τι άλλο πρέπει να κάνουμε;

151
00:07:17,040 --> 00:07:21,000
Καλά ήμασταν προσαύξηση
η κορυφή της στοίβας στην ώθηση,

152
00:07:21,000 --> 00:07:24,050
γι 'αυτό πρόκειται πιθανώς να θέλουν
να ελαττώσει την κορυφή της στοίβας

153
00:07:24,050 --> 00:07:25,009
στην ποπ, έτσι δεν είναι;

154
00:07:25,009 --> 00:07:26,800
Και τότε φυσικά
είμαστε επίσης πρόκειται να θέλουν

155
00:07:26,800 --> 00:07:29,240
να επιστρέψει την αξία που βγάζουμε.

156
00:07:29,240 --> 00:07:32,125
Αν είμαστε προσθήκη στοιχείων, θέλουμε
για να πάρει στοιχεία από αργότερα,

157
00:07:32,125 --> 00:07:34,000
πιθανότατα στην πραγματικότητα
Θέλετε να τις αποθηκεύσετε έτσι

158
00:07:34,000 --> 00:07:36,490
όχι μόνο τα διαγράφει από το
στοίβα και στη συνέχεια να κάνουμε τίποτα μαζί τους.

159
00:07:36,490 --> 00:07:38,500
Σε γενικές γραμμές, αν είμαστε
πιέζει και να βρεθώ εδώ

160
00:07:38,500 --> 00:07:41,250
θέλουμε να αποθηκεύσουμε αυτή
πληροφοριών με ουσιαστικό τρόπο

161
00:07:41,250 --> 00:07:43,250
και γι 'αυτό δεν κάνει
νόημα να το απορρίψει μόνο.

162
00:07:43,250 --> 00:07:46,380
Έτσι, η λειτουργία αυτή θα πρέπει να
ίσως επιστρέψει μια τιμή για εμάς.

163
00:07:46,380 --> 00:07:51,040
>> Έτσι, αυτό είναι ό, τι μια δήλωση για την ποπ
μπορεί να μοιάζει σαν να υπάρχει στην επάνω αριστερή γωνία.

164
00:07:51,040 --> 00:07:53,870
Αυτή η συνάρτηση επιστρέφει
δεδομένων της αξίας του τύπου.

165
00:07:53,870 --> 00:07:56,320
Πάλι έχουμε χρησιμοποιήσει
ακέραιοι όλη.

166
00:07:56,320 --> 00:08:01,916
Και δέχεται ένα δείκτη σε μια στοίβα όπως
μοναδικό επιχείρημα του ή μόνη παράμετρος.

167
00:08:01,916 --> 00:08:03,040
Έτσι τι είναι ποπ πρόκειται να κάνει;

168
00:08:03,040 --> 00:08:07,990
Ας πούμε ότι θέλουμε τώρα
ποπ ένα στοιχείο εκτός της s.

169
00:08:07,990 --> 00:08:14,000
Έτσι θυμηθείτε είπα ότι στοίβες είναι η τελευταία
in, first out, LIFO δομές δεδομένων.

170
00:08:14,000 --> 00:08:17,855
Ποιο στοιχείο πρόκειται να
να απομακρύνονται από τη στοίβα;

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Μήπως να μαντέψετε 19;

173
00:08:24,150 --> 00:08:25,290
Επειδή θα ήθελα να είναι σωστή.

174
00:08:25,290 --> 00:08:28,836
19 ήταν το τελευταίο στοιχείο που προστίθεται στο
στοίβα όταν πιέσαμε στοιχεία σχετικά,

175
00:08:28,836 --> 00:08:31,210
και γι 'αυτό πρόκειται να το πρώτο
στοιχείο που παίρνει αφαιρεθεί.

176
00:08:31,210 --> 00:08:34,780
Είναι σαν να λέγαμε 28, και
Στη συνέχεια βάζουμε 33 πάνω από αυτό,

177
00:08:34,780 --> 00:08:36,659
και βάζουμε 19 πάνω από αυτό.

178
00:08:36,659 --> 00:08:40,650
Το μόνο στοιχείο που μπορούμε να απογειωθεί είναι 19.

179
00:08:40,650 --> 00:08:45,019
>> Τώρα στο διάγραμμα εδώ ό, τι έχω κάνει
Είναι το είδος των διαγραμμένων 19 από τον πίνακα.

180
00:08:45,019 --> 00:08:46,810
Αυτό δεν είναι στην πραγματικότητα
τι θα πάμε να κάνουμε.

181
00:08:46,810 --> 00:08:48,934
Εμείς απλά θα το είδος
της προσποιούμαστε ότι δεν υπάρχει.

182
00:08:48,934 --> 00:08:51,441
Είναι ακόμα εκεί
αυτή τη θέση μνήμης,

183
00:08:51,441 --> 00:08:54,190
αλλά είμαστε ακριβώς πρόκειται να το αγνοήσει
αλλάζοντας την κορυφή της στοίβας μας

184
00:08:54,190 --> 00:08:56,080
από το να είναι 3 προς 2.

185
00:08:56,080 --> 00:08:58,720
Έτσι, αν ήταν να πιέσει τώρα
Ένα άλλο στοιχείο στη στοίβα,

186
00:08:58,720 --> 00:09:00,720
θα γράψει πάνω από 19.

187
00:09:00,720 --> 00:09:03,990
>> Αλλά ας μην μπει στον κόπο
διαγραφή 19 από τη στοίβα.

188
00:09:03,990 --> 00:09:05,830
Εμείς απλά να προσποιούμαστε ότι δεν υπάρχει.

189
00:09:05,830 --> 00:09:11,107
Για τους σκοπούς της στοίβας θα φύγει αν
αλλάζουμε την κορυφή να είναι 2 αντί για 3.

190
00:09:11,107 --> 00:09:12,690
Εντάξει, έτσι ώστε να ήταν λίγο πολύ αυτό.

191
00:09:12,690 --> 00:09:15,080
Αυτό είναι το μόνο που χρειάζεται να κάνουμε
να σκάσει ένα στοιχείο μακριά.

192
00:09:15,080 --> 00:09:16,090
Ας το κάνουμε ξανά.

193
00:09:16,090 --> 00:09:18,610
Έτσι έχω να επισημαίνονται με κόκκινο χρώμα εδώ για να
δείχνουν φτιάχνουμε μια άλλη κλήση.

194
00:09:18,610 --> 00:09:19,720
Εμείς πάμε να κάνουμε το ίδιο πράγμα.

195
00:09:19,720 --> 00:09:20,803
>> Έτσι τι πρόκειται να συμβεί;

196
00:09:20,803 --> 00:09:23,670
Λοιπόν, θα πάμε να αποθηκεύσετε
33 x και θα πάμε

197
00:09:23,670 --> 00:09:26,217
να αλλάξει το κορυφή της στοίβας να 1.

198
00:09:26,217 --> 00:09:29,050
Έτσι ώστε αν ήμασταν τώρα να ωθήσει ένα
στοιχείου στη στοίβα που είμαστε

199
00:09:29,050 --> 00:09:31,610
πρόκειται να κάνουμε τώρα,
τι πρόκειται να συμβεί

200
00:09:31,610 --> 00:09:36,367
είναι θα πάμε overwrite
συστοιχία αριθμό θέσης 1.

201
00:09:36,367 --> 00:09:38,950
Έτσι, το 33 που είχε απομείνει από το είδος
πίσω από ότι εμείς απλώς προσποιήθηκε

202
00:09:38,950 --> 00:09:44,390
δεν υπάρχει πια, απλά θα
για να κοπανάω και να θέσει 40 εκεί αντ 'αυτού.

203
00:09:44,390 --> 00:09:46,290
Και τότε φυσικά,
αφού κάναμε μια ώθηση,

204
00:09:46,290 --> 00:09:48,780
θα πάμε για να αυξήσετε το
κορυφή της στοίβας από 1 να 2

205
00:09:48,780 --> 00:09:50,950
έτσι ώστε αν προσθέτουμε τώρα
Ένα άλλο στοιχείο αυτό θα

206
00:09:50,950 --> 00:09:54,700
μπω σε σειρά αριθμό θέσης δύο.

207
00:09:54,700 --> 00:09:57,590
>> Τώρα συνδεδεμένες λίστες είναι μια άλλη
τρόπος για την εφαρμογή στοίβες.

208
00:09:57,590 --> 00:10:01,210
Και αν τον ορισμό αυτό με
οθόνη εδώ φαίνεται γνωστό σε σας,

209
00:10:01,210 --> 00:10:04,260
αυτό συμβαίνει γιατί φαίνεται σχεδόν
ακριβώς το ίδιο, στην πραγματικότητα,

210
00:10:04,260 --> 00:10:07,790
λίγο πολύ είναι ακριβώς η
ίδια ως μεμονωμένα συνδεδεμένη λίστα,

211
00:10:07,790 --> 00:10:11,990
αν θυμάστε από τη συζήτησή μας
μεμονωμένα συνδεδεμένες λίστες σε άλλο βίντεο.

212
00:10:11,990 --> 00:10:15,510
Ο μόνος περιορισμός εδώ
είναι για μας, όπως προγραμματιστές,

213
00:10:15,510 --> 00:10:17,900
δεν είμαστε επιτρέπεται να
εισάγετε ή να διαγράψετε τυχαία

214
00:10:17,900 --> 00:10:20,620
από την μεμονωμένα συνδεδεμένη λίστα
πράγμα που θα μπορούσαμε να κάνουμε στο παρελθόν.

215
00:10:20,620 --> 00:10:25,820
Μπορούμε μόνο τώρα να εισάγετε και να διαγράψετε από
η μπροστινή ή η κορυφή του συνδεδεμένου

216
00:10:25,820 --> 00:10:26,320
κατάλογο.

217
00:10:26,320 --> 00:10:28,028
Αυτό είναι πραγματικά το μόνο
διαφορά όμως.

218
00:10:28,028 --> 00:10:29,700
Αυτό είναι αλλιώς ένα μεμονωμένα συνδεδεμένη λίστα.

219
00:10:29,700 --> 00:10:32,060
Είναι μόνο ο περιορισμός
αντικαθιστώντας τον εαυτό μας

220
00:10:32,060 --> 00:10:35,770
οι προγραμματιστές ότι
αλλάζει το σε μια στοίβα.

221
00:10:35,770 --> 00:10:39,280
>> Ο κανόνας εδώ είναι να διατηρεί πάντα μια
pointer στο κεφάλι μιας συνδεδεμένης λίστας.

222
00:10:39,280 --> 00:10:41,520
Αυτό είναι φυσικά ένα γενικά
σημαντικός κανόνας για πρώτη φορά.

223
00:10:41,520 --> 00:10:44,260
Για μεμονωμένα συνδεδεμένη λίστα ούτως ή άλλως σας
μόνο που χρειάζεται είναι ένα δείκτη στο κεφάλι

224
00:10:44,260 --> 00:10:46,160
ώστε να έχει αυτό
αλυσίδας να είναι σε θέση να υποβάλει

225
00:10:46,160 --> 00:10:48,596
σε κάθε άλλο στοιχείο
στη συνδεδεμένη λίστα.

226
00:10:48,596 --> 00:10:50,470
Αλλά είναι ιδιαίτερα
σημαντική με μια στοίβα.

227
00:10:50,470 --> 00:10:52,386
Και έτσι γενικά είστε
πρόκειται να θέλουν πραγματικά

228
00:10:52,386 --> 00:10:54,090
Αυτός ο δείκτης είναι μια καθολική μεταβλητή.

229
00:10:54,090 --> 00:10:56,574
Είναι κατά πάσα πιθανότητα θα
είναι ακόμη πιο εύκολο με αυτόν τον τρόπο.

230
00:10:56,574 --> 00:10:58,240
Έτσι ποια είναι τα ανάλογα της ώθησης και ποπ;

231
00:10:58,240 --> 00:10:58,740
Δεξιά.

232
00:10:58,740 --> 00:11:01,812
Έτσι, πιέζει και πάλι είναι η προσθήκη
ένα νέο στοιχείο στη στοίβα.

233
00:11:01,812 --> 00:11:03,770
Σε μια συνδεδεμένη λίστα που
σημαίνει ότι πρόκειται να έχουν

234
00:11:03,770 --> 00:11:07,770
για να δημιουργήσετε ένα νέο κόμβο που είμαστε
πρόκειται να προσθέσει στη συνδεδεμένη λίστα,

235
00:11:07,770 --> 00:11:10,500
και, στη συνέχεια, ακολουθήστε τα προσεκτικά βήματα
ότι έχουμε υπογραμμίσει στο παρελθόν

236
00:11:10,500 --> 00:11:16,050
σε μεμονωμένα συνδεδεμένες λίστες για να το προσθέσετε στο
η αλυσίδα χωρίς σπάσιμο της αλυσίδας

237
00:11:16,050 --> 00:11:18,900
και να χάσει ή ορφανούς οποιοδήποτε
στοιχεία της συνδεδεμένης λίστας.

238
00:11:18,900 --> 00:11:21,820
Και αυτό είναι βασικά αυτό που
μικρή σταγόνα του κειμένου εκεί συνοψίζει.

239
00:11:21,820 --> 00:11:23,740
Και ας ρίξουμε μια ματιά
το σαν ένα διάγραμμα.

240
00:11:23,740 --> 00:11:24,823
>> Τόσο εδώ είναι συνδεδεμένη λίστα μας.

241
00:11:24,823 --> 00:11:26,620
Περιέχει ταυτόχρονα τέσσερα στοιχεία.

242
00:11:26,620 --> 00:11:30,420
Και πιο τέλεια εδώ μας
στοίβα που περιέχει τέσσερα στοιχεία.

243
00:11:30,420 --> 00:11:36,030
Και ας πούμε ότι θέλουμε τώρα να
ωθήσει ένα νέο στοιχείο σε αυτή τη στοίβα.

244
00:11:36,030 --> 00:11:39,792
Και θέλουμε να ωθήσει ένα νέο
αντικείμενο των οποίων τα δεδομένα η τιμή είναι 12.

245
00:11:39,792 --> 00:11:41,000
Λοιπόν, τι θα κάνουμε;

246
00:11:41,000 --> 00:11:43,420
Λοιπόν πρώτα θα πάμε να
χώρο malloc, δυναμικά

247
00:11:43,420 --> 00:11:45,411
διατεθεί χώρος για ένα νέο κόμβο.

248
00:11:45,411 --> 00:11:48,160
Και φυσικά αμέσως μετά
κάνουμε μια κλήση για να είμαστε πάντα malloc

249
00:11:48,160 --> 00:11:52,989
φροντίστε να ελέγξετε για μηδενική,
γιατί αν έχουμε μηδενική πίσω

250
00:11:52,989 --> 00:11:54,280
υπήρχε κάποιο είδος του προβλήματος.

251
00:11:54,280 --> 00:11:57,570
Δεν θέλουμε να dereference λόγω null
δείκτη ή θα υποστούν βλάβη SEG.

252
00:11:57,570 --> 00:11:58,510
Αυτό δεν είναι καλό.

253
00:11:58,510 --> 00:11:59,760
Έτσι έχουμε malloced του κόμβου.

254
00:11:59,760 --> 00:12:01,260
Θα υποθέσουμε ότι είχαμε επιτυχία εδώ.

255
00:12:01,260 --> 00:12:06,090
Εμείς πάμε να θέσει σε 12
το πεδίο δεδομένων του εν λόγω κόμβου.

256
00:12:06,090 --> 00:12:11,570
Τώρα μπορώ να σας υπενθυμίσω το οποίο δείκτες μας
κινείται δίπλα έτσι ώστε να μην σπάσει την αλυσίδα;

257
00:12:11,570 --> 00:12:15,100
Έχουμε δύο επιλογές εδώ, αλλά
η μόνη που πρόκειται να είναι ασφαλείς

258
00:12:15,100 --> 00:12:19,330
είναι να θέσει νέα δίπλα στο δείκτη
σημείο στην παλιά κεφαλή της λίστας

259
00:12:19,330 --> 00:12:21,360
ή ό, τι θα είναι σύντομα η
παλιά επικεφαλής της λίστας.

260
00:12:21,360 --> 00:12:23,610
Και τώρα που όλοι μας
Τα στοιχεία δεμένους,

261
00:12:23,610 --> 00:12:27,370
Λίστα μπορούμε να προχωρήσουμε απλώς να επισημάνω
στην ίδια θέση που κάνει νέα.

262
00:12:27,370 --> 00:12:33,550
Και έχουμε τώρα ουσιαστικά έσπρωξε
νέο στοιχείο πάνω στο μπροστινό μέρος της στοίβας.

263
00:12:33,550 --> 00:12:36,420
>> Για να είμαστε ποπ απλά θέλετε να
διαγράψετε το πρώτο στοιχείο.

264
00:12:36,420 --> 00:12:38,150
Και έτσι ουσιαστικά ό, τι
έχουμε να κάνουμε εδώ,

265
00:12:38,150 --> 00:12:40,050
και πρέπει να βρούμε το δεύτερο στοιχείο.

266
00:12:40,050 --> 00:12:43,540
Τελικά ότι θα γίνει ο νέος
το κεφάλι αφού διαγράψετε το πρώτο.

267
00:12:43,540 --> 00:12:47,300
Γι 'αυτό ακριβώς πρέπει να ξεκινήσουμε από
η αρχή, να προχωρήσουμε προς τα εμπρός ένα.

268
00:12:47,300 --> 00:12:50,340
Μόλις έχουμε μια λαβή σε ένα
προς τα εμπρός για το πού βρισκόμαστε σήμερα

269
00:12:50,340 --> 00:12:53,850
Δεν μπορούμε να διαγράψετε το πρώτο με ασφάλεια
και στη συνέχεια μπορούμε να προχωρήσουμε μόνο το κεφάλι

270
00:12:53,850 --> 00:12:57,150
να υποδείξει ποια ήταν η
δεύτερη θητεία και στη συνέχεια, τώρα

271
00:12:57,150 --> 00:12:59,170
είναι το πρώτο μετά από αυτό
κόμβος να έχει διαγραφεί.

272
00:12:59,170 --> 00:13:01,160
>> Έτσι και πάλι, ρίχνοντας μια ματιά
σε αυτό ως ένα διάγραμμα που

273
00:13:01,160 --> 00:13:05,022
Θέλετε να σκάσει τώρα μια
στοιχείο εκτός αυτής της στοίβας.

274
00:13:05,022 --> 00:13:05,730
Λοιπόν, τι θα κάνουμε;

275
00:13:05,730 --> 00:13:08,188
Καλά είμαστε πρώτα πρόκειται να δημιουργήσουμε
ένα νέο δείκτη που πρόκειται

276
00:13:08,188 --> 00:13:10,940
ώστε να παραπέμπει στο ίδιο σημείο με το κεφάλι.

277
00:13:10,940 --> 00:13:13,790
Εμείς πάμε για να το μετακινήσετε μία θέση
προς τα εμπρός λέγοντας ίσων Trav

278
00:13:13,790 --> 00:13:17,510
Trav επόμενο, για παράδειγμα, η οποία
θα προωθήσει το δείκτη Trav ένα

279
00:13:17,510 --> 00:13:19,324
θέση προς τα εμπρός.

280
00:13:19,324 --> 00:13:21,240
Τώρα που έχουμε μια
κρατήστε το πρώτο στοιχείο

281
00:13:21,240 --> 00:13:24,573
μέσω του δείκτη που ονομάζεται λίστα, και η
δεύτερο στοιχείο μέσω ενός δείκτη που ονομάζεται

282
00:13:24,573 --> 00:13:28,692
Trav, μπορούμε να διαγράψετε με ασφάλεια ότι
πρώτο στοιχείο από τη στοίβα

283
00:13:28,692 --> 00:13:30,650
χωρίς να χάσει το υπόλοιπο
της αλυσίδας, επειδή

284
00:13:30,650 --> 00:13:32,358
έχουν έναν τρόπο να αναφερθώ
με το δεύτερο στοιχείο

285
00:13:32,358 --> 00:13:34,780
διαβιβάζει μέσω του
δείκτη που ονομάζεται Trav.

286
00:13:34,780 --> 00:13:37,100
>> Έτσι τώρα μπορούμε να ελευθερώσουμε αυτόν τον κόμβο.

287
00:13:37,100 --> 00:13:38,404
Μπορούμε να απελευθερώσει λίστα.

288
00:13:38,404 --> 00:13:41,320
Και τότε το μόνο που πρέπει να κάνουμε τώρα είναι
Λίστα κινηθεί προς το σημείο στην ίδια θέση

289
00:13:41,320 --> 00:13:44,482
Trav ότι κάνει, και είμαστε είδος πίσω
όπου ξεκινήσαμε πριν πιέσαμε 12

290
00:13:44,482 --> 00:13:45,690
σχετικά με στην πρώτη θέση, δεξιά.

291
00:13:45,690 --> 00:13:46,940
Αυτό είναι ακριβώς εκεί που ήμασταν.

292
00:13:46,940 --> 00:13:48,840
Είχαμε αυτή την στοίβα τεσσάρων στοιχείων.

293
00:13:48,840 --> 00:13:49,690
Προσθέσαμε ένα πέμπτο.

294
00:13:49,690 --> 00:13:51,910
Προωθήσαμε το ένα πέμπτο
στοιχείο και, στη συνέχεια εμείς

295
00:13:51,910 --> 00:13:55,980
έσκασε το ότι πρόσφατα
προστίθεται το στοιχείο πίσω μακριά.

296
00:13:55,980 --> 00:13:58,816
>> Αυτό είναι πραγματικά λίγο πολύ
όλα είναι εκεί για να στοίβες.

297
00:13:58,816 --> 00:14:00,190
Μπορείτε να τα εφαρμόσουν ως πίνακες.

298
00:14:00,190 --> 00:14:01,815
Μπορείτε να τα εφαρμόσουν ως συνδεδεμένες λίστες.

299
00:14:01,815 --> 00:14:04,810
Υπάρχουν, φυσικά, άλλες
τρόπους για την εφαρμογή τους, καθώς και.

300
00:14:04,810 --> 00:14:09,060
Βασικά ο λόγος που θα χρησιμοποιήσετε
στοίβες είναι να διατηρήσει τα δεδομένα με τέτοιο τρόπο

301
00:14:09,060 --> 00:14:12,090
ότι τα πιο πρόσφατα προστέθηκε
στοιχείο είναι το πρώτο πράγμα είμαστε

302
00:14:12,090 --> 00:14:14,980
πρόκειται να θέλουν να πάρουν πίσω.

303
00:14:14,980 --> 00:14:17,900
Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.

304
00:14:17,900 --> 00:14:19,926