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

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

3
00:00:05,990 --> 00:00:09,020
sannsynligvis ganske kjent
med arrays og koblede lister

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

5
00:00:10,950 --> 00:00:16,810
snakket om for å holde sett
data av tilsvarende datatyper organisert.

6
00:00:16,810 --> 00:00:19,080
>> Nå skal vi snakke
om et par varianter

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

8
00:00:20,330 --> 00:00:22,362
I denne videoen skal vi
å snakke om stabler.

9
00:00:22,362 --> 00:00:25,320
Spesielt vi kommer til å snakke
om en datastruktur kalt en stabel.

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

11
00:00:28,510 --> 00:00:32,060
at bunken er også
nevne for et segment av minne

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

13
00:00:34,980 --> 00:00:38,730
navn, variabler som du navn, et
cetera og funksjonsrammer som vi også

14
00:00:38,730 --> 00:00:41,000
kallstakken rammer eksisterer.

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

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

17
00:00:45,920 --> 00:00:46,890
>> Men hva er en stabel?

18
00:00:46,890 --> 00:00:49,220
Så det er ganske mye bare en
spesiell type struktur

19
00:00:49,220 --> 00:00:51,190
som opprettholder data på en organisert måte.

20
00:00:51,190 --> 00:00:53,760
Og det er to svært
vanlige måter å implementere

21
00:00:53,760 --> 00:00:57,380
stabler med to datastrukturer
at vi allerede er kjent med,

22
00:00:57,380 --> 00:01:00,340
arrays og koblede lister.

23
00:01:00,340 --> 00:01:04,430
Hva gjør en stabel spesielt er
Måten vi legger informasjon

24
00:01:04,430 --> 00:01:08,200
i bunken, og måten vi
fjerne informasjon fra bunken.

25
00:01:08,200 --> 00:01:11,600
Spesielt med stabler
regelen er bare de mest

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

27
00:01:15,830 --> 00:01:17,660
>> Så tenk på det som om det er en stabel.

28
00:01:17,660 --> 00:01:21,170
Vi pæling informasjon
på toppen av seg selv,

29
00:01:21,170 --> 00:01:24,271
og bare ting på toppen
av pelen kan fjernes.

30
00:01:24,271 --> 00:01:27,020
Vi kan ikke fjerne noe under
fordi alt annet ville

31
00:01:27,020 --> 00:01:28,020
kollapse og falle over.

32
00:01:28,020 --> 00:01:32,580
Så vi virkelig bygger en stabel som
vi deretter må fjerne bit for bit.

33
00:01:32,580 --> 00:01:36,590
På grunn av dette vi vanligvis omtaler
til en stabel som en LIFO struktur,

34
00:01:36,590 --> 00:01:38,940
sist inn, først ut.

35
00:01:38,940 --> 00:01:42,290
LIFO, sist inn, først ut.

36
00:01:42,290 --> 00:01:45,635
>> Det på grunn av denne begrensning på
Slik informasjon kan legges til

37
00:01:45,635 --> 00:01:49,080
og fjernet fra en stabel, det er egentlig
bare to ting vi kan gjøre med en stack.

38
00:01:49,080 --> 00:01:52,010
Vi kan presse, som er
begrep vi bruker for å legge til

39
00:01:52,010 --> 00:01:55,130
et nytt element til toppen av
stabel, eller dersom stabelen ikke eksisterer

40
00:01:55,130 --> 00:01:58,550
og vi skaper det fra bunnen av,
skape stabelen i første omgang

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

42
00:02:00,110 --> 00:02:04,990
Og så pop, det er den slags CS
Uttrykket vi bruker til å fjerne den sist

43
00:02:04,990 --> 00:02:08,330
lagt element fra toppen av bunken.

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

45
00:02:11,130 --> 00:02:13,120
og lenket liste basert.

46
00:02:13,120 --> 00:02:14,870
Og vi kommer til å
starte med gruppe basert.

47
00:02:14,870 --> 00:02:19,990
Så her er den grunnleggende idé om hva
array basert stabelen datastruktur

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

49
00:02:21,140 --> 00:02:23,740
Vi har et maskinskrevet definisjon her.

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

51
00:02:27,790 --> 00:02:29,880
Vi har en matrise.

