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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Dobre,
takže týmto bodom, ktorú ste

3
00:00:05,990 --> 00:00:09,020
asi dosť povedomý
s polí a spojových zoznamov

4
00:00:09,020 --> 00:00:10,950
čo je dva primárne
dátové štruktúry sme

5
00:00:10,950 --> 00:00:16,810
hovoril o pre vedenie sád
Údaje z podobných typov dátových organizovaný.

6
00:00:16,810 --> 00:00:19,080
>> Teraz budeme hovoriť
o niekoľko variantov

7
00:00:19,080 --> 00:00:20,330
Na pole a spojových zoznamov.

8
00:00:20,330 --> 00:00:22,362
V tomto videu budeme
hovoriť o komíny.

9
00:00:22,362 --> 00:00:25,320
Konkrétne budeme hovoriť
o dátovú štruktúru volal hromadu.

10
00:00:25,320 --> 00:00:28,510
Pripomeňme z predchádzajúcich diskusií
o ukazovatele a pamäť,

11
00:00:28,510 --> 00:00:32,060
že zásobník je tiež
menovať segment pamäte

12
00:00:32,060 --> 00:00:34,980
kde staticky deklaroval
memory-- pamäť, ktorá vám

13
00:00:34,980 --> 00:00:38,730
meno, premenné, ktoré si len spomeniete, et
cetera a funkcie rámy, ktoré sme tiež

14
00:00:38,730 --> 00:00:41,000
zásobník volaní rámce existujú.

15
00:00:41,000 --> 00:00:45,421
Takže toto je štruktúra zásobník dát
nie je stoh segment pamäte.

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

17
00:00:45,920 --> 00:00:46,890
>> Ale čo je to zásobník?

18
00:00:46,890 --> 00:00:49,220
Takže je to do značnej miery len
Zvláštny druh konštrukcie

19
00:00:49,220 --> 00:00:51,190
ktorý udržuje dáta v organizovaným spôsobom.

20
00:00:51,190 --> 00:00:53,760
A tam sú dve veľmi
obyčajné spôsoby, ako realizovať

21
00:00:53,760 --> 00:00:57,380
komíny pomocou dvoch dátových štruktúr
že sme už oboznámení s,

22
00:00:57,380 --> 00:01:00,340
poľa a spojové zoznamy.

23
00:01:00,340 --> 00:01:04,430
Čo robí balík zvláštne, je
spôsob, v ktorom sa vložiť informácie

24
00:01:04,430 --> 00:01:08,200
do komína, a spôsob, akým
odobrať informácie zo zásobníka.

25
00:01:08,200 --> 00:01:11,600
Najmä s komíny
pravidlo je len tie

26
00:01:11,600 --> 00:01:15,830
pridanie element môžu byť odstránené.

27
00:01:15,830 --> 00:01:17,660
>> Takže myslíte, že o tom, ako keby je to hromada.

28
00:01:17,660 --> 00:01:21,170
Sme hromadia informácie
v hornej časti sama o sebe,

29
00:01:21,170 --> 00:01:24,271
a to len vec na vrchole
hromady môžu byť odstránené.

30
00:01:24,271 --> 00:01:27,020
Nemôžeme odstrániť vec pod
pretože všetko ostatné by

31
00:01:27,020 --> 00:01:28,020
zrúti a spadnúť.

32
00:01:28,020 --> 00:01:32,580
Takže sme vlastne budujeme zväzok, ktorý
my potom musieť odstrániť kúsok po kúsku.

33
00:01:32,580 --> 00:01:36,590
Z tohto dôvodu sme sa obyčajne sa odvolávajú
do komína ako štruktúra LIFO,

34
00:01:36,590 --> 00:01:38,940
posledný dnu, prvý von.

35
00:01:38,940 --> 00:01:42,290
LIFO, posledný dnu, prvý von.

36
00:01:42,290 --> 00:01:45,635
>> Takže kvôli tomuto obmedzeniu
ako môžu byť informácie pridané do

37
00:01:45,635 --> 00:01:49,080
a odstránil z balíka, je to naozaj
len dve veci, čo môžeme urobiť s komínom.

38
00:01:49,080 --> 00:01:52,010
Môžeme tlačiť, čo je
termín používame pre pridávanie

39
00:01:52,010 --> 00:01:55,130
nový prvok v hornej časti
stack, alebo ak neexistuje stack

