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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Okay,
så ved dette punkt, du er

3
00:00:05,990 --> 00:00:09,020
sandsynligvis temmelig bekendt
med arrays og hægtede lister

4
00:00:09,020 --> 00:00:10,950
som er de to primære
datastrukturer vi har

5
00:00:10,950 --> 00:00:16,810
talte om for at holde sæt
data af tilsvarende datatyper organiseret.

6
00:00:16,810 --> 00:00:19,080
>> Nu vil vi tale
om et par variationer

7
00:00:19,080 --> 00:00:20,330
på arrays og hægtede lister.

8
00:00:20,330 --> 00:00:22,362
I denne video vil vi
at tale om stakke.

9
00:00:22,362 --> 00:00:25,320
Konkret vil vi tale
om en datastruktur kaldes en stabel.

10
00:00:25,320 --> 00:00:28,510
Recall fra tidligere diskussioner
om pointere og hukommelse,

11
00:00:28,510 --> 00:00:32,060
at stakken er også
navn for et segment af hukommelse

12
00:00:32,060 --> 00:00:34,980
hvor statisk erklæret
memory-- hukommelse, som du

13
00:00:34,980 --> 00:00:38,730
navn, variabler, som du nævne, et
cetera og funktion rammer, som vi også

14
00:00:38,730 --> 00:00:41,000
findes call stack rammer.

15
00:00:41,000 --> 00:00:45,421
Så dette er en stak datastruktur
ikke en stabel segment af hukommelse.

16
00:00:45,421 --> 00:00:45,920
OK.

17
00:00:45,920 --> 00:00:46,890
>> Men hvad er en stak?

18
00:00:46,890 --> 00:00:49,220
Så det er temmelig meget bare en
særlig form for struktur

19
00:00:49,220 --> 00:00:51,190
der vedligeholder data på en organiseret måde.

20
00:00:51,190 --> 00:00:53,760
Og der er to meget
almindelige måder at implementere

21
00:00:53,760 --> 00:00:57,380
stakke ved hjælp af data to strukturer
at vi er allerede er bekendt med,

22
00:00:57,380 --> 00:01:00,340
arrays og hægtede lister.

23
00:01:00,340 --> 00:01:04,430
Hvad gør en stak særlige er
måde, hvorpå vi lægge oplysninger

24
00:01:04,430 --> 00:01:08,200
ind i stakken, og den måde, vi
fjerne oplysninger fra stakken.

25
00:01:08,200 --> 00:01:11,600
Navnlig med stakke
reglen er kun de mest

26
00:01:11,600 --> 00:01:15,830
nylig tilføjet element kan fjernes.

27
00:01:15,830 --> 00:01:17,660
>> Så tænk over det, som om det er en stak.

28
00:01:17,660 --> 00:01:21,170
Vi hober oplysninger
oven på sig selv,

29
00:01:21,170 --> 00:01:24,271
og kun de ting i toppen
af bunken kan fjernes.

30
00:01:24,271 --> 00:01:27,020
Vi kan ikke fjerne ting nedenunder
fordi alt andet ville

31
00:01:27,020 --> 00:01:28,020
sammenbrud og vælter.

32
00:01:28,020 --> 00:01:32,580
Så vi virkelig er ved at opbygge en stak, der
vi så nødt til at fjerne stykke for stykke.

33
00:01:32,580 --> 00:01:36,590
På grund af dette, vi almindeligvis henvise
til en stak som LIFO struktur,

34
00:01:36,590 --> 00:01:38,940
sidste ind, først ud.

35
00:01:38,940 --> 00:01:42,290
LIFO, sidste ind, først ud.

36
00:01:42,290 --> 00:01:45,635
>> Så på grund af denne begrænsning på
hvordan information kan føjes til

37
00:01:45,635 --> 00:01:49,080
og fjernet fra en stak, er der virkelig
kun to ting, vi kan gøre med en stak.

38
00:01:49,080 --> 00:01:52,010
Vi kan skubbe, som er
Udtrykket vi bruger til at tilføje

39
00:01:52,010 --> 00:01:55,130
et nyt element til toppen af
stak, eller hvis stakken ikke findes

40
00:01:55,130 --> 00:01:58,550
og vi er ved at oprette det fra bunden,
skabe stablen i første omgang