52
00:02:29,880 --> 00:02:32,400
Og igjen jeg bruker
vilkårlig datatype verdi.

53
00:02:32,400 --> 00:02:35,180
>> Så dette kan være en hvilken som helst datatype,
int røye eller annen data

54
00:02:35,180 --> 00:02:37,080
skriver du opprettet tidligere.

55
00:02:37,080 --> 00:02:39,861
Så vi har en rekke størrelse kapasitet.

56
00:02:39,861 --> 00:02:44,010
Kapasitet blir et pund definert konstant,
kanskje et annet sted i vår fil.

57
00:02:44,010 --> 00:02:47,550
Så merker allerede med denne
implementering vi byks

58
00:02:47,550 --> 00:02:49,800
oss som var typisk
tilfelle med matriser

59
00:02:49,800 --> 00:02:53,170
som vi ikke kan dynamisk endre størrelse,
hvor det er et visst antall

60
00:02:53,170 --> 00:02:55,450
av elementer maksimale som
vi kan sette i stacken.

61
00:02:55,450 --> 00:02:57,930
I dette tilfellet er det kapasitets elementer.

62
00:02:57,930 --> 00:03:00,310
>> Vi holder også styr på
toppen av bunken.

63
00:03:00,310 --> 00:03:04,350
Hva element er den mest
nylig lagt til stakken?

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

65
00:03:07,470 --> 00:03:11,692
Og alt dette blir pakket sammen
inn i en ny datatype som kalles en stabel.

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

67
00:03:13,400 --> 00:03:15,410
vi kan behandle det som
hvilken som helst annen datatype.

68
00:03:15,410 --> 00:03:20,970
Vi kan erklære stabelen s, akkurat som
vi kunne gjøre int x, eller røye y.

69
00:03:20,970 --> 00:03:22,990
Og når vi sier stable
s, vel hva som skjer

70
00:03:22,990 --> 00:03:26,420
er vi får et sett med
minne satt til side for oss.

71
00:03:26,420 --> 00:03:28,770
>> I dette tilfelle kapasiteten
Jeg har tydeligvis bestemt seg

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

73
00:03:33,470 --> 00:03:35,320
som inneholder to felt huske.

74
00:03:35,320 --> 00:03:38,330
En matrise, i dette tilfellet går
å være en oppstilling av heltall

75
00:03:38,330 --> 00:03:40,440
slik tilfellet er i de fleste av mine eksempler.

76
00:03:40,440 --> 00:03:43,996
Og en annen heltallsvariabelen
som kan lagre den øverste,

77
00:03:43,996 --> 00:03:45,870
den mest nylig lagt
element av stabelen.

78
00:03:45,870 --> 00:03:50,290
Så en enkelt stakk av hva vi
bare definert ser ut som dette.

79
00:03:50,290 --> 00:03:53,190
Det er en boks som inneholder
en rekke 10 hva

80
00:03:53,190 --> 00:03:57,280
vil være heltall i denne saken, og
annen heltallsvariabelen det i grønt

81
00:03:57,280 --> 00:04:00,010
å indikere toppen av bunken.

82
00:04:00,010 --> 00:04:02,600
>> Slik stiller toppen av
stack vi bare si s.top.

83
00:04:02,600 --> 00:04:04,890
Det er hvordan vi tilgang til et
felt av en struktur tilbakekalling.

84
00:04:04,890 --> 00:04:10,460
s.top lik 0 effektivt
gjør dette til vår stabelen.

85
00:04:10,460 --> 00:04:12,960
Så igjen har vi to operasjoner
at vi kan utføre nå.

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

87
00:04:14,270 --> 00:04:15,635
La oss starte med push.

88
00:04:15,635 --> 00:04:18,260
Igjen, presser er å legge til en ny
element til toppen av stabelen.

89
00:04:18,260 --> 00:04:21,460
>> Så hva gjør vi trenger å gjøre i
denne matrisen basert implementering?

90
00:04:21,460 --> 00:04:23,210
Vel generelt
push-funksjonen skal

91
00:04:23,210 --> 00:04:26,160
å trenge å akseptere en
Peker til bunken.

92
00:04:26,160 --> 00:04:28,610
Nå tar en andre og tenke på det.