40
00:01:55,130 --> 00:01:58,550
a my sme ju vytvárať od nuly,
vytváranie zásobníka na prvom mieste

41
00:01:58,550 --> 00:02:00,110
bude tlačiť.

42
00:02:00,110 --> 00:02:04,990
A potom sa pop, to je druh SK
termín používame na odstránenie naposledy

43
00:02:04,990 --> 00:02:08,330
pridaný prvok z hornej časti zásobníka.

44
00:02:08,330 --> 00:02:11,130
>> Takže budeme pozerať na oboch
implementácia, a to ako na báze pole

45
00:02:11,130 --> 00:02:13,120
a spájať zoznam založený.

46
00:02:13,120 --> 00:02:14,870
A ideme
začať s radom báze.

47
00:02:14,870 --> 00:02:19,990
Tak tu je základná myšlienka o tom, čo
štruktúra zásobníka dátové polia na báze

48
00:02:19,990 --> 00:02:21,140
vyzerať.

49
00:02:21,140 --> 00:02:23,740
Máme definíciu zadaný tu.

50
00:02:23,740 --> 00:02:27,790
Vo vnútri, že máme dvoch členov
alebo pole štruktúry.

51
00:02:27,790 --> 00:02:29,880
Máme pole.

52
00:02:29,880 --> 00:02:32,400
A opäť som pomocou
ľubovoľná dátový typ hodnoty.

53
00:02:32,400 --> 00:02:35,180
>> Takže to môže byť akýkoľvek typ údajov,
int char alebo iné údaje

54
00:02:35,180 --> 00:02:37,080
typ ste predtým vytvorili.

55
00:02:37,080 --> 00:02:39,861
Takže máme rad veľkosti kapacity.

56
00:02:39,861 --> 00:02:44,010
Kapacita je pol kila definovaný konštantný,
Možno niekde inde v našej súboru.

57
00:02:44,010 --> 00:02:47,550
Takže si všimnúť už s týmto konkrétnym
implementácia sme ohraničujúca

58
00:02:47,550 --> 00:02:49,800
sami seba ako bol typicky
prípad s poli,

59
00:02:49,800 --> 00:02:53,170
ktoré nemôžeme dynamicky meniť veľkosť,
tam, kde je určitý počet

60
00:02:53,170 --> 00:02:55,450
z prvkov, ktoré maxima
môžeme dať v našej zásobníku.

61
00:02:55,450 --> 00:02:57,930
V tomto prípade je to kapacitné prvkami.

62
00:02:57,930 --> 00:03:00,310
>> Tiež sledovať
v hornej časti zásobníka.

63
00:03:00,310 --> 00:03:04,350
Čo element je najviac
nedávno pridal do stohu?

64
00:03:04,350 --> 00:03:07,470
A tak sme sa sledovať, že
v premennej s názvom vrchole.

65
00:03:07,470 --> 00:03:11,692
A to všetko dostane zabalené spolu
do nového dátového typu s názvom hromadu.

66
00:03:11,692 --> 00:03:13,400
A akonáhle sme vytvorili
tento nový dátový typ

67
00:03:13,400 --> 00:03:15,410
môžeme liečiť ako
akýkoľvek iný typ dát.

68
00:03:15,410 --> 00:03:20,970
Môžeme prehlásiť zásobníka s, rovnako ako
sme mohli urobiť int x, alebo char y.

69
00:03:20,970 --> 00:03:22,990
A keď hovoríme stack
s, aj čo sa stane

70
00:03:22,990 --> 00:03:26,420
sa dostaneme sadu
Pamäť zrušil pre nás.

71
00:03:26,420 --> 00:03:28,770
>> V tomto prípade kapacity
Som sa zrejme rozhodol,

72
00:03:28,770 --> 00:03:33,470
10 preto, že som dostal
single premenná typu zásobníka

73
00:03:33,470 --> 00:03:35,320
ktorý obsahuje dve polia obehu.

74
00:03:35,320 --> 00:03:38,330
Pole, v tomto prípade bude
byť pole celých čísel

75
00:03:38,330 --> 00:03:40,440
ako je to v prípade väčšiny svojich príkladov.

76
00:03:40,440 --> 00:03:43,996
A ďalšie integer premenná
schopný uloženie na vrchol,

77
00:03:43,996 --> 00:03:45,870
najnovšie pridané
element do stohu.

78
00:03:45,870 --> 00:03:50,290
Takže jeden jediný zásobník, čo sme
Len definované vyzerá takto.