41
00:01:58,550 --> 00:02:00,110
ville være at skubbe.

42
00:02:00,110 --> 00:02:04,990
Og derefter pop, det er den slags CS
sigt, vi bruger til at fjerne den senest

43
00:02:04,990 --> 00:02:08,330
yderligere element fra toppen af ​​stakken.

44
00:02:08,330 --> 00:02:11,130
>> Så vi kommer til at se på både
implementeringer, både matrix baseret

45
00:02:11,130 --> 00:02:13,120
og knyttet liste baseret på.

46
00:02:13,120 --> 00:02:14,870
Og vi kommer til at
starte med matrix baseret.

47
00:02:14,870 --> 00:02:19,990
Så her er den grundlæggende idé om, hvad
array baseret stabel datastruktur

48
00:02:19,990 --> 00:02:21,140
ville se ud.

49
00:02:21,140 --> 00:02:23,740
Vi har en indtastet definition her.

50
00:02:23,740 --> 00:02:27,790
Inde i at vi har to medlemmer
eller felter af strukturen.

51
00:02:27,790 --> 00:02:29,880
Vi har et array.

52
00:02:29,880 --> 00:02:32,400
Og igen Jeg bruger
vilkårlig datatype værdi.

53
00:02:32,400 --> 00:02:35,180
>> Så dette kunne være en hvilken som helst datatype,
int char eller anden data

54
00:02:35,180 --> 00:02:37,080
type du tidligere har oprettet.

55
00:02:37,080 --> 00:02:39,861
Så vi har en bred vifte af størrelse kapacitet.

56
00:02:39,861 --> 00:02:44,010
Kapacitet, der er et pund defineret konstant,
måske et andet sted i vores fil.

57
00:02:44,010 --> 00:02:47,550
Så mærke allerede med denne særlige
gennemførelse vi afgrænser

58
00:02:47,550 --> 00:02:49,800
os selv som var typisk
tilfældet med arrays,

59
00:02:49,800 --> 00:02:53,170
som vi ikke kan dynamisk ændre størrelse,
hvor der er et vist antal

60
00:02:53,170 --> 00:02:55,450
af den maksimale elementer,
vi kan sætte i vores stak.

61
00:02:55,450 --> 00:02:57,930
I dette tilfælde er det kapacitet elementer.

62
00:02:57,930 --> 00:03:00,310
>> Vi holder også styr på
toppen af ​​stakken.

63
00:03:00,310 --> 00:03:04,350
Hvilket element er den mest
for nylig tilføjet til stakken?

64
00:03:04,350 --> 00:03:07,470
Og så vi holde styr på det
i en variabel kaldet toppen.

65
00:03:07,470 --> 00:03:11,692
Og alt dette bliver pakket op sammen
i en ny datatype kaldes en stabel.

66
00:03:11,692 --> 00:03:13,400
Og når vi er skabt
denne nye datatype

67
00:03:13,400 --> 00:03:15,410
vi kan behandle det som
enhver anden datatype.

68
00:03:15,410 --> 00:03:20,970
Vi kan erklære stak s, ligesom
vi kunne gøre int x, eller char y.

69
00:03:20,970 --> 00:03:22,990
Og når vi siger stable
s, godt, hvad der sker

70
00:03:22,990 --> 00:03:26,420
er vi får et sæt
hukommelse afsat til os.

71
00:03:26,420 --> 00:03:28,770
>> I dette tilfælde kapacitet
Jeg har åbenbart besluttet

72
00:03:28,770 --> 00:03:33,470
er 10, fordi jeg har en
enkelt variabel af typen stack

73
00:03:33,470 --> 00:03:35,320
som indeholder to felter huske.

74
00:03:35,320 --> 00:03:38,330
Et array, i dette tilfælde vil
at være et array af heltal

75
00:03:38,330 --> 00:03:40,440
som det er tilfældet i de fleste af mine eksempler.

76
00:03:40,440 --> 00:03:43,996
Og en anden heltalsvariabel
stand til at lagre toppen,

77
00:03:43,996 --> 00:03:45,870
den senest tilføjede
element til stakken.

78
00:03:45,870 --> 00:03:50,290
Så en enkelt stak af det, vi
netop definerede ligner dette.