93
00:04:28,610 --> 00:04:32,840
Hvorfor skulle vi ønske å akseptere
en peker til stakken?

94
00:04:32,840 --> 00:04:36,830
Recall fra tidligere videoer på
variabel omfang og pekere,

95
00:04:36,830 --> 00:04:42,350
hva som ville skje hvis vi bare sendt
stabel, s snarere som en parameter?

96
00:04:42,350 --> 00:04:45,770
Hva ville egentlig bli vedtatt i det?

97
00:04:45,770 --> 00:04:49,430
Husk at vi oppretter en kopi
når vi passerer den til en funksjon

98
00:04:49,430 --> 00:04:51,160
med mindre vi bruker pekere.

99
00:04:51,160 --> 00:04:55,380
Og så denne funksjonen presse behov
å akseptere en peker til stabelen

100
00:04:55,380 --> 00:04:59,160
slik at vi faktisk endring
bunken vi har til hensikt å endre.

101
00:04:59,160 --> 00:05:03,060
>> Den andre tingen presse ønsker sannsynligvis å
godta et dataelement av type verdi.

102
00:05:03,060 --> 00:05:06,970
I dette tilfellet, igjen, er et helt tall som
vi kommer til å legge opp til toppen av bunken.

103
00:05:06,970 --> 00:05:08,680
Så vi har fått våre to parametere.

104
00:05:08,680 --> 00:05:11,310
Hva skal vi
nå gjøre inne av push?

105
00:05:11,310 --> 00:05:14,860
Vel, ganske enkelt, vi bare kommer til å legge
som element til toppen av stabelen

106
00:05:14,860 --> 00:05:22,860
og deretter endre hvor toppen av
stabelen er, som er prikk øverste verdi.

107
00:05:22,860 --> 00:05:25,639
Så dette er hva en funksjon
erklæring for push-

108
00:05:25,639 --> 00:05:27,680
kan se ut i en
matrise-basert implementering.

109
00:05:27,680 --> 00:05:30,967
>> Igjen dette er ikke en fast regel
at du kan endre dette og har

110
00:05:30,967 --> 00:05:32,050
det varierer på forskjellige måter.

111
00:05:32,050 --> 00:05:33,840
Kanskje s er erklært globalt.

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

113
00:05:36,180 --> 00:05:39,125
Dette er igjen bare en
generelle tilfellet for push.

114
00:05:39,125 --> 00:05:41,000
Og det er annerledes
måter å gjennomføre det.

115
00:05:41,000 --> 00:05:42,810
Men i dette tilfellet vår
Push kommer til å ta

116
00:05:42,810 --> 00:05:48,540
to argumenter, en peker til en stabel og
et dataelement av type verdi, heltall

117
00:05:48,540 --> 00:05:49,840
i denne saken.

118
00:05:49,840 --> 00:05:52,100
>> Så vi erklært s, vi
sa s.top lik 0.

119
00:05:52,100 --> 00:05:55,969
Nå la oss presse
nummer 28 på stakken.

120
00:05:55,969 --> 00:05:57,010
Vel hva betyr det?

121
00:05:57,010 --> 00:05:59,600
Vel i dag den
toppen av stabelen er 0.

122
00:05:59,600 --> 00:06:01,350
Og så hva er i utgangspunktet
kommer til å skje er

123
00:06:01,350 --> 00:06:05,820
vi kommer til å holde fast antall
28 i matrisen plassering 0.

124
00:06:05,820 --> 00:06:09,540
Ganske grei, ikke sant, at
var toppen, og nå er vi godt å gå.

125
00:06:09,540 --> 00:06:12,910
Og da må vi endre hva
toppen av bunken vil bli.

126
00:06:12,910 --> 00:06:15,130
Slik at neste gang
vi presse et element i,

127
00:06:15,130 --> 00:06:18,017
vi kommer til å lagre den i
matrise beliggenhet, sannsynligvis ikke er 0.

128
00:06:18,017 --> 00:06:20,100
Vi ønsker ikke å overskrive
hva vi bare satt der.

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

130
00:06:23,510 --> 00:06:24,890
Som sannsynligvis er fornuftig.

131
00:06:24,890 --> 00:06:28,940
>> Nå hvis vi ønsker å sette et annet element
på stakken, si at vi ønsker å presse 33,

132
00:06:28,940 --> 00:06:33,190
vel nå er vi bare nødt til å ta 33
og sette den på rekke plasseringsnummer

133
00:06:33,190 --> 00:06:37,580
1, og deretter endre toppen av vår
stable å være matrisen plassering nummer to.

134
00:06:37,580 --> 00:06:40,650
Så hvis neste gang vi ønsker å
presse et element på stakken,

135
00:06:40,650 --> 00:06:43,087
det vil bli satt i matrise plassering 2.

136
00:06:43,087 --> 00:06:44,420
Og la oss gjøre det en gang til.

137
00:06:44,420 --> 00:06:45,753
Vi skal presse 19 ut av stabler.

138
00:06:45,753 --> 00:06:48,940
Vi setter 19 i matrisen plassering 2
og endre toppen av stacken

139
00:06:48,940 --> 00:06:51,220
å være matrise plassering 3
så hvis neste gang vi

140
00:06:51,220 --> 00:06:54,780
trenger for å gjøre en push vi er godt å gå.

141
00:06:54,780 --> 00:06:56,980
>> OK, så som presser i et nøtteskall.

142
00:06:56,980 --> 00:06:57,830
Hva med dukker?

143
00:06:57,830 --> 00:07:00,240
Så popping er den slags
motstykke til å skyve.

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

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

146
00:07:04,610 --> 00:07:07,600
Det er behov for å akseptere en peker til
stable, igjen i det generelle tilfellet.

147
00:07:07,600 --> 00:07:10,480
I enkelte andre tilfeller kan det være
har erklært stabelen globalt,

148
00:07:10,480 --> 00:07:13,910
I så fall trenger du ikke å passere det
i fordi det allerede har tilgang 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 så hva annet trenger vi å gjøre?

151
00:07:17,040 --> 00:07:21,000
Vel vi ble økes
toppen av stabelen i push,

152
00:07:21,000 --> 00:07:24,050
slik at vi sannsynligvis kommer til å ønske
for å dekrementere toppen av stabelen

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

154
00:07:25,009 --> 00:07:26,800
Og så selvfølgelig
vi også kommer til å ønske

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

156
00:07:29,240 --> 00:07:32,125
Hvis vi legger til elementer, vi ønsker
å få elementer ut senere,

157
00:07:32,125 --> 00:07:34,000
vi sannsynligvis faktisk
ønsker å lagre dem, slik at vi

158
00:07:34,000 --> 00:07:36,490
ikke bare slette dem fra
stable og så gjøre noe med dem.

159
00:07:36,490 --> 00:07:38,500
Vanligvis hvis vi er
presser og spratt her

160
00:07:38,500 --> 00:07:41,250
vi ønsker å lagre denne
informasjon på en meningsfull måte

161
00:07:41,250 --> 00:07:43,250
og så det gjør ikke
fornuftig å bare forkaste det.

162
00:07:43,250 --> 00:07:46,380
Så denne funksjonen bør
trolig returnere en verdi for oss.

163
00:07:46,380 --> 00:07:51,040
>> Så dette er hva en erklæring for pop
kan se ut som det øverst til venstre.

164
00:07:51,040 --> 00:07:53,870
Denne funksjonen returnerer
data av type verdi.

165
00:07:53,870 --> 00:07:56,320
Igjen har vi brukt
heltall hele.

166
00:07:56,320 --> 00:08:01,916
Og den godtar en peker til en stabel som
eget argument eller eneste parameter.

167
00:08:01,916 --> 00:08:03,040
Så hva er pop kommer til å gjøre?

168
00:08:03,040 --> 00:08:07,990
La oss si at vi ønsker å nå
pop et element av av s.

169
00:08:07,990 --> 00:08:14,000
Så husker jeg sa at stabler er siste
inn, først ut, LIFO datastrukturer.

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

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

172
00:08:21,780 --> 00:08:24,150
Visste du gjette 19?

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

174
00:08:25,290 --> 00:08:28,836
19 var den siste element vi satt til
stable når vi var skyve elementer på,

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

176
00:08:31,210 --> 00:08:34,780
Det er som om vi sa 28, og
da vi satt 33 på toppen av det,

177
00:08:34,780 --> 00:08:36,659
og vi legger 19 på toppen av det.

178
00:08:36,659 --> 00:08:40,650
Den eneste element vi kan ta av er 19.

179
00:08:40,650 --> 00:08:45,019
>> Nå i diagrammet her hva jeg har gjort
er liksom slettet 19 fra tabellen.

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

181
00:08:46,810 --> 00:08:48,934
Vi skal bare snill
av late som om det ikke er der.

182
00:08:48,934 --> 00:08:51,441
Det er fortsatt der i
at minneposisjon

183
00:08:51,441 --> 00:08:54,190
men vi skal bare ignorere det
ved å endre toppen av stacken

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

185
00:08:56,080 --> 00:08:58,720
Så hvis vi skulle nå presse
et annet element på stakken,

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

187
00:09:00,720 --> 00:09:03,990
>> Men la oss ikke gå gjennom problemer
av å slette 19 fra stabelen.

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

189
00:09:05,830 --> 00:09:11,107
Med henblikk på stabelen er den borte hvis
vi endrer toppen for å være to i stedet for tre.

190
00:09:11,107 --> 00:09:12,690
All right, så det var ganske mye det.

191
00:09:12,690 --> 00:09:15,080
Det er alt vi trenger å gjøre
til pop et element av.

192
00:09:15,080 --> 00:09:16,090
La oss gjøre det igjen.

193
00:09:16,090 --> 00:09:18,610
Så jeg har fremhevet det i rødt her for å
indikerer vi gjør en annen samtale.

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

195
00:09:19,720 --> 00:09:20,803
>> Så hva kommer til å skje?

196
00:09:20,803 --> 00:09:23,670
Vel, vi skal lagre
33 i x, og vi kommer

197
00:09:23,670 --> 00:09:26,217
å endre øverst i bunken til en.

198
00:09:26,217 --> 00:09:29,050
Slik at hvis vi var nå å presse en
element i bunken som vi er

199
00:09:29,050 --> 00:09:31,610
kommer til å gjøre akkurat nå,
hva kommer til å skje

200
00:09:31,610 --> 00:09:36,367
er vi kommer skrivings
matrise plassering nummer 1.

201
00:09:36,367 --> 00:09:38,950
Slik at 33 som ble liksom igjen
bak at vi bare lot

202
00:09:38,950 --> 00:09:44,390
er ikke der lenger, vi bare går
til clobber den og sette 40 der i stedet.

203
00:09:44,390 --> 00:09:46,290
Og da selvfølgelig,
siden vi gjorde en push,

204
00:09:46,290 --> 00:09:48,780
vi kommer til å øke den
toppen av stabelen fra 1 til 2

205
00:09:48,780 --> 00:09:50,950
slik at hvis vi nå legger
et annet element det vil

206
00:09:50,950 --> 00:09:54,700
gå inn i matrisen plassering nummer to.

207
00:09:54,700 --> 00:09:57,590
>> Nå lenkede lister er en annen
måte å implementere stabler.

208
00:09:57,590 --> 00:10:01,210
Og hvis denne definisjonen på
skjermen her ser kjent ut for deg,

209
00:10:01,210 --> 00:10:04,260
det er fordi det ser nesten
nøyaktig det samme, faktisk

210
00:10:04,260 --> 00:10:07,790
det ganske mye er akkurat den
samme som en enkeltvis lenket liste,

211
00:10:07,790 --> 00:10:11,990
hvis du husker fra vår diskusjon av
enkeltvis knyttet lister i en annen video.

212
00:10:11,990 --> 00:10:15,510
Den eneste begrensningen her
er for oss som programmerere,

213
00:10:15,510 --> 00:10:17,900
Vi har ikke lov til å
sette inn eller slette tilfeldig

214
00:10:17,900 --> 00:10:20,620
fra enkeltvis lenket liste
som vi tidligere kunne gjøre.

215
00:10:20,620 --> 00:10:25,820
Vi kan bare nå sette inn og slette fra
forsiden eller toppen av den koblede

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

217
00:10:26,320 --> 00:10:28,028
Det er egentlig den eneste
Forskjellen skjønt.

218
00:10:28,028 --> 00:10:29,700
Dette er ellers en enkeltvis lenket liste.

219
00:10:29,700 --> 00:10:32,060
Det er bare en begrensning
erstatter på oss selv

220
00:10:32,060 --> 00:10:35,770
som programmerere som
endrer den til en stabel.

221
00:10:35,770 --> 00:10:39,280
>> Regelen her er å alltid ha en
Peker til hodet på en lenket liste.

222
00:10:39,280 --> 00:10:41,520
Dette er selvfølgelig en vanligvis
viktig regel først.

223
00:10:41,520 --> 00:10:44,260
For enkeltvis lenket liste allikevel du
trenger bare en peker til hodet

224
00:10:44,260 --> 00:10:46,160
for å få den
kjeden kunne henvise

225
00:10:46,160 --> 00:10:48,596
til alle andre element
i lenket liste.

226
00:10:48,596 --> 00:10:50,470
Men det er spesielt
viktig med en stabel.

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

228
00:10:52,386 --> 00:10:54,090
denne pekeren til å bli en global variabel.

229
00:10:54,090 --> 00:10:56,574
Det er trolig kommer til å
bli enda enklere på den måten.

230
00:10:56,574 --> 00:10:58,240
Så hva er de analoger av push og pop?

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

232
00:10:58,740 --> 00:11:01,812
Så presser igjen er å legge
et nytt element i stabelen.

233
00:11:01,812 --> 00:11:03,770
I en lenket liste som
betyr at vi kommer til å ha

234
00:11:03,770 --> 00:11:07,770
å opprette en ny node som vi er
kommer til å legge inn i lenket liste,

235
00:11:07,770 --> 00:11:10,500
og følg deretter forsiktige skritt
at vi har skissert tidligere

236
00:11:10,500 --> 00:11:16,050
i enkeltvis lenkede lister å legge det til
kjedet uten å bryte kjeden

237
00:11:16,050 --> 00:11:18,900
og miste eller orphaning noen
elementer av lenket liste.

238
00:11:18,900 --> 00:11:21,820
Og det er stort sett hva som
liten blob av tekst der oppsummerer.

239
00:11:21,820 --> 00:11:23,740
Og la oss ta en titt
på det som et diagram.

240
00:11:23,740 --> 00:11:24,823
>> Så her er vår lenket liste.

241
00:11:24,823 --> 00:11:26,620
Den inneholder fire elementer samtidig.

242
00:11:26,620 --> 00:11:30,420
Og mer perfekt her er vår
stable inneholder fire elementer.

243
00:11:30,420 --> 00:11:36,030
Og la oss si at vi nå ønsker å
presse et nytt element på denne bunken.

244
00:11:36,030 --> 00:11:39,792
Og vi ønsker å presse en ny
element som dataverdi er 12.

245
00:11:39,792 --> 00:11:41,000
Vel hva skal vi gjøre?

246
00:11:41,000 --> 00:11:43,420
Vel første vi kommer til å
malloc plass, dynamisk

247
00:11:43,420 --> 00:11:45,411
tildele plass for en ny node.

248
00:11:45,411 --> 00:11:48,160
Og selvfølgelig umiddelbart etter
vi ringe til malloc vi alltid

249
00:11:48,160 --> 00:11:52,989
sørg for å sjekke for null,
fordi hvis vi fikk null tilbake

250
00:11:52,989 --> 00:11:54,280
det var et slags problem.

251
00:11:54,280 --> 00:11:57,570
Vi ønsker ikke å dereference at null
pekeren eller du vil lide en SEG feil.

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

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

254
00:11:59,760 --> 00:12:01,260
Vi vil anta vi har hatt suksess her.

255
00:12:01,260 --> 00:12:06,090
Vi kommer til å sette 12 inn
datafelt for den noden.

256
00:12:06,090 --> 00:12:11,570
Nå husker du hvilke av våre pekere
flytter neste slik at vi ikke bryte kjeden?

257
00:12:11,570 --> 00:12:15,100
Vi har et par alternativer her, men
den eneste som kommer til å være trygge

258
00:12:15,100 --> 00:12:19,330
er å sette nyheter neste pekeren til
punkt til den gamle hodet av listen

259
00:12:19,330 --> 00:12:21,360
eller hva som snart vil være den
gamle hodet av listen.

260
00:12:21,360 --> 00:12:23,610
Og nå som alle våre
Elementene er lenket sammen,

261
00:12:23,610 --> 00:12:27,370
vi kan bare flytte listen til å peke
til det samme sted som nye gjør.

262
00:12:27,370 --> 00:12:33,550
Og vi har nå effektivt skjøvet en
nytt element på forsiden av stabelen.

263
00:12:33,550 --> 00:12:36,420
>> Til pop vi bare ønsker å
slette det første elementet.

264
00:12:36,420 --> 00:12:38,150
Og så i utgangspunktet hva
vi har å gjøre her,

265
00:12:38,150 --> 00:12:40,050
Vel vi må finne det andre elementet.

266
00:12:40,050 --> 00:12:43,540
Etter hvert som blir ny
hodet etter at vi slette den første.

267
00:12:43,540 --> 00:12:47,300
Så vi trenger bare å starte fra
begynnelsen, flytte en fremover.

268
00:12:47,300 --> 00:12:50,340
Når vi har fått tak på en
frem til der vi i dag

269
00:12:50,340 --> 00:12:53,850
vi kan slette den første man trygt
og da kan vi bare flytte hodet

270
00:12:53,850 --> 00:12:57,150
å peke på hva som var den
andre periode og deretter nå

271
00:12:57,150 --> 00:12:59,170
er den første etter at
node har blitt slettet.

272
00:12:59,170 --> 00:13:01,160
>> Så igjen, ta en titt
på det som et diagram vi

273
00:13:01,160 --> 00:13:05,022
vil nå sprette en
element av av denne bunken.

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

275
00:13:05,730 --> 00:13:08,188
Vel vi først kommer til å skape
en ny peker som kommer

276
00:13:08,188 --> 00:13:10,940
å peke på det samme stedet som hodet.

277
00:13:10,940 --> 00:13:13,790
Vi kommer til å flytte den ene stilling
frem ved å si trav equals

278
00:13:13,790 --> 00:13:17,510
trav neste for eksempel, som
ville fremme trav pekeren én

279
00:13:17,510 --> 00:13:19,324
posisjon fremover.

280
00:13:19,324 --> 00:13:21,240
Nå som vi har fått en
hold på det første elementet

281
00:13:21,240 --> 00:13:24,573
gjennom pekeren kalt liste, og
andre element via en peker som kalles

282
00:13:24,573 --> 00:13:28,692
trav, kan vi trygt slette den
første element fra stabelen

283
00:13:28,692 --> 00:13:30,650
uten å miste resten
av kjeden fordi vi

284
00:13:30,650 --> 00:13:32,358
har en måte å referere
til det andre elementet

285
00:13:32,358 --> 00:13:34,780
sende ved hjelp av
pekeren kalt trav.

286
00:13:34,780 --> 00:13:37,100
>> Så nå kan vi frigjøre den noden.

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

288
00:13:38,404 --> 00:13:41,320
Og så alt vi trenger å gjøre nå er
flytte listen til punkt til samme sted

289
00:13:41,320 --> 00:13:44,482
at trav gjør, og vi er liksom tilbake
der vi startet før vi presset 12

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

291
00:13:45,690 --> 00:13:46,940
Dette er akkurat der vi var.

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

293
00:13:48,840 --> 00:13:49,690
Vi har lagt til en femte.

294
00:13:49,690 --> 00:13:51,910
Vi presset en femte
element på, og da er vi

295
00:13:51,910 --> 00:13:55,980
popped som sist
lagt element tilbake av.

296
00:13:55,980 --> 00:13:58,816
>> Det er egentlig ganske mye
alt som er å stabler.

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 koblede lister.

299
00:14:01,815 --> 00:14:04,810
Det er, selvfølgelig, annen
måter å implementere dem også.

300
00:14:04,810 --> 00:14:09,060
I utgangspunktet grunnen til at vi ville bruke
stabler er å opprettholde data på en slik måte

301
00:14:09,060 --> 00:14:12,090
at det mest nylig lagt
element er det første vi er

302
00:14:12,090 --> 00:14:14,980
kommer til å ønske å komme tilbake.

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

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