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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Okej,
så genom denna punkt är du

3
00:00:05,990 --> 00:00:09,020
förmodligen ganska bekant
med arrayer och länkade listor

4
00:00:09,020 --> 00:00:10,950
vilket är de två primära
datastrukturer vi ve

5
00:00:10,950 --> 00:00:16,810
talade om för att hålla uppsättningar
uppgifter av liknande datatyper organiserad.

6
00:00:16,810 --> 00:00:19,080
>> Nu ska vi prata
om ett par varianter

7
00:00:19,080 --> 00:00:20,330
på matriser och länkade listor.

8
00:00:20,330 --> 00:00:22,362
I den här videon vi ska
att prata om stackar.

9
00:00:22,362 --> 00:00:25,320
Specifikt vi ska prata
om en datastruktur som kallas en stapel.

10
00:00:25,320 --> 00:00:28,510
Minns från tidigare diskussioner
om pekare och minne,

11
00:00:28,510 --> 00:00:32,060
att bunten är också
namn för ett segment av minnet

12
00:00:32,060 --> 00:00:34,980
där statiskt deklarerade
memory-- minne som du

13
00:00:34,980 --> 00:00:38,730
namn, variabler som du namnger et
cetera och funktionsramar som vi också

14
00:00:38,730 --> 00:00:41,000
samtals stack ramar finns.

15
00:00:41,000 --> 00:00:45,421
Så det här är en stack datastruktur
inte en stapel segment av minnet.

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

17
00:00:45,920 --> 00:00:46,890
>> Men vad är en bunt?

18
00:00:46,890 --> 00:00:49,220
Så det är ganska mycket bara en
speciell typ av struktur

19
00:00:49,220 --> 00:00:51,190
som upprätthåller uppgifter på ett organiserat sätt.

20
00:00:51,190 --> 00:00:53,760
Och det finns två mycket
vanligaste sätten att genomföra

21
00:00:53,760 --> 00:00:57,380
staplar med två datastrukturer
att vi redan är bekant med,

22
00:00:57,380 --> 00:01:00,340
arrayer och länkade listor.

23
00:01:00,340 --> 00:01:04,430
Vad gör en stapel speciell är
sätt på vilket vi lägga in information

24
00:01:04,430 --> 00:01:08,200
i stacken, och hur vi
ta bort information från stapeln.

25
00:01:08,200 --> 00:01:11,600
I synnerhet med staplar
regeln är bara den mest

26
00:01:11,600 --> 00:01:15,830
nyligen tillagda elementet kan avlägsnas.

27
00:01:15,830 --> 00:01:17,660
>> Så tänk på det som om det är en stapel.

28
00:01:17,660 --> 00:01:21,170
Vi pålning uppgifter
ovanpå sig själv,

29
00:01:21,170 --> 00:01:24,271
och endast sak på toppen
i högen kan avlägsnas.

30
00:01:24,271 --> 00:01:27,020
Vi kan inte ta bort saken under
eftersom allt annat skulle

31
00:01:27,020 --> 00:01:28,020
kollapsa och välta.

32
00:01:28,020 --> 00:01:32,580
Så vi verkligen håller på att bygga en stapel som
vi sedan måste ta bort bit för bit.

33
00:01:32,580 --> 00:01:36,590
På grund av detta har vi ofta hänvisar
på en stapel som LIFO struktur,

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

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

36
00:01:42,290 --> 00:01:45,635
>> Så på grund av denna begränsning av
hur information kan läggas till

37
00:01:45,635 --> 00:01:49,080
och tas bort från en stapel, det finns verkligen
bara två saker vi kan göra med en skorsten.

38
00:01:49,080 --> 00:01:52,010
Vi kan skjuta, som är den
term vi använder för att lägga till

39
00:01:52,010 --> 00:01:55,130
ett nytt element i början av
stack, eller om stapeln inte existerar

40
00:01:55,130 --> 00:01:58,550
och vi skapar det från början,
skapa stapeln i första hand

41
00:01:58,550 --> 00:02:00,110
skulle trycka.

42
00:02:00,110 --> 00:02:04,990
Och sedan pop, det är den typ av CS
term vi använder för att ta bort den senast

43
00:02:04,990 --> 00:02:08,330
tillsatt elementet från toppen av stacken.

44
00:02:08,330 --> 00:02:11,130
>> Så vi kommer att titta på både
implementeringar, både array baserad

45
00:02:11,130 --> 00:02:13,120
och länkad lista baserad.

46
00:02:13,120 --> 00:02:14,870
Och vi kommer att
börja med array baserad.

47
00:02:14,870 --> 00:02:19,990
Så här är den grundläggande uppfattning om vad
arrayen baserad stapeln datastruktur

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

49
00:02:21,140 --> 00:02:23,740
Vi har en definition typbestämd här.

50
00:02:23,740 --> 00:02:27,790
Insidan av att vi har två medlemmar
eller fält av strukturen.

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

52
00:02:29,880 --> 00:02:32,400
Och återigen jag använder
godtycklig datatyp värde.

53
00:02:32,400 --> 00:02:35,180
>> Så det kan vara någon datatyp
int char eller något annat uppgifter

54
00:02:35,180 --> 00:02:37,080
skriver du tidigare skapat.

55
00:02:37,080 --> 00:02:39,861
Så vi har en matris med storlek kapacitet.

56
00:02:39,861 --> 00:02:44,010
Kapacitet som ett pund definierad konstant,
kanske någon annanstans i vår fil.

57
00:02:44,010 --> 00:02:47,550
Så märker redan med just denna
genomförande vi avgränsar

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

59
00:02:49,800 --> 00:02:53,170
som vi kan inte dynamiskt ändra storlek,
där det finns ett visst antal

60
00:02:53,170 --> 00:02:55,450
maximal element som
vi kan sätta i vår stack.

61
00:02:55,450 --> 00:02:57,930
I detta fall är det kapacitetselement.

62
00:02:57,930 --> 00:03:00,310
>> Vi håller också koll på
överst i stacken.

63
00:03:00,310 --> 00:03:04,350
Vilken del är det mest
nyligen lagts till stacken?

64
00:03:04,350 --> 00:03:07,470
Och så håller vi koll på det
i en variabel som kallas topp.

65
00:03:07,470 --> 00:03:11,692
Och allt detta blir insvept tillsammans
in i en ny datatyp som kallas en stapel.

66
00:03:11,692 --> 00:03:13,400
Och när vi är skapade
denna nya datatypen

67
00:03:13,400 --> 00:03:15,410
vi kan behandla det som
andra datatyper.

68
00:03:15,410 --> 00:03:20,970
Vi kan deklarera stack s, precis som
vi kunde göra int x, eller röding y.

69
00:03:20,970 --> 00:03:22,990
Och när vi säger stack
s, och vad som händer

70
00:03:22,990 --> 00:03:26,420
är vi en uppsättning av
minne avsatt för oss.

71
00:03:26,420 --> 00:03:28,770
>> I detta fall är kapaciteten
Jag har tydligen bestämt

72
00:03:28,770 --> 00:03:33,470
är 10, eftersom jag har en
enda variabel av typen stack

73
00:03:33,470 --> 00:03:35,320
som innehåller två fält minns.

74
00:03:35,320 --> 00:03:38,330
En array, i detta fall kommer
att vara en array av heltal

75
00:03:38,330 --> 00:03:40,440
vilket är fallet i de flesta av mina exempel.

76
00:03:40,440 --> 00:03:43,996
Och en annan heltalsvariabel
kan lagra toppen,

77
00:03:43,996 --> 00:03:45,870
senast tillagda
elementet till stapeln.

78
00:03:45,870 --> 00:03:50,290
Så en enda stack med vad vi
bara definierade ser ut så här.

79
00:03:50,290 --> 00:03:53,190
Det är en låda som innehåller
en uppsättning av 10 vad