79
00:03:50,290 --> 00:03:53,190
Det er en boks, der indeholder
et array af 10 hvad

80
00:03:53,190 --> 00:03:57,280
vil være heltal i denne sag, og
anden heltalsvariabel der i grøn

81
00:03:57,280 --> 00:04:00,010
at angive toppen af ​​stakken.

82
00:04:00,010 --> 00:04:02,600
>> For at indstille toppen af
stak vi bare sige s.top.

83
00:04:02,600 --> 00:04:04,890
Det er, hvordan vi adgang til en
inden for en struktur tilbagekaldelse.

84
00:04:04,890 --> 00:04:10,460
s.top lig 0 effektivt
gør dette til vores stack.

85
00:04:10,460 --> 00:04:12,960
Så igen har vi to operationer
at vi kan udføre nu.

86
00:04:12,960 --> 00:04:14,270
Vi kan skubbe, og vi kan pop.

87
00:04:14,270 --> 00:04:15,635
Lad os starte med push.

88
00:04:15,635 --> 00:04:18,260
Igen, skubber tilføjer en ny
element til toppen af ​​stakken.

89
00:04:18,260 --> 00:04:21,460
>> Så hvad skal vi gøre i
dette array baseret implementering?

90
00:04:21,460 --> 00:04:23,210
Tja generelt
push-funktion går

91
00:04:23,210 --> 00:04:26,160
få brug for at acceptere en
pointer til stakken.

92
00:04:26,160 --> 00:04:28,610
Nu tager en anden og tænke over det.

93
00:04:28,610 --> 00:04:32,840
Hvorfor skulle vi vil acceptere
en pointer til stakken?

94
00:04:32,840 --> 00:04:36,830
Recall fra tidligere videoer på
variabel rækkevidde og pointere,

95
00:04:36,830 --> 00:04:42,350
hvad der ville ske, hvis vi lige har sendt
stakken, s snarere som en parameter?

96
00:04:42,350 --> 00:04:45,770
Hvad ville der egentlig være bestået derinde?

97
00:04:45,770 --> 00:04:49,430
Husk at vi er ved at oprette en kopi
når vi videregive det til en funktion

98
00:04:49,430 --> 00:04:51,160
medmindre vi bruger pointere.

99
00:04:51,160 --> 00:04:55,380
Og så denne funktion skubbe behov
at acceptere en pegepind til stakken

100
00:04:55,380 --> 00:04:59,160
så at vi faktisk ændrer
stakken vi agter at ændre.

101
00:04:59,160 --> 00:05:03,060
>> Den anden ting skub sandsynligvis vil
acceptere, er en dataelement af typen værdi.

102
00:05:03,060 --> 00:05:06,970
I dette tilfælde igen, et heltal, der
vi kommer til at føje til toppen af ​​stakken.

103
00:05:06,970 --> 00:05:08,680
Så vi har fået vores to parametre.

104
00:05:08,680 --> 00:05:11,310
Hvad skal vi
nu gøre inde push?

105
00:05:11,310 --> 00:05:14,860
Nå, simpelthen, vi bare kommer til at tilføje
dette element til toppen af ​​stablen

106
00:05:14,860 --> 00:05:22,860
og derefter ændre hvor toppen af
stakken er, at s dot top værdi.

107
00:05:22,860 --> 00:05:25,639
Så dette er, hvad en funktion
angivelse til tryk

108
00:05:25,639 --> 00:05:27,680
kan se ud i en
matrix-baseret implementering.

109
00:05:27,680 --> 00:05:30,967
>> Igen dette er ikke en ufravigelig regel
at du kunne ændre dette og har

110
00:05:30,967 --> 00:05:32,050
Det varierer på forskellige måder.

111
00:05:32,050 --> 00:05:33,840
Måske s erklæres globalt.

112
00:05:33,840 --> 00:05:36,180
Og så du behøver ikke engang
at passere det er som en parameter.

113
00:05:36,180 --> 00:05:39,125
Dette er igen blot en
generel tilfældet for push.

114
00:05:39,125 --> 00:05:41,000
Og der er forskellige
måder at gennemføre den.

115
00:05:41,000 --> 00:05:42,810
Men i dette tilfælde vores
skub kommer til at tage

116
00:05:42,810 --> 00:05:48,540
to argumenter, en pointer til en stak og
en dataelement af typen værdi, heltal

117
00:05:48,540 --> 00:05:49,840
I dette tilfælde.

118
00:05:49,840 --> 00:05:52,100
>> Så vi erklærede s, vi
nævnte s.top lig 0.

119
00:05:52,100 --> 00:05:55,969
Lad os nu skubbe
nummer 28 på stablen.

120
00:05:55,969 --> 00:05:57,010
Nå hvad betyder det?

121
00:05:57,010 --> 00:05:59,600
Godt øjeblikket
toppen af ​​stakken er 0.

122
00:05:59,600 --> 00:06:01,350
Og så hvad er dybest set
kommer til at ske, er

123
00:06:01,350 --> 00:06:05,820
vi kommer til at holde antallet
28 ind matrix placering 0.

124
00:06:05,820 --> 00:06:09,540
Temmelig ligetil, højre, at
var den øverste, og nu vi er gode til at gå.

125
00:06:09,540 --> 00:06:12,910
Og så er vi nødt til at ændre, hvad
toppen af ​​stakken bliver.

126
00:06:12,910 --> 00:06:15,130
Således at næste gang
vi skubber et element i,

127
00:06:15,130 --> 00:06:18,017
vi kommer til at gemme det i
matrix placering, sandsynligvis ikke 0.

128
00:06:18,017 --> 00:06:20,100
Vi ønsker ikke at overskrive
hvad vi bare sætte der.

129
00:06:20,100 --> 00:06:23,510
Og så vi vil bare flytte toppen til 1.

130
00:06:23,510 --> 00:06:24,890
Det sandsynligvis giver mening.

131
00:06:24,890 --> 00:06:28,940
>> Nu, hvis vi ønsker at sætte et andet element
på stakken, siger vi ønsker at presse 33,

132
00:06:28,940 --> 00:06:33,190
godt nu vi bare kommer til at tage 33
og sætte det på matrix placering nummer

133
00:06:33,190 --> 00:06:37,580
1, og derefter ændre øverst på vores
stable at være matrix placering nummer to.

134
00:06:37,580 --> 00:06:40,650
Så hvis næste gang vi ønsker at
skubbe et element på stakken,

135
00:06:40,650 --> 00:06:43,087
det vil blive sat i matrix placering 2.

136
00:06:43,087 --> 00:06:44,420
Og lad os gøre det en gang mere.

137
00:06:44,420 --> 00:06:45,753
Vi vil skubbe 19 ud af stakkene.

138
00:06:45,753 --> 00:06:48,940
Vi vil sætte 19 i matrix placering 2
og ændre øverst på vores stack

139
00:06:48,940 --> 00:06:51,220
at være matrix Sted 3
så hvis næste gang vi

140
00:06:51,220 --> 00:06:54,780
nødt til at gøre en push vi er gode til at gå.

141
00:06:54,780 --> 00:06:56,980
>> OK, så der er skubber i en nøddeskal.

142
00:06:56,980 --> 00:06:57,830
Hvad med popping?

143
00:06:57,830 --> 00:07:00,240
Så popping er den slags
modstykke til at skubbe.

144
00:07:00,240 --> 00:07:02,720
Det er, hvordan vi fjerne data fra stakken.

145
00:07:02,720 --> 00:07:04,610
Og generelt pop behov
at gøre følgende.

146
00:07:04,610 --> 00:07:07,600
Det har brug for at acceptere en pointer til den
stak, igen i det generelle tilfælde.

147
00:07:07,600 --> 00:07:10,480
I visse andre tilfælde du måske
har erklæret stakken globalt,

148
00:07:10,480 --> 00:07:13,910
i hvilket tilfælde du ikke behøver at passere det
i, fordi det allerede har adgang til det

149
00:07:13,910 --> 00:07:15,541
som en global variabel.

150
00:07:15,541 --> 00:07:17,040
Men hvad skal vi gøre?

151
00:07:17,040 --> 00:07:21,000
Nå vi forøgelse
toppen af ​​stakken i tryk,

152
00:07:21,000 --> 00:07:24,050
så vi sandsynligvis vil ønsker
for at mindske toppen af ​​stablen

153
00:07:24,050 --> 00:07:25,009
i pop, ikke?

154
00:07:25,009 --> 00:07:26,800
Og så selvfølgelig
vi også vil ønsker

155
00:07:26,800 --> 00:07:29,240
at returnere værdien at vi fjerner.

156
00:07:29,240 --> 00:07:32,125
Hvis vi tilføjer elementer, vi ønsker
at få elementer ud senere,

157
00:07:32,125 --> 00:07:34,000
vi sandsynligvis faktisk
ønsker at gemme dem, så vi

158
00:07:34,000 --> 00:07:36,490
ikke bare slette dem fra
stable og derefter gøre noget med dem.

159
00:07:36,490 --> 00:07:38,500
Generelt hvis vi er
skubber og knaldende her

160
00:07:38,500 --> 00:07:41,250
vi ønsker at gemme denne
oplysninger på en meningsfuld måde

161
00:07:41,250 --> 00:07:43,250
og så betyder det ikke gør
mening at bare kassere det.

162
00:07:43,250 --> 00:07:46,380
Så denne funktion bør
sandsynligvis vende tilbage en værdi for os.

163
00:07:46,380 --> 00:07:51,040
>> Så dette er, hvad en angivelse til pop
kan se ud der øverst til venstre.

164
00:07:51,040 --> 00:07:53,870
Denne funktion returnerer
data af typen værdi.

165
00:07:53,870 --> 00:07:56,320
Igen vi har været ved hjælp af
heltal overalt.

166
00:07:56,320 --> 00:08:01,916
Og det accepterer en pointer til en stak som
dens eneste argument eller tunge parameter.

167
00:08:01,916 --> 00:08:03,040
Så hvad der pop kommer til at gøre?

168
00:08:03,040 --> 00:08:07,990
Lad os sige, at vi ønsker at nu
pop et element ud af s.

169
00:08:07,990 --> 00:08:14,000
Så husk jeg sagde, at stakke er sidste
ind, først ud, LIFO datastrukturer.

170
00:08:14,000 --> 00:08:17,855
Hvilket element vil
fjernes fra stablen?

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

172
00:08:21,780 --> 00:08:24,150
Vidste du gætte 19?

173
00:08:24,150 --> 00:08:25,290
Fordi du ville være rigtigt.

174
00:08:25,290 --> 00:08:28,836
19 var den sidste element, vi føjet til
stable da vi skubber elementer,

175
00:08:28,836 --> 00:08:31,210
og så det kommer til den første
element, der bliver fjernet.

176
00:08:31,210 --> 00:08:34,780
Det er, som om vi sagde 28, og
så vi sætter 33 på toppen af ​​det,

177
00:08:34,780 --> 00:08:36,659
og vi sætter 19 oven i købet.

178
00:08:36,659 --> 00:08:40,650
19. Det eneste element, vi kan tage off er

179
00:08:40,650 --> 00:08:45,019
>> Nu i diagrammet her hvad jeg har gjort
er slags slettet 19 fra arrayet.

180
00:08:45,019 --> 00:08:46,810
Det er faktisk ikke
hvad vi skal gøre.

181
00:08:46,810 --> 00:08:48,934
Vi bare at slags
af lade som om det ikke er der.

182
00:08:48,934 --> 00:08:51,441
Det er stadig der i
at hukommelsen placering,

183
00:08:51,441 --> 00:08:54,190
men vi bare at ignorere det
ved at ændre øverst på vores stack

184
00:08:54,190 --> 00:08:56,080
fra at være 3 til 2.

185
00:08:56,080 --> 00:08:58,720
Så hvis vi skulle nu skubbe
et andet element på stakken,

186
00:08:58,720 --> 00:09:00,720
det ville i løbet skrive 19.

187
00:09:00,720 --> 00:09:03,990
>> Men lad os ikke gå gennem den ulejlighed
at slette 19 fra stablen.

188
00:09:03,990 --> 00:09:05,830
Vi kan bare lade som om det ikke er der.

189
00:09:05,830 --> 00:09:11,107
Med henblik på stakken det er gået, hvis
vi ændre toppen til 2 i stedet for 3.

190
00:09:11,107 --> 00:09:12,690
Okay, så det var temmelig meget det.

191
00:09:12,690 --> 00:09:15,080
Det er alt, vi skal gøre
til pop et element fra.

192
00:09:15,080 --> 00:09:16,090
Lad os gøre det igen.

193
00:09:16,090 --> 00:09:18,610
Så jeg har fremhævet det i rødt her til
angiver vi gør et andet opkald.

194
00:09:18,610 --> 00:09:19,720
Vi kommer til at gøre det samme.

195
00:09:19,720 --> 00:09:20,803
>> Så hvad der vil ske?

196
00:09:20,803 --> 00:09:23,670
Nå, vi kommer til at gemme
33 i x- og vi vil

197
00:09:23,670 --> 00:09:26,217
at ændre toppen af ​​stakken til 1.

198
00:09:26,217 --> 00:09:29,050
Så hvis vi nu til at skubbe en
element i stakken, som vi er

199
00:09:29,050 --> 00:09:31,610
kommer til at gøre lige nu,
hvad der kommer til at ske

200
00:09:31,610 --> 00:09:36,367
er vi vil overskrive
vifte placering nummer 1.

201
00:09:36,367 --> 00:09:38,950
Således at 33 der var slags venstre
bag at vi bare lod

202
00:09:38,950 --> 00:09:44,390
ikke er der længere, vi bare
at tæske det og sætte 40 der i stedet.

203
00:09:44,390 --> 00:09:46,290
Og så selvfølgelig,
da vi gjorde et skub,

204
00:09:46,290 --> 00:09:48,780
vi kommer til at øge den
toppen af ​​stakken fra 1 til 2

205
00:09:48,780 --> 00:09:50,950
så hvis vi nu føje
et andet element det vil

206
00:09:50,950 --> 00:09:54,700
gå ind matrix placering nummer to.

207
00:09:54,700 --> 00:09:57,590
>> Nu hægtede lister er en anden
måde at gennemføre stakke.

208
00:09:57,590 --> 00:10:01,210
Og hvis denne definition på
skærmen her ser bekendt for dig,

209
00:10:01,210 --> 00:10:04,260
det er fordi det ser næsten
nøjagtigt det samme, i virkeligheden,

210
00:10:04,260 --> 00:10:07,790
det temmelig meget er præcis den
samme som en enkelt bundet liste,

211
00:10:07,790 --> 00:10:11,990
hvis du husker fra vores diskussion af
enkeltvis forbundet lister i en anden video.

212
00:10:11,990 --> 00:10:15,510
Den eneste begrænsning her
er for os som programmører,

213
00:10:15,510 --> 00:10:17,900
vi ikke lov til at
indsætte eller slette tilfældigt

214
00:10:17,900 --> 00:10:20,620
fra enkelt bundet liste
som vi tidligere kunne gøre.

215
00:10:20,620 --> 00:10:25,820
Vi kan kun nu indsætte og slette fra
forsiden eller toppen af ​​den linkede

216
00:10:25,820 --> 00:10:26,320
listen.

217
00:10:26,320 --> 00:10:28,028
Det er virkelig den eneste
forskel selv.

218
00:10:28,028 --> 00:10:29,700
Dette er ellers et enkelt bundet listen.

219
00:10:29,700 --> 00:10:32,060
Det er kun den begrænsning
udskiftning på os selv

220
00:10:32,060 --> 00:10:35,770
som programmører, der
ændrer det til en stabel.

221
00:10:35,770 --> 00:10:39,280
>> Reglen her er altid at opretholde en
pointer til lederen af ​​en linket liste.

222
00:10:39,280 --> 00:10:41,520
Dette er naturligvis en generelt
vigtig regel først.

223
00:10:41,520 --> 00:10:44,260
For enkeltvis sammenkædet liste alligevel du
behøver kun en pointer til hovedet

224
00:10:44,260 --> 00:10:46,160
med henblik på at få det
kæde kunne henvise

225
00:10:46,160 --> 00:10:48,596
til alle andre elementer
i den linkede liste.

226
00:10:48,596 --> 00:10:50,470
Men det er især
vigtigt med en stak.

227
00:10:50,470 --> 00:10:52,386
Og så generelt er du
vil rent faktisk ønsker

228
00:10:52,386 --> 00:10:54,090
denne pegepind til at være en global variabel.

229
00:10:54,090 --> 00:10:56,574
Det er nok at gå til
være endnu nemmere på den måde.

230
00:10:56,574 --> 00:10:58,240
Så hvad er analoger af skub og pop?

231
00:10:58,240 --> 00:10:58,740
Højre.

232
00:10:58,740 --> 00:11:01,812
Så skubber igen tilføjer
et nyt element til stakken.

233
00:11:01,812 --> 00:11:03,770
I en sammenkædet liste,
betyder, at vi er nødt til

234
00:11:03,770 --> 00:11:07,770
at oprette en ny knude, at vi er
kommer til at tilføje i linkede liste,

235
00:11:07,770 --> 00:11:10,500
og følg derefter forsigtige skridt
at vi har skitseret tidligere

236
00:11:10,500 --> 00:11:16,050
i enkeltvis hægtede lister at føje den til
kæden uden at bryde kæden

237
00:11:16,050 --> 00:11:18,900
og miste eller forældreløse enhver
elementer i den linkede liste.

238
00:11:18,900 --> 00:11:21,820
Og det er dybest set, hvad der
lille klat af tekst der opsummerer.

239
00:11:21,820 --> 00:11:23,740
Og lad os tage et kig
på det som et diagram.

240
00:11:23,740 --> 00:11:24,823
>> Så her er vores linkede liste.

241
00:11:24,823 --> 00:11:26,620
Det samtidigt indeholder fire elementer.

242
00:11:26,620 --> 00:11:30,420
Og mere perfekt her er vores
stak indeholder fire elementer.

243
00:11:30,420 --> 00:11:36,030
Og lad os sige, at vi nu ønsker at
skubbe en ny post på denne stak.

244
00:11:36,030 --> 00:11:39,792
Og vi ønsker at skubbe en ny
post, hvis data værdi 12.

245
00:11:39,792 --> 00:11:41,000
Nå, hvad skal vi gøre?

246
00:11:41,000 --> 00:11:43,420
Nå først vil vi
malloc plads, dynamisk

247
00:11:43,420 --> 00:11:45,411
allokere plads til en ny node.

248
00:11:45,411 --> 00:11:48,160
Og selvfølgelig umiddelbart efter
Vi foretage et opkald til malloc vi altid

249
00:11:48,160 --> 00:11:52,989
Sørg for at tjekke for null,
for hvis vi fik nul tilbage

250
00:11:52,989 --> 00:11:54,280
der var en slags problem.

251
00:11:54,280 --> 00:11:57,570
Vi ønsker ikke at dereference at null
pointer eller du vil lide en seg fejl.

252
00:11:57,570 --> 00:11:58,510
Det er ikke godt.

253
00:11:58,510 --> 00:11:59,760
Så vi har malloced for knuden.

254
00:11:59,760 --> 00:12:01,260
Vi vil antage, at vi har haft succes her.

255
00:12:01,260 --> 00:12:06,090
Vi kommer til at sætte 12 ind
datafeltet for denne node.

256
00:12:06,090 --> 00:12:11,570
Nu kan du huske hvilke af vores pejlemærker
flytter næste så vi ikke bryder kæden?

257
00:12:11,570 --> 00:12:15,100
Vi har et par muligheder her, men
den eneste, der kommer til at være sikker

258
00:12:15,100 --> 00:12:19,330
er at sætte nyheder næste pointer til
punkt til den gamle leder af listen

259
00:12:19,330 --> 00:12:21,360
eller hvad vil snart være den
gamle leder af listen.

260
00:12:21,360 --> 00:12:23,610
Og nu, at alle vores
elementer er lænket sammen,

261
00:12:23,610 --> 00:12:27,370
Vi kan bare flytte listen til at pege
til det samme sted, som nye gør.

262
00:12:27,370 --> 00:12:33,550
Og vi har nu effektivt skubbet en
nyt element på forsiden af ​​stablen.

263
00:12:33,550 --> 00:12:36,420
>> Til pop vi ønsker blot at
slette det første element.

264
00:12:36,420 --> 00:12:38,150
Og så dybest set, hvad
vi har at gøre her,

265
00:12:38,150 --> 00:12:40,050
godt vi nødt til at finde det andet element.

266
00:12:40,050 --> 00:12:43,540
Til sidst, som vil blive den nye
hovedet efter vi sletter den første.

267
00:12:43,540 --> 00:12:47,300
Så vi bare nødt til at starte fra
begyndelsen, flytte en fremad.

268
00:12:47,300 --> 00:12:50,340
Når vi har fået fat på en
foran hvor vi i øjeblikket

269
00:12:50,340 --> 00:12:53,850
er vi kan slette den første sikkert
og så kan vi bare flytte hovedet

270
00:12:53,850 --> 00:12:57,150
til at pege på, hvad der var den
anden periode og derefter nu

271
00:12:57,150 --> 00:12:59,170
er det første, efter at
node er blevet slettet.

272
00:12:59,170 --> 00:13:01,160
>> Så igen, at tage et kig
på det som et diagram, vi

273
00:13:01,160 --> 00:13:05,022
vil nu pop en
element ud af denne stak.

274
00:13:05,022 --> 00:13:05,730
Så hvad gør vi?

275
00:13:05,730 --> 00:13:08,188
Nå vi først kommer til at skabe
en ny pointer, der kommer

276
00:13:08,188 --> 00:13:10,940
til at pege på det samme sted som leder.

277
00:13:10,940 --> 00:13:13,790
Vi kommer til at flytte det en position
frem ved at sige Trav ligemænd

278
00:13:13,790 --> 00:13:17,510
trav næste for eksempel, som
ville fremme trav pointer én

279
00:13:17,510 --> 00:13:19,324
position fremad.

280
00:13:19,324 --> 00:13:21,240
Nu hvor vi har fået en
hold på det første element

281
00:13:21,240 --> 00:13:24,573
gennem markøren kaldet listen, og
andet element gennem en pegepind kaldes

282
00:13:24,573 --> 00:13:28,692
trav, kan vi roligt slette det
første element fra stakken

283
00:13:28,692 --> 00:13:30,650
uden at miste resten
af kæden, fordi vi

284
00:13:30,650 --> 00:13:32,358
har en måde at henvise
til det andet element

285
00:13:32,358 --> 00:13:34,780
sende ved hjælp af
pointer kaldte trav.

286
00:13:34,780 --> 00:13:37,100
>> Så nu kan vi frigøre denne node.

287
00:13:37,100 --> 00:13:38,404
Vi kan frigøre listen.

288
00:13:38,404 --> 00:13:41,320
Og så alt vi skal gøre nu, er
flytte listen til punkt til det samme sted

289
00:13:41,320 --> 00:13:44,482
at trav gør, og vi er en slags tilbage
hvor vi startede, før vi pressede 12

290
00:13:44,482 --> 00:13:45,690
på i første omgang, højre.

291
00:13:45,690 --> 00:13:46,940
Dette er præcis, hvor vi var.

292
00:13:46,940 --> 00:13:48,840
Vi havde denne fire element stak.

293
00:13:48,840 --> 00:13:49,690
Vi har tilføjet en femtedel.

294
00:13:49,690 --> 00:13:51,910
Vi pressede en femtedel
element, og så vi

295
00:13:51,910 --> 00:13:55,980
dukkede der senest
yderligere element tilbage fra.

296
00:13:55,980 --> 00:13:58,816
>> Det er virkelig temmelig meget
alt hvad der er at stakke.

297
00:13:58,816 --> 00:14:00,190
Du kan implementere dem som arrays.

298
00:14:00,190 --> 00:14:01,815
Du kan implementere dem som hægtede lister.

299
00:14:01,815 --> 00:14:04,810
Der er naturligvis andre
måder at gennemføre dem så godt.

300
00:14:04,810 --> 00:14:09,060
Dybest set årsagen til at vi ville bruge
stakke er at vedligeholde data på en sådan måde

301
00:14:09,060 --> 00:14:12,090
at den mest nylig tilføjet
element er den første ting, vi er

302
00:14:12,090 --> 00:14:14,980
lyst til at komme tilbage.

303
00:14:14,980 --> 00:14:17,900
Jeg er Doug Lloyd, det er CS50.

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