79
00:03:50,290 --> 00:03:53,190
Je to krabička obsahujúca
Poľa 10, čo

80
00:03:53,190 --> 00:03:57,280
bude celé čísla v tomto prípade, a
ďalšie integer premenná tam zelene

81
00:03:57,280 --> 00:04:00,010
pre indikáciu v hornej časti zásobníka.

82
00:04:00,010 --> 00:04:02,600
>> Ak chcete nastaviť hornú z
stack sme len povedať s.top.

83
00:04:02,600 --> 00:04:04,890
To je, ako sme prístup k
poľa štruktúru odvolanie.

84
00:04:04,890 --> 00:04:10,460
s.top rovná 0 účinne
robí to na náš stack.

85
00:04:10,460 --> 00:04:12,960
Takže znovu máme dve operácie
že môžeme hrať teraz.

86
00:04:12,960 --> 00:04:14,270
Môžeme tlačiť a môžeme pop.

87
00:04:14,270 --> 00:04:15,635
Začnime s Push.

88
00:04:15,635 --> 00:04:18,260
Opäť platí, že tlačí je pridanie novej
prvok na vrchol zásobníka.

89
00:04:18,260 --> 00:04:21,460
>> Takže to, čo potrebujeme urobiť v
Toto pole implementácia na báze?

90
00:04:21,460 --> 00:04:23,210
No všeobecne
Funkcia Push sa deje

91
00:04:23,210 --> 00:04:26,160
musieť akceptovať
Ukazovateľ na zásobníku.

92
00:04:26,160 --> 00:04:28,610
Teraz sa druhý a premýšľať o tom.

93
00:04:28,610 --> 00:04:32,840
Prečo by sme chceli prijať
ukazovateľ na zásobníku?

94
00:04:32,840 --> 00:04:36,830
Pripomeňme z predošlých videí na
variabilný rozsah a ukazovatele,

95
00:04:36,830 --> 00:04:42,350
čo by sa stalo, keby sme práve poslal
zásobník, to skôr ako parameter?

96
00:04:42,350 --> 00:04:45,770
Čo by vlastne byť odovzdané tam?

97
00:04:45,770 --> 00:04:49,430
Pamätajte si, že sme vytvorenie kópie
keď sme to odovzdať funkciu

98
00:04:49,430 --> 00:04:51,160
ak nebudeme používať ukazovatele.

99
00:04:51,160 --> 00:04:55,380
A tak táto funkcia tlačiť potreby
prijať ukazovateľ na stohu

100
00:04:55,380 --> 00:04:59,160
takže sme skutočne mení,
stoh hodláme zmeniť.

101
00:04:59,160 --> 00:05:03,060
>> Ďalšia vec, tlak pravdepodobne chce
prijať je dátový prvok z hodnoty typ.

102
00:05:03,060 --> 00:05:06,970
V tomto prípade je opäť, celé číslo, ktoré
budeme pridávať na vrchol zásobníka.

103
00:05:06,970 --> 00:05:08,680
Takže máme naše dva parametre.

104
00:05:08,680 --> 00:05:11,310
Čo budeme
teraz robiť vnútri tlačiť?

105
00:05:11,310 --> 00:05:14,860
No, proste sme len tak pridať
že element na vrchol stohu

106
00:05:14,860 --> 00:05:22,860
a potom zmeňte kde je horná
zásobník je, že s dot najvyššiu hodnotu.

107
00:05:22,860 --> 00:05:25,639
Takže toto je to, čo funkcia
Vyhlásenie Push

108
00:05:25,639 --> 00:05:27,680
by mohla vyzerať An
array-založené implementácie.

109
00:05:27,680 --> 00:05:30,967
>> Opäť to nie je tvrdé a rýchle pravidlo
že by ste mohli zmeniť a majú

110
00:05:30,967 --> 00:05:32,050
že sa líši v rôznych smeroch.

111
00:05:32,050 --> 00:05:33,840
Možno, že s je deklarovaný globálne.

112
00:05:33,840 --> 00:05:36,180
A tak ani nepotrebujete
odovzdať je ako parameter.

113
00:05:36,180 --> 00:05:39,125
To je opäť len
všeobecný prípad Push.

114
00:05:39,125 --> 00:05:41,000
A tam sú rôzne
spôsoby, ako na jeho vykonanie.

115
00:05:41,000 --> 00:05:42,810
Ale v tomto prípade je naša
Push bude trvať

116
00:05:42,810 --> 00:05:48,540
dva argumenty, ukazovateľ zásobníka a
dátový prvok typu hodnoty, celočíselné

117
00:05:48,540 --> 00:05:49,840
v tomto prípade.

118
00:05:49,840 --> 00:05:52,100
>> Takže sme deklarovali ov, my
povedal s.top rovná 0.

119
00:05:52,100 --> 00:05:55,969
Teraz poďme tlačiť
číslo 28 do zásobníka.

120
00:05:55,969 --> 00:05:57,010
Tak čo to znamená?

121
00:05:57,010 --> 00:05:59,600
No v súčasnosti
stoh papiera je 0.

122
00:05:59,600 --> 00:06:01,350
A tak to, čo je v podstate
bude diať, je

123
00:06:01,350 --> 00:06:05,820
budeme držať číslo
28 do umiestnenia poľa 0.

124
00:06:05,820 --> 00:06:09,540
Celkom jednoduché, vpravo, že
bol vrchol a teraz sme dobrí ísť.

125
00:06:09,540 --> 00:06:12,910
A potom musíme zmeniť to, čo
horná časť zásobníka bude.

126
00:06:12,910 --> 00:06:15,130
Tak, že nabudúce
tlačíme prvok v,

127
00:06:15,130 --> 00:06:18,017
budeme ukladať do
umiestnenie poľa, pravdepodobne nie 0.

128
00:06:18,017 --> 00:06:20,100
Nechceme, aby prepísať
čo sme práve tam dal.

129
00:06:20,100 --> 00:06:23,510
A tak sme si len presunúť odhora 1.

130
00:06:23,510 --> 00:06:24,890
To asi dáva zmysel.

131
00:06:24,890 --> 00:06:28,940
>> Teraz, ak chceme dať ďalšie prvok
do zásobníka, že chceme, aby sa zasadila 33,

132
00:06:28,940 --> 00:06:33,190
No teraz sme len bude trvať 33
a dal ho na pole číslo umiestnenia

133
00:06:33,190 --> 00:06:37,580
1, a potom zmeňte na vrchol nášho
stack byť poľa číslo umiestnenia dvoch.

134
00:06:37,580 --> 00:06:40,650
Takže ak nabudúce chceme
tlačiť prvok do zásobníka,

135
00:06:40,650 --> 00:06:43,087
to bude dať v mieste poľa 2.

136
00:06:43,087 --> 00:06:44,420
A poďme to urobiť ešte raz.

137
00:06:44,420 --> 00:06:45,753
Budeme tlačiť 19 preč z komínov.

138
00:06:45,753 --> 00:06:48,940
Dáme 19 v mieste poľa 2
a zmeniť na vrchol nášho stohu

139
00:06:48,940 --> 00:06:51,220
byť umiestnenie poľa 3
takže ak nabudúce

140
00:06:51,220 --> 00:06:54,780
je potrebné, aby sa tlačiť sme dobrí ísť.

141
00:06:54,780 --> 00:06:56,980
>> OK, takže sa tlačí v kocke.

142
00:06:56,980 --> 00:06:57,830
A čo objavovať?

143
00:06:57,830 --> 00:07:00,240
Takže popping je druh
náprotivok tlačiť.

144
00:07:00,240 --> 00:07:02,720
Je to, ako sme sa odstrániť dáta zo zásobníka.

145
00:07:02,720 --> 00:07:04,610
A v sociálne potreby popových
urobiť nasledujúce.

146
00:07:04,610 --> 00:07:07,600
Je potrebné prijať ukazovateľ na
zásobník, opäť vo všeobecnom prípade.

147
00:07:07,600 --> 00:07:10,480
V niektorých opačnom prípade by ste mohli
vyhlásili stoh globálne,

148
00:07:10,480 --> 00:07:13,910
v takom prípade nemusíte ho prejsť
V pretože už má prístup k nemu

149
00:07:13,910 --> 00:07:15,541
ako globálne premenné.

150
00:07:15,541 --> 00:07:17,040
Ale čo iné robiť, musíme urobiť?

151
00:07:17,040 --> 00:07:21,000
Tak sme sa postupne
horná časť zásobníka v tlačiť,

152
00:07:21,000 --> 00:07:24,050
tak sme pravdepodobne bude chcieť
pre zníženie hornú časť stohu

153
00:07:24,050 --> 00:07:25,009
v pop, že jo?

154
00:07:25,009 --> 00:07:26,800
A potom samozrejme
sme tiež bude chcieť

155
00:07:26,800 --> 00:07:29,240
vrátiť hodnotu, ktoré sme odstrániť.

156
00:07:29,240 --> 00:07:32,125
Ak sme pridať prvky, chceme
dostať prvky sa neskôr,

157
00:07:32,125 --> 00:07:34,000
tak si pravdepodobne skutočne
Chcete ich uložiť, takže sme

158
00:07:34,000 --> 00:07:36,490
nie len odstrániť z
stack, a potom robiť nič s nimi.

159
00:07:36,490 --> 00:07:38,500
Všeobecne platí keď sme
tlačenie a praskanie tu

160
00:07:38,500 --> 00:07:41,250
chceme uložiť tento
Informácie zmysluplne

161
00:07:41,250 --> 00:07:43,250
a tak to neznamená, že
zmysel len odhodiť to.

162
00:07:43,250 --> 00:07:46,380
Takže táto funkcia by mala
pravdepodobne vrátiť hodnotu k nám.

163
00:07:46,380 --> 00:07:51,040
>> Takže to je to, čo vyhlásenie pre pop
môže vyzerať, ako by tam v ľavom hornom rohu.

164
00:07:51,040 --> 00:07:53,870
Táto funkcia vracia
Dáta typu hodnoty.

165
00:07:53,870 --> 00:07:56,320
Opäť sme boli s použitím
celé čísla v celom texte.

166
00:07:56,320 --> 00:08:01,916
A to prijíma ukazovateľ na stack ako
jeho jediným argumentom, alebo jediný parameter.

167
00:08:01,916 --> 00:08:03,040
Takže to, čo sa pop robiť?

168
00:08:03,040 --> 00:08:07,990
Povedzme, že chceme, aby teraz
pop prvok preč s.

169
00:08:07,990 --> 00:08:14,000
Takže pamätajte Povedal som, že zásobníky sú posledné
in, first out, LIFO dátových štruktúr.

170
00:08:14,000 --> 00:08:17,855
Ktorý prvok sa chystá
byť odstránená zo zásobníka?

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

172
00:08:21,780 --> 00:08:24,150
Vedeli ste asi 19?

173
00:08:24,150 --> 00:08:25,290
Vzhľadom k tomu, že budeš v poriadku.

174
00:08:25,290 --> 00:08:28,836
19 bola posledná element sme pridali do
stack, keď sme tlačili na prvky,

175
00:08:28,836 --> 00:08:31,210
a tak to bude prvý
element, ktorý sa odstráni.

176
00:08:31,210 --> 00:08:34,780
Je to, ako keby sme povedali 28, a
Potom sme dali 33 na vrchole toho,

177
00:08:34,780 --> 00:08:36,659
a kladieme 19 na vrchole to.

178
00:08:36,659 --> 00:08:40,650
Jediný prvok môžeme zložiť, je 19.

179
00:08:40,650 --> 00:08:45,019
>> Teraz v diagrame tu, čo som urobil
je druh vymazaný 19 z poľa.

180
00:08:45,019 --> 00:08:46,810
To nie je v skutočnosti
to, čo budeme robiť.

181
00:08:46,810 --> 00:08:48,934
Sme len tak druhu
z predstierať, že tam nie je.

182
00:08:48,934 --> 00:08:51,441
Je to stále tam v
že pamäťové miesto,

183
00:08:51,441 --> 00:08:54,190
ale my sme len tak ignorovať
zmenou vrchol nášho stohu

184
00:08:54,190 --> 00:08:56,080
toho, že 3 až 2.

185
00:08:56,080 --> 00:08:58,720
Takže keby sme teraz tlačiť
Ďalším prvkom do zásobníka,

186
00:08:58,720 --> 00:09:00,720
že by v priebehu písať 19.

187
00:09:00,720 --> 00:09:03,990
>> Ale poďme sa prejsť ťažkostí
mazanie 19 zo zásobníka.

188
00:09:03,990 --> 00:09:05,830
Môžeme len predstierať, že tam nie je.

189
00:09:05,830 --> 00:09:11,107
Na účely stohu je to preč, ak
zmeníme hornej byť 2 namiesto 3.

190
00:09:11,107 --> 00:09:12,690
Dobre, takže to bolo celkom veľa to.

191
00:09:12,690 --> 00:09:15,080
To je všetko, čo potrebujete urobiť,
pop prvok off.

192
00:09:15,080 --> 00:09:16,090
Urobme to znova.

193
00:09:16,090 --> 00:09:18,610
Takže som ho zvýraznené červenou tu
naznačujú, robíme ďalšie hovor.

194
00:09:18,610 --> 00:09:19,720
Chystáme sa urobiť to isté.

195
00:09:19,720 --> 00:09:20,803
>> Takže čo sa stane?

196
00:09:20,803 --> 00:09:23,670
No, budeme uchovávať
33 v x a ideme

197
00:09:23,670 --> 00:09:26,217
pre zmenu v hornej časti zásobníka 1.

198
00:09:26,217 --> 00:09:29,050
Takže keby sme teraz tlačiť
prvok do zásobníka, ktorý ktorom sme

199
00:09:29,050 --> 00:09:31,610
robiť práve teraz,
čo sa bude diať

200
00:09:31,610 --> 00:09:36,367
sa ideme prepisovanie
array číslo umiestnenia 1.

201
00:09:36,367 --> 00:09:38,950
Takže to 33, ktorý bol druh vľavo
za ktoré sme pred chvíľou predstieral

202
00:09:38,950 --> 00:09:44,390
už tam nie je, sme len tak
to naložiť a dal 40 tam miesto.

203
00:09:44,390 --> 00:09:46,290
A potom samozrejme,
od tej doby sme urobili tlak,

204
00:09:46,290 --> 00:09:48,780
ideme pre zvýšenie hodnoty
Vrchol zásobníka 1-2

205
00:09:48,780 --> 00:09:50,950
takže ak by sme teraz pridať
Ďalším prvkom bude to

206
00:09:50,950 --> 00:09:54,700
prejsť do poľa umiestnenie číslo dva.

207
00:09:54,700 --> 00:09:57,590
>> Teraz spojové zoznamy sú ďalšie
spôsob, ako realizovať komíny.

208
00:09:57,590 --> 00:10:01,210
A ak je táto definícia na strane
Obrazovka tu vyzerá povedome vám,

209
00:10:01,210 --> 00:10:04,260
je to preto, že vyzerá skoro
presne rovnaký, v skutočnosti,

210
00:10:04,260 --> 00:10:07,790
je to celkom veľa je presne
rovnaké ako jednotlivo spájať zoznam,

211
00:10:07,790 --> 00:10:11,990
Ak si spomínate z našej diskusie o
jednotlivo spojené zoznamy v inom videu.

212
00:10:11,990 --> 00:10:15,510
Jediné obmedzenie tu
je pre nás ako programátori,

213
00:10:15,510 --> 00:10:17,900
nie sme dovolené
vloženie alebo odstránenie náhodne

214
00:10:17,900 --> 00:10:20,620
zo jednotlivo Google zoznamu
ktoré sme mohli skôr urobiť.

215
00:10:20,620 --> 00:10:25,820
Môžeme sa len teraz vložiť a odstrániť z
prednej alebo hornej časti spojené

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

217
00:10:26,320 --> 00:10:28,028
To je naozaj len
rozdiel hoci.

218
00:10:28,028 --> 00:10:29,700
To je inak single previazaný zoznam.

219
00:10:29,700 --> 00:10:32,060
Je to len obmedzenia
nahrádzať sami na seba

220
00:10:32,060 --> 00:10:35,770
ako programátori, že
zmení ho do zásobníka.

221
00:10:35,770 --> 00:10:39,280
>> Pravidlo je tu vždy udržiavať
ukazovateľ na hlavu prepojeného zozname.

222
00:10:39,280 --> 00:10:41,520
Toto je samozrejme všeobecne
Dôležité pravidlo ako prvý.

223
00:10:41,520 --> 00:10:44,260
Pre jednotlivo spojené zoznam rovnako sa vám
potrebujú iba ukazovateľ na hlave

224
00:10:44,260 --> 00:10:46,160
aby sa, že
reťazec sa odvolať

225
00:10:46,160 --> 00:10:48,596
ku každému druhému prvku
v pripojenom zozname.

226
00:10:48,596 --> 00:10:50,470
Ale je to obzvlášť
dôležité s hromadu.

227
00:10:50,470 --> 00:10:52,386
A tak všeobecne, že ste
bude skutočne chcieť

228
00:10:52,386 --> 00:10:54,090
Tento ukazovateľ byť globálne premenná.

229
00:10:54,090 --> 00:10:56,574
Je to pravdepodobne bude
byť ešte jednoduchšie, že cesta.

230
00:10:56,574 --> 00:10:58,240
Takže aké sú analógy tlačiť a pop?

231
00:10:58,240 --> 00:10:58,740
Správne.

232
00:10:58,740 --> 00:11:01,812
Takže znovu tlačí je pridanie
nový prvok do zásobníka.

233
00:11:01,812 --> 00:11:03,770
V zozname, ktorý Google
znamená, že budeme mať

234
00:11:03,770 --> 00:11:07,770
vytvoriť nový uzol, že sme
Pridáme do prepojeného zoznamu,

235
00:11:07,770 --> 00:11:10,500
a potom postupujte podľa pokynov starostlivo
že sme sa už skôr načrtol

236
00:11:10,500 --> 00:11:16,050
v jednotlivo spojových zoznamov pridať do
reťaz bez prerušenia reťazca

237
00:11:16,050 --> 00:11:18,900
a stráca alebo orphaning akýkoľvek
prvky Google zoznamu.

238
00:11:18,900 --> 00:11:21,820
A to je v podstate, čo to
malá kvapka texte tam zhŕňa.

239
00:11:21,820 --> 00:11:23,740
A poďme sa pozrieť
sa na to ako diagram.

240
00:11:23,740 --> 00:11:24,823
>> Tak tu je náš previazaný zoznam.

241
00:11:24,823 --> 00:11:26,620
To súčasne obsahuje štyri prvky.

242
00:11:26,620 --> 00:11:30,420
A dokonalejšie Tu je náš
stack obsahujúce štyri prvky.

243
00:11:30,420 --> 00:11:36,030
A povedzme, že chceme teraz
tlačiť nové položky na tomto zásobníku.

244
00:11:36,030 --> 00:11:39,792
A my chceme, aby sa zasadila nový
položka, ktorej údaje hodnota je 12.

245
00:11:39,792 --> 00:11:41,000
Tak čo budeme robiť?

246
00:11:41,000 --> 00:11:43,420
Tak po prvé, že budeme
malloc priestor, dynamicky

247
00:11:43,420 --> 00:11:45,411
prideliť priestor pre nový uzol.

248
00:11:45,411 --> 00:11:48,160
A samozrejme okamžite po
urobíme volanie sme vždy malloc

249
00:11:48,160 --> 00:11:52,989
uistite sa, že pre kontrolu null,
pretože ak by sme dostali null staré

250
00:11:52,989 --> 00:11:54,280
tam bol nejaký problém.

251
00:11:54,280 --> 00:11:57,570
Nechceme, aby dereferencia tomuto null
Ukazovateľ alebo budete trpieť poruchu seg.

252
00:11:57,570 --> 00:11:58,510
To nie je dobré.

253
00:11:58,510 --> 00:11:59,760
Takže sme malloced uzla.

254
00:11:59,760 --> 00:12:01,260
Budeme predpokladať, že sme mali úspech tu.

255
00:12:01,260 --> 00:12:06,090
Chystáme sa dať do 12
pole dáta tohto uzla.

256
00:12:06,090 --> 00:12:11,570
Teraz spomínaš si, ktoré z našich ukazovateľov
presunie budúci takže neporušujú reťaz?

257
00:12:11,570 --> 00:12:15,100
Máme niekoľko možností, ale tu
jediná, ktorá to bude v bezpečí

258
00:12:15,100 --> 00:12:19,330
je stanoviť ďalšie ukazovatele na novinky
prejdite na starú hlavu zoznamu

259
00:12:19,330 --> 00:12:21,360
alebo to, čo bude čoskoro
stará hlava zoznamu.

260
00:12:21,360 --> 00:12:23,610
A teraz, že všetky naše
prvky sú pripútal spolu,

261
00:12:23,610 --> 00:12:27,370
môžeme len presunúť zoznam na bod
na rovnaké miesto, že nová robí.

262
00:12:27,370 --> 00:12:33,550
A my sme teraz skutočne presadzovalo
Novým prvkom na prednej strane zásobníka.

263
00:12:33,550 --> 00:12:36,420
>> Ak chcete pop chceme len
zmazať, že prvý prvok.

264
00:12:36,420 --> 00:12:38,150
A tak podstate to, čo
musíme urobiť tu,

265
00:12:38,150 --> 00:12:40,050
dobre musíme nájsť druhý prvok.

266
00:12:40,050 --> 00:12:43,540
Nakoniec, že ​​sa stane novým
hlavu po tom, čo sme odstrániť prvý jeden.

267
00:12:43,540 --> 00:12:47,300
Takže len musíme začať od
začiatok, pohybovať jedným dopredu.

268
00:12:47,300 --> 00:12:50,340
Potom, čo máme držať na jednom
vpred, kde sme v súčasnosti

269
00:12:50,340 --> 00:12:53,850
sme môžete odstrániť prvý bezpečne
a potom môžeme len presunúť hlavou

270
00:12:53,850 --> 00:12:57,150
poukázať na to, čo bolo
druhý termín a potom teraz

271
00:12:57,150 --> 00:12:59,170
je prvá po tom
Uzol bol zmazaný.

272
00:12:59,170 --> 00:13:01,160
>> Takže znova, pričom sa pozrieť
na to ako diagram my

273
00:13:01,160 --> 00:13:05,022
Chcete teraz pop
prvok z tohto zásobníka.

274
00:13:05,022 --> 00:13:05,730
Tak čo budeme robiť?

275
00:13:05,730 --> 00:13:08,188
Tak sme to ako prvý chce vytvoriť
nový ukazovateľ, ktorý sa deje

276
00:13:08,188 --> 00:13:10,940
poukázať na rovnakom mieste ako hlava.

277
00:13:10,940 --> 00:13:13,790
Budeme to jedno miesto presunúť
vpred tým, že hovorí tráv rovná

278
00:13:13,790 --> 00:13:17,510
tráv ďalší napríklad, ktorý
by postupovať ten, tráv ukazovateľ

279
00:13:17,510 --> 00:13:19,324
polohy dopredu.

280
00:13:19,324 --> 00:13:21,240
Teraz, keď máme
držať na prvý prvok

281
00:13:21,240 --> 00:13:24,573
cez ukazovatele s názvom zoznamu a
Druhý prvok prostredníctvom ukazovateľa nazvaný

282
00:13:24,573 --> 00:13:28,692
tráv, môžeme bezpečne zmazať, že
prvý prvok zo zásobníka

283
00:13:28,692 --> 00:13:30,650
bez straty zvyšku
reťaze, pretože sme

284
00:13:30,650 --> 00:13:32,358
mať spôsob, ako odkazovať
k druhému prvku

285
00:13:32,358 --> 00:13:34,780
odovzdá prostredníctvom z
ukazovateľ nazvaný tráv.

286
00:13:34,780 --> 00:13:37,100
>> Takže teraz sa môžeme oslobodiť tento uzol.

287
00:13:37,100 --> 00:13:38,404
Môžeme oslobodiť zoznam.

288
00:13:38,404 --> 00:13:41,320
A potom všetko, čo potrebujete urobiť, je teraz
presunúť zoznam bodu na rovnaké miesto

289
00:13:41,320 --> 00:13:44,482
že tráv robí, a my sme tak nejako staré
kde sme začali, než sme sa tlačil 12

290
00:13:44,482 --> 00:13:45,690
na prvom mieste, doprava.

291
00:13:45,690 --> 00:13:46,940
To je presne tam, kde sme boli.

292
00:13:46,940 --> 00:13:48,840
Mali sme štvorprvková zásobníka.

293
00:13:48,840 --> 00:13:49,690
Pridali sme pätinu.

294
00:13:49,690 --> 00:13:51,910
Presadili sme pätinu
prvok na, a potom sme

295
00:13:51,910 --> 00:13:55,980
vyskočila, že v poslednej dobe
pridaný element späť.

296
00:13:55,980 --> 00:13:58,816
>> To je naozaj celkom veľa
všetko, čo je na komíny.

297
00:13:58,816 --> 00:14:00,190
Môžete je implementovať ako pole.

298
00:14:00,190 --> 00:14:01,815
Môžete ich implementovať ako prepojené zoznamy.

299
00:14:01,815 --> 00:14:04,810
Tam sú, samozrejme, ostatné
spôsoby, ako je tiež realizovať.

300
00:14:04,810 --> 00:14:09,060
V podstate dôvod, prečo by sme použiť
zásobníky je udržať dát takým spôsobom,

301
00:14:09,060 --> 00:14:12,090
že naposledy pridané
prvkom je prvá vec, ktorú sme

302
00:14:12,090 --> 00:14:14,980
bude chcieť vrátiť.

303
00:14:14,980 --> 00:14:17,900
Som Doug Lloyd, to je CS50.

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