80
00:03:53,190 --> 00:03:57,280
kommer vara heltal i detta fall och
annan heltalsvariabel där i grönt

81
00:03:57,280 --> 00:04:00,010
att indikera överst i stacken.

82
00:04:00,010 --> 00:04:02,600
>> Om du vill ställa upp i
stack vi bara säga s.top.

83
00:04:02,600 --> 00:04:04,890
Det är så vi åt en
fält av en struktur återkallande.

84
00:04:04,890 --> 00:04:10,460
s.top lika 0 effektivt
gör detta till vår stack.

85
00:04:10,460 --> 00:04:12,960
Så återigen har vi två operationer
att vi kan utföra nu.

86
00:04:12,960 --> 00:04:14,270
Vi kan driva och vi kan dyka.

87
00:04:14,270 --> 00:04:15,635
Låt oss börja med push.

88
00:04:15,635 --> 00:04:18,260
Återigen, driver är att lägga en ny
element till toppen av stacken.

89
00:04:18,260 --> 00:04:21,460
>> Så vad gör vi behöver göra
denna array baserad genomförande?

90
00:04:21,460 --> 00:04:23,210
Väl i allmänhet
push-funktion går

91
00:04:23,210 --> 00:04:26,160
att behöva acceptera en
Pekare till stapeln.

92
00:04:26,160 --> 00:04:28,610
Nu tar en andra och tänka på det.

93
00:04:28,610 --> 00:04:32,840
Varför skulle vi vilja att acceptera
en pekare till stapeln?

94
00:04:32,840 --> 00:04:36,830
Minns från tidigare videor på
variabel omfattning och pekare,

95
00:04:36,830 --> 00:04:42,350
vad skulle hända om vi precis skickat
stack, s snarare in som en parameter?

96
00:04:42,350 --> 00:04:45,770
Vad skulle faktiskt gått där?

97
00:04:45,770 --> 00:04:49,430
Kom ihåg att vi skapar en kopia
när vi passerar den till en funktion

98
00:04:49,430 --> 00:04:51,160
om vi inte använder pekare.

99
00:04:51,160 --> 00:04:55,380
Och så den här funktionen driva behov
att acceptera en pekare till stapeln

100
00:04:55,380 --> 00:04:59,160
så att vi faktiskt förändras
stapeln tänker vi ändra.

101
00:04:59,160 --> 00:05:03,060
>> Den andra saken tryck vill förmodligen
acceptera är ett dataelement av typen värde.

102
00:05:03,060 --> 00:05:06,970
I detta fall, återigen, ett heltal som
vi kommer att lägga till toppen av stacken.

103
00:05:06,970 --> 00:05:08,680
Så vi har fått våra två parametrar.

104
00:05:08,680 --> 00:05:11,310
Vad ska vi
Nu gör insidan av tryck?

105
00:05:11,310 --> 00:05:14,860
Jo, helt enkelt, vi ska bara lägga
detta element till toppen av stacken

106
00:05:14,860 --> 00:05:22,860
och sedan ändra var toppen av
stapeln är, att s prick toppvärde.

107
00:05:22,860 --> 00:05:25,639
Så det här är vad en funktion
deklaration för push-

108
00:05:25,639 --> 00:05:27,680
kan se ut i ett
matrisbaserad implementering.

109
00:05:27,680 --> 00:05:30,967
>> Återigen är detta inte en hård och snabb regel
att du kan ändra på detta och har

110
00:05:30,967 --> 00:05:32,050
det varierar på olika sätt.

111
00:05:32,050 --> 00:05:33,840
Kanske s förklaras globalt.

112
00:05:33,840 --> 00:05:36,180
Och så att du inte ens behöver
att passera den är som en parameter.

113
00:05:36,180 --> 00:05:39,125
Detta är återigen bara en
generella fallet för push.

114
00:05:39,125 --> 00:05:41,000
Och det finns olika
sätt att genomföra den.

115
00:05:41,000 --> 00:05:42,810
Men i detta fall vår
tryck kommer att ta

116
00:05:42,810 --> 00:05:48,540
två argument, en pekare till en skorsten och
en dataelement av typen värde, heltal

117
00:05:48,540 --> 00:05:49,840
I det här fallet.

118
00:05:49,840 --> 00:05:52,100
>> Så vi förklarade s, vi
nämnda s.top lika 0.

119
00:05:52,100 --> 00:05:55,969
Låt oss nu driva
nummer 28 på stacken.

120
00:05:55,969 --> 00:05:57,010
Och vad betyder det?

121
00:05:57,010 --> 00:05:59,600
Väl närvarande den
toppen av stapeln är 0.

122
00:05:59,600 --> 00:06:01,350
Och så vad är i grund och botten
kommer att hända är

123
00:06:01,350 --> 00:06:05,820
vi kommer att hålla antalet
28 in array plats 0.

124
00:06:05,820 --> 00:06:09,540
Ganska enkelt, rätt att
var toppen och nu är vi är bra att gå.

125
00:06:09,540 --> 00:06:12,910
Och då måste vi ändra på det
överst i stapeln kommer att bli.

126
00:06:12,910 --> 00:06:15,130
Så att nästa gång
Vi trycker ett led i,

127
00:06:15,130 --> 00:06:18,017
vi kommer att lagra den i
array plats, förmodligen inte 0.

128
00:06:18,017 --> 00:06:20,100
Vi vill inte skriva över
vad vi bara sätta dit.

129
00:06:20,100 --> 00:06:23,510
Och så vi ska bara flytta upp för att en.

130
00:06:23,510 --> 00:06:24,890
Det gör förmodligen vettigt.

131
00:06:24,890 --> 00:06:28,940
>> Om vi ​​nu vill sätta ett annat element
på stacken, säga att vi vill driva 33,

132
00:06:28,940 --> 00:06:33,190
väl nu vi ska bara ta 33
och satte den på array platsnummer

133
00:06:33,190 --> 00:06:37,580
1, och sedan ändra toppen av vår
stack vara array plats nummer två.

134
00:06:37,580 --> 00:06:40,650
Så om nästa gång vi vill
skjuta ett element på stacken,

135
00:06:40,650 --> 00:06:43,087
det ska sättas i array plats 2.

136
00:06:43,087 --> 00:06:44,420
Och låt oss göra det en gång till.

137
00:06:44,420 --> 00:06:45,753
Vi kommer att driva 19 av av staplarna.

138
00:06:45,753 --> 00:06:48,940
Vi sätter 19 i array plats 2
och ändra toppen av vår stack

139
00:06:48,940 --> 00:06:51,220
att vara array plats 3
så om nästa gång vi

140
00:06:51,220 --> 00:06:54,780
måste göra en push vi är bra att gå.

141
00:06:54,780 --> 00:06:56,980
>> OK, så det är att trycka i ett nötskal.

142
00:06:56,980 --> 00:06:57,830
Vad sägs om popping?

143
00:06:57,830 --> 00:07:00,240
Så popping är den sortens
motsvarighet till att pressa.

144
00:07:00,240 --> 00:07:02,720
Det är hur vi tar bort data från stacken.

145
00:07:02,720 --> 00:07:04,610
Och i allmänhet pop behov
att göra följande.

146
00:07:04,610 --> 00:07:07,600
Det måste acceptera en pekare till
stack, återigen i det allmänna fallet.

147
00:07:07,600 --> 00:07:10,480
I vissa andra fall du kanske
har förklarat stapeln globalt,

148
00:07:10,480 --> 00:07:13,910
i vilket fall du behöver inte passera det
i eftersom det redan har tillgång till den

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

150
00:07:15,541 --> 00:07:17,040
Men vad behöver vi göra?

151
00:07:17,040 --> 00:07:21,000
Jo vi uppräkning
toppen av stapeln i tryck,

152
00:07:21,000 --> 00:07:24,050
så vi förmodligen kommer att vilja
att dekrementera toppen av stacken

153
00:07:24,050 --> 00:07:25,009
pop, eller hur?

154
00:07:25,009 --> 00:07:26,800
Och sedan naturligtvis
vi också kommer att vilja

155
00:07:26,800 --> 00:07:29,240
att returnera värdet att vi tar bort.

156
00:07:29,240 --> 00:07:32,125
Om vi ​​lägger till element, vi vill ha
att få element ut senare,

157
00:07:32,125 --> 00:07:34,000
vi förmodligen faktiskt
vill lagra dem så vi

158
00:07:34,000 --> 00:07:36,490
inte bara ta bort dem från
stapla och sedan inte göra något med dem.

159
00:07:36,490 --> 00:07:38,500
Generellt om vi
trycka och poppar här

160
00:07:38,500 --> 00:07:41,250
vi vill lagra detta
information på ett meningsfullt sätt

161
00:07:41,250 --> 00:07:43,250
och så att den inte gör
vettigt att bara slänga den.

162
00:07:43,250 --> 00:07:46,380
Så denna funktion bör
förmodligen tillbaka ett värde för oss.

163
00:07:46,380 --> 00:07:51,040
>> Så det här är vad en deklaration för pop
kan se ut det längst upp till vänster.

164
00:07:51,040 --> 00:07:53,870
Den här funktionen returnerar
uppgifter av typen värde.

165
00:07:53,870 --> 00:07:56,320
Återigen har vi använt
heltal hela.

166
00:07:56,320 --> 00:08:01,916
Och det accepterar en pekare till en stapel som
dess enda argument eller enda parameter.

167
00:08:01,916 --> 00:08:03,040
Så vad är pop kommer att göra?

168
00:08:03,040 --> 00:08:07,990
Låt oss säga att vi vill nu
pop ett element bort av er.

169
00:08:07,990 --> 00:08:14,000
Så minns att jag sa att staplar är sista
in, först ut, LIFO datastrukturer.

170
00:08:14,000 --> 00:08:17,855
Vilket element kommer att
avlägsnas från stapeln?

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

172
00:08:21,780 --> 00:08:24,150
Har du gissa 19?

173
00:08:24,150 --> 00:08:25,290
Eftersom du skulle vara rätt.

174
00:08:25,290 --> 00:08:28,836
19 var den sista delen vi lagt till
stack när vi drev element på,

175
00:08:28,836 --> 00:08:31,210
och så det kommer att den första
element som får bort.

176
00:08:31,210 --> 00:08:34,780
Det är som om vi sade 28, och
då sätter vi 33 ovanpå det,

177
00:08:34,780 --> 00:08:36,659
och vi sätter 19 på toppen av det.

178
00:08:36,659 --> 00:08:40,650
Den enda faktor vi kan ta bort är 19.

179
00:08:40,650 --> 00:08:45,019
>> Nu i diagrammet här vad jag har gjort
är sorts bort 19 från gruppen.

180
00:08:45,019 --> 00:08:46,810
Det är faktiskt inte
vad vi ska göra.

181
00:08:46,810 --> 00:08:48,934
Vi ska bara typ
av låtsas att det inte finns.

182
00:08:48,934 --> 00:08:51,441
Det är fortfarande kvar i
den minnesplatsen,

183
00:08:51,441 --> 00:08:54,190
men vi kommer bara att ignorera det
genom att ändra toppen av vår stack

184
00:08:54,190 --> 00:08:56,080
från att vara tre till två.

185
00:08:56,080 --> 00:08:58,720
Så om vi skulle nu trycka
ett annat element på stacken,

186
00:08:58,720 --> 00:09:00,720
det skulle skriva över 19.

187
00:09:00,720 --> 00:09:03,990
>> Men låt oss inte gå igenom besväret
för att ta bort 19 från stapeln.

188
00:09:03,990 --> 00:09:05,830
Vi kan bara låtsas som om det inte finns.

189
00:09:05,830 --> 00:09:11,107
Vid tillämpningen av stapeln det har gått om
vi ändrar toppen att vara två i stället för tre.

190
00:09:11,107 --> 00:09:12,690
Okej, så det var ganska mycket det.

191
00:09:12,690 --> 00:09:15,080
Det är allt vi behöver göra
att smälla en del av.

192
00:09:15,080 --> 00:09:16,090
Låt oss göra det igen.

193
00:09:16,090 --> 00:09:18,610
Så jag har markerat det i rött här för att
anger vi gör ett annat samtal.

194
00:09:18,610 --> 00:09:19,720
Vi kommer att göra samma sak.

195
00:09:19,720 --> 00:09:20,803
>> Så vad kommer att hända?

196
00:09:20,803 --> 00:09:23,670
Tja, vi kommer att lagra
33 i x- och vi kommer

197
00:09:23,670 --> 00:09:26,217
att ändra toppen av stapeln till ett.

198
00:09:26,217 --> 00:09:29,050
Så att om vi nu att driva en
elementet i stapeln som vi är

199
00:09:29,050 --> 00:09:31,610
kommer att göra just nu,
vad som kommer att hända

200
00:09:31,610 --> 00:09:36,367
är vi ska skrivnings
array plats nummer ett.

201
00:09:36,367 --> 00:09:38,950
Så att 33 som var typ av vänster
bakom att vi bara låtsades

202
00:09:38,950 --> 00:09:44,390
är inte där längre, vi bara gå
att clobber dem och lägg 40 där i stället.

203
00:09:44,390 --> 00:09:46,290
Och då naturligtvis,
eftersom vi gjorde en push,

204
00:09:46,290 --> 00:09:48,780
vi kommer att öka den
toppen av stapeln från ett till 2

205
00:09:48,780 --> 00:09:50,950
så att om vi nu lägga till
en annan faktor Det kommer

206
00:09:50,950 --> 00:09:54,700
gå in array plats nummer två.

207
00:09:54,700 --> 00:09:57,590
>> Nu länkade listor är en annan
sätt att implementera stackar.

208
00:09:57,590 --> 00:10:01,210
Och om denna definition på
skärm här ser bekant för dig,

209
00:10:01,210 --> 00:10:04,260
det beror på att det ser nästan
exakt samma, i själva verket,

210
00:10:04,260 --> 00:10:07,790
det ganska mycket är exakt
samma som en enskilt länkad lista,

211
00:10:07,790 --> 00:10:11,990
Om du minns från vår diskussion om
listor enskilt kopplade i en annan video.

212
00:10:11,990 --> 00:10:15,510
Den enda begränsningen här
är för oss som programmerare,

213
00:10:15,510 --> 00:10:17,900
vi är inte tillåtet att
infoga eller ta bort slumpmässigt

214
00:10:17,900 --> 00:10:20,620
från var för sig länkad lista
som vi kunde tidigare göra.

215
00:10:20,620 --> 00:10:25,820
Vi kan bara nu infoga och ta bort från
den främre eller toppen av länkade

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

217
00:10:26,320 --> 00:10:28,028
Det är egentligen den enda
skillnad ändå.

218
00:10:28,028 --> 00:10:29,700
Detta är annars ett enskilt länkad lista.

219
00:10:29,700 --> 00:10:32,060
Det är bara begränsning
byte på oss själva

220
00:10:32,060 --> 00:10:35,770
som programmerare som
ändras den till en stapel.

221
00:10:35,770 --> 00:10:39,280
>> Regeln är att alltid hålla en
pekaren till chefen för en länkad lista.

222
00:10:39,280 --> 00:10:41,520
Detta är naturligtvis en allmänt
viktig regel först.

223
00:10:41,520 --> 00:10:44,260
För lista enskilt kopplade ändå du
behöver bara en pekare till huvudet

224
00:10:44,260 --> 00:10:46,160
i syfte att ha det
kedja kunna hänvisa

225
00:10:46,160 --> 00:10:48,596
varje annat element
i den länkade listan.

226
00:10:48,596 --> 00:10:50,470
Men det är framför allt
viktigt med en skorsten.

227
00:10:50,470 --> 00:10:52,386
Och så allmänt du
ska verkligen vill

228
00:10:52,386 --> 00:10:54,090
denna pekare att vara en global variabel.

229
00:10:54,090 --> 00:10:56,574
Det är förmodligen kommer att
bli ännu enklare på det sättet.

230
00:10:56,574 --> 00:10:58,240
Så vad är analoger av tryck och pop?

231
00:10:58,240 --> 00:10:58,740
Höger.

232
00:10:58,740 --> 00:11:01,812
Så driver igen lägger
ett nytt element i stacken.

233
00:11:01,812 --> 00:11:03,770
I en länkad lista som
innebär att vi kommer att ha

234
00:11:03,770 --> 00:11:07,770
att skapa en ny nod som vi är
kommer att lägga in den länkade listan,

235
00:11:07,770 --> 00:11:10,500
och följ sedan försiktiga steg
att vi har beskrivit tidigare

236
00:11:10,500 --> 00:11:16,050
i enskilt länkade listor för att lägga till
kedjan utan att bryta kedjan

237
00:11:16,050 --> 00:11:18,900
och att förlora eller föräldralösa någon
delar av den länkade listan.

238
00:11:18,900 --> 00:11:21,820
Och det är i princip vad som
liten klump av text finns sammanfattar.

239
00:11:21,820 --> 00:11:23,740
Och låt oss ta en titt
på det som ett diagram.

240
00:11:23,740 --> 00:11:24,823
>> Så här är vår länkad lista.

241
00:11:24,823 --> 00:11:26,620
Den innehåller samtidigt fyra element.

242
00:11:26,620 --> 00:11:30,420
Och mer perfekt här är vår
stack innehåller fyra element.

243
00:11:30,420 --> 00:11:36,030
Och låt oss säga att vi nu vill
driva en ny punkt på denna stack.

244
00:11:36,030 --> 00:11:39,792
Och vi vill driva en ny
posten vars datavärde är 12.

245
00:11:39,792 --> 00:11:41,000
Och vad ska vi göra?

246
00:11:41,000 --> 00:11:43,420
Väl först ska vi
malloc utrymme, dynamiskt

247
00:11:43,420 --> 00:11:45,411
allokera utrymme för en ny nod.

248
00:11:45,411 --> 00:11:48,160
Och naturligtvis omedelbart efter
Vi gör ett anrop till malloc vi alltid

249
00:11:48,160 --> 00:11:52,989
se till att kontrollera för null,
eftersom om vi fick null tillbaka

250
00:11:52,989 --> 00:11:54,280
Det var någon slags problem.

251
00:11:54,280 --> 00:11:57,570
Vi vill inte dereference som null
pekare eller du kommer att drabbas av en seg fel.

252
00:11:57,570 --> 00:11:58,510
Det är inte 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 kommer att anta att vi har haft framgång här.

255
00:12:01,260 --> 00:12:06,090
Vi kommer att sätta 12 i
datafältet av den noden.

256
00:12:06,090 --> 00:12:11,570
Nu minns du vilka av våra pekare
flyttar nästa så att vi inte bryter kedjan?

257
00:12:11,570 --> 00:12:15,100
Vi har ett par alternativ här men
det enda som kommer att vara säkra

258
00:12:15,100 --> 00:12:19,330
är att sätta nyheter nästa pekare till
peka på den gamla chefen listan

259
00:12:19,330 --> 00:12:21,360
eller vad som kommer snart att vara
gamla chef på listan.

260
00:12:21,360 --> 00:12:23,610
Och nu när alla våra
element kedjas ihop,

261
00:12:23,610 --> 00:12:27,370
Vi kan bara flytta listan till punkt
till samma plats som nya gör.

262
00:12:27,370 --> 00:12:33,550
Och vi har nu i praktiken drivit en
nytt element på framsidan av stapeln.

263
00:12:33,550 --> 00:12:36,420
>> Pop vi bara vill
ta bort det första elementet.

264
00:12:36,420 --> 00:12:38,150
Och så i princip vad
vi måste göra här,

265
00:12:38,150 --> 00:12:40,050
väl vi måste hitta det andra elementet.

266
00:12:40,050 --> 00:12:43,540
Till slut som kommer att bli den nya
huvudet efter att vi tar bort den första.

267
00:12:43,540 --> 00:12:47,300
Så vi behöver bara börja från
början, flytta en framåt.

268
00:12:47,300 --> 00:12:50,340
När vi har fått tag på ett
framför där vi idag

269
00:12:50,340 --> 00:12:53,850
är att vi kan ta bort den första på ett säkert sätt
och sedan kan vi bara flytta huvudet

270
00:12:53,850 --> 00:12:57,150
att peka på vad som var
andra terminen och sedan nu

271
00:12:57,150 --> 00:12:59,170
är den första efter att
nod har raderats.

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

273
00:13:01,160 --> 00:13:05,022
vill nu pop en
del av av denna stack.

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

275
00:13:05,730 --> 00:13:08,188
Väl vi först kommer att skapa
en ny pekare som händer

276
00:13:08,188 --> 00:13:10,940
att peka på samma plats som huvudet.

277
00:13:10,940 --> 00:13:13,790
Vi kommer att flytta den en position
framåt genom att säga trav jämlikar

278
00:13:13,790 --> 00:13:17,510
trav nästa till exempel, som
skulle föra trav pekaren en

279
00:13:17,510 --> 00:13:19,324
läge framåt.

280
00:13:19,324 --> 00:13:21,240
Nu när vi har fått en
håll på det första elementet

281
00:13:21,240 --> 00:13:24,573
genom pekaren kallas listan, och
andra elementet genom en pekare som heter

282
00:13:24,573 --> 00:13:28,692
trav, kan vi säkert ta bort den
första elementet från stapeln

283
00:13:28,692 --> 00:13:30,650
utan att förlora resten
av kedjan, eftersom vi

284
00:13:30,650 --> 00:13:32,358
har ett sätt att hänvisa
till det andra elementet

285
00:13:32,358 --> 00:13:34,780
framåt med hjälp av
pekaren kallade trav.

286
00:13:34,780 --> 00:13:37,100
>> Så nu kan vi frigöra den noden.

287
00:13:37,100 --> 00:13:38,404
Vi kan frigöra listan.

288
00:13:38,404 --> 00:13:41,320
Och sedan allt vi behöver göra nu är
flytta listan till punkt till samma plats

289
00:13:41,320 --> 00:13:44,482
att trav gör, och vi är typ av tillbaka
där vi började innan vi drivit 12

290
00:13:44,482 --> 00:13:45,690
på i första hand, till höger.

291
00:13:45,690 --> 00:13:46,940
Det är precis där vi var.

292
00:13:46,940 --> 00:13:48,840
Vi hade detta med fyra element stack.

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

294
00:13:49,690 --> 00:13:51,910
Vi sköt en femtedel
element på, och sedan vi

295
00:13:51,910 --> 00:13:55,980
poppade som senast
tillagda elementet backa.

296
00:13:55,980 --> 00:13:58,816
>> Det är egentligen ganska mycket
allt som finns att travar.

297
00:13:58,816 --> 00:14:00,190
Du kan genomföra dem matriser.

298
00:14:00,190 --> 00:14:01,815
Du kan genomföra dem länkade listor.

299
00:14:01,815 --> 00:14:04,810
Det finns naturligtvis andra
sätt att genomföra dem.

300
00:14:04,810 --> 00:14:09,060
I grund och botten anledningen till att vi skulle använda
stackar är att underhålla data på ett sådant sätt

301
00:14:09,060 --> 00:14:12,090
att det senast tillagda
elementet är det första vi är

302
00:14:12,090 --> 00:14:14,980
kommer att vilja komma tillbaka.

303
00:14:14,980 --> 00:14:17,900
Jag är Doug Lloyd, är detta CS50.

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