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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Dobře,
takže tímto bodem, kterou jste

3
00:00:05,990 --> 00:00:09,020
asi dost povědomý
s polí a spojových seznamů

4
00:00:09,020 --> 00:00:10,950
což je dva primární
datové struktury jsme

5
00:00:10,950 --> 00:00:16,810
mluvil o pro vedení sad
Údaje z podobných typů datových organizovaný.

6
00:00:16,810 --> 00:00:19,080
>> Teď budeme mluvit
o několik variant

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

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

9
00:00:22,362 --> 00:00:25,320
Konkrétně budeme mluvit
o datovou strukturu volal hromadu.

10
00:00:25,320 --> 00:00:28,510
Připomeňme z předchozích diskusí
o ukazatele a paměť,

11
00:00:28,510 --> 00:00:32,060
že zásobník je také
jmenovat segment paměti

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

13
00:00:34,980 --> 00:00:38,730
jméno, proměnné, které si jen vzpomenete, et
cetera a funkce rámy, které jsme také

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

15
00:00:41,000 --> 00:00:45,421
Takže tohle je struktura zásobník dat
není stoh segment paměti.

16
00:00:45,421 --> 00:00:45,920
DOBŘE.

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

18
00:00:46,890 --> 00:00:49,220
Takže je to do značné míry jen
Zvláštní druh konstrukce

19
00:00:49,220 --> 00:00:51,190
který udržuje data v organizovaným způsobem.

20
00:00:51,190 --> 00:00:53,760
A tam jsou dvě velmi
obyčejné způsoby, jak realizovat

21
00:00:53,760 --> 00:00:57,380
komíny pomocí dvou datových struktur
že jsme již obeznámeni s,

22
00:00:57,380 --> 00:01:00,340
pole a spojové seznamy.

23
00:01:00,340 --> 00:01:04,430
Co dělá balík zvláštní, je
způsob, ve kterém se vložit informace

24
00:01:04,430 --> 00:01:08,200
do komína, a způsob, jakým
odebrat informace ze zásobníku.

25
00:01:08,200 --> 00:01:11,600
Zejména s komíny
pravidlo je jen ty

26
00:01:11,600 --> 00:01:15,830
přidání element mohou být odstraněny.

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

28
00:01:17,660 --> 00:01:21,170
Jsme hromadí informace
v horní části sama o sobě,

29
00:01:21,170 --> 00:01:24,271
a to pouze věc na vrcholu
hromady mohou být odstraněny.

30
00:01:24,271 --> 00:01:27,020
Nemůžeme odstranit věc pod
protože všechno ostatní by

31
00:01:27,020 --> 00:01:28,020
zhroutí a spadnout.

32
00:01:28,020 --> 00:01:32,580
Takže jsme vlastně budujeme svazek, který
my pak muset odstranit kousek po kousku.

33
00:01:32,580 --> 00:01:36,590
Z tohoto důvodu jsme se obyčejně se odkazují
do komína jako struktura LIFO,

34
00:01:36,590 --> 00:01:38,940
poslední dovnitř, první ven.

35
00:01:38,940 --> 00:01:42,290
LIFO, poslední dovnitř, první ven.

36
00:01:42,290 --> 00:01:45,635
>> Takže kvůli tomuto omezení
jak mohou být informace přidány do

37
00:01:45,635 --> 00:01:49,080
a odstranil z balíčku, je to opravdu
jen dvě věci, co můžeme udělat s komínem.

38
00:01:49,080 --> 00:01:52,010
Můžeme tlačit, což je
termín používáme pro přidávání

39
00:01:52,010 --> 00:01:55,130
nový prvek v horní části
stack, nebo pokud neexistuje stack

40
00:01:55,130 --> 00:01:58,550
a my jsme ji vytvářet od nuly,
vytváření zásobníku na prvním místě

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

42
00:02:00,110 --> 00:02:04,990
A pak se pop, to je druh CS
termín používáme k odstranění naposledy

43
00:02:04,990 --> 00:02:08,330
přidán prvek z horní části zásobníku.

44
00:02:08,330 --> 00:02:11,130
>> Takže budeme dívat na obou
implementace, a to jak na bázi pole

45
00:02:11,130 --> 00:02:13,120
a spojový seznam založen.

46
00:02:13,120 --> 00:02:14,870
A jdeme
začít s řadou bázi.

47
00:02:14,870 --> 00:02:19,990
Tak tady je základní myšlenka o tom, co
struktura zásobníku datové pole na bázi

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

49
00:02:21,140 --> 00:02:23,740
Máme definici zadaný zde.

50
00:02:23,740 --> 00:02:27,790
Uvnitř, že máme dva členy
nebo pole struktury.

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

52
00:02:29,880 --> 00:02:32,400
A opět jsem pomocí
libovolná datový typ hodnoty.

53
00:02:32,400 --> 00:02:35,180
>> Takže to může být jakýkoliv datový typ,
int char nebo jiné údaje

54
00:02:35,180 --> 00:02:37,080
typ jste dříve vytvořili.

55
00:02:37,080 --> 00:02:39,861
Takže máme řadu velikosti kapacity.

56
00:02:39,861 --> 00:02:44,010
Kapacita je půl kila definovaný konstantní,
Možná někde jinde v naší souboru.

57
00:02:44,010 --> 00:02:47,550
Takže si všimnout již s tímto konkrétním
implementace jsme ohraničující

58
00:02:47,550 --> 00:02:49,800
sami sebe jako byl typicky
případ s poli,

59
00:02:49,800 --> 00:02:53,170
které nemůžeme dynamicky měnit velikost,
tam, kde je určitý počet

60
00:02:53,170 --> 00:02:55,450
z prvků, které maxima
můžeme dát v naší zásobníku.

61
00:02:55,450 --> 00:02:57,930
V tomto případě je to kapacitní prvky.

62
00:02:57,930 --> 00:03:00,310
>> Také sledovat
v horní části zásobníku.

63
00:03:00,310 --> 00:03:04,350
Co element je nejvíce
nedávno přidal do stohu?

64
00:03:04,350 --> 00:03:07,470
A tak jsme se sledovat, že
v proměnné s názvem vrcholu.

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

66
00:03:11,692 --> 00:03:13,400
A jakmile jsme vytvořili
tento nový datový typ

67
00:03:13,400 --> 00:03:15,410
můžeme léčit jako
jakýkoli jiný typ dat.

68
00:03:15,410 --> 00:03:20,970
Můžeme prohlásit zásobníku s, stejně jako
jsme mohli udělat int x, nebo char y.

69
00:03:20,970 --> 00:03:22,990
A když říkáme stack
s, i co se stane

70
00:03:22,990 --> 00:03:26,420
se dostaneme sadu
Paměť zrušil pro nás.

71
00:03:26,420 --> 00:03:28,770
>> V tomto případě kapacity
Jsem se zřejmě rozhodl,

72
00:03:28,770 --> 00:03:33,470
10 proto, že jsem dostal
single proměnná typu zásobníku

73
00:03:33,470 --> 00:03:35,320
který obsahuje dvě pole oběhu.

74
00:03:35,320 --> 00:03:38,330
Pole, v tomto případě bude
být pole celých čísel

75
00:03:38,330 --> 00:03:40,440
jako je tomu v případě většiny svých příkladů.

76
00:03:40,440 --> 00:03:43,996
A další integer proměnná
schopný uložení na vrchol,

77
00:03:43,996 --> 00:03:45,870
nejnověji přidané
element do stohu.

78
00:03:45,870 --> 00:03:50,290
Takže jeden jediný zásobník, co jsme
Jen definovány vypadá takto.

79
00:03:50,290 --> 00:03:53,190
Je to krabička obsahující
Pole 10, co

80
00:03:53,190 --> 00:03:57,280
bude celá čísla v tomto případě, a
další integer proměnná tam zeleně

81
00:03:57,280 --> 00:04:00,010
pro indikaci v horní části zásobníku.

82
00:04:00,010 --> 00:04:02,600
>> Chcete-li nastavit horní z
stack jsme jen říct s.top.

83
00:04:02,600 --> 00:04:04,890
To je, jak jsme přístup k
pole strukturu odvolání.

84
00:04:04,890 --> 00:04:10,460
s.top rovná 0 účinně
dělá to na náš stack.

85
00:04:10,460 --> 00:04:12,960
Takže znovu máme dvě operace
že můžeme hrát teď.

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

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

88
00:04:15,635 --> 00:04:18,260
Opět platí, že tlačí je přidání nové
prvek na vrchol zásobníku.

89
00:04:18,260 --> 00:04:21,460
>> Takže to, co potřebujeme udělat v
Toto pole implementace na bázi?

90
00:04:21,460 --> 00:04:23,210
No obecně
Funkce Push se děje

91
00:04:23,210 --> 00:04:26,160
muset akceptovat
Ukazatel na zásobníku.

92
00:04:26,160 --> 00:04:28,610
Nyní se druhý a přemýšlet o tom.

93
00:04:28,610 --> 00:04:32,840
Proč bychom chtěli přijmout
ukazatel na zásobníku?

94
00:04:32,840 --> 00:04:36,830
Připomeňme z předešlých videí na
variabilní rozsah a ukazatele,

95
00:04:36,830 --> 00:04:42,350
co by se stalo, kdybychom právě poslal
zásobník, to spíše jako parametr?

96
00:04:42,350 --> 00:04:45,770
Co by vlastně být předány tam?

97
00:04:45,770 --> 00:04:49,430
Pamatujte si, že jsme vytvoření kopie
když jsme to předat funkci

98
00:04:49,430 --> 00:04:51,160
pokud nebudeme používat ukazatele.

99
00:04:51,160 --> 00:04:55,380
A tak tato funkce tlačit potřeby
přijmout ukazatel na stohu

100
00:04:55,380 --> 00:04:59,160
takže jsme skutečně mění,
stoh hodláme změnit.

101
00:04:59,160 --> 00:05:03,060
>> Další věc, tlak pravděpodobně chce
přijmout je datový prvek z hodnoty typ.

102
00:05:03,060 --> 00:05:06,970
V tomto případě je opět, celé číslo, které
budeme přidávat na vrchol zásobníku.

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

104
00:05:08,680 --> 00:05:11,310
Co budeme
teď dělat uvnitř tlačit?

105
00:05:11,310 --> 00:05:14,860
No, prostě jsme jen tak přidat
že element na vrchol stohu

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

107
00:05:22,860 --> 00:05:25,639
Takže tohle je to, co funkce
Prohlášení Push

108
00:05:25,639 --> 00:05:27,680
by mohla vypadat An
array-založené implementace.

109
00:05:27,680 --> 00:05:30,967
>> Opět to není tvrdé a rychlé pravidlo
že byste mohli změnit a mají

110
00:05:30,967 --> 00:05:32,050
že se liší v různých směrech.

111
00:05:32,050 --> 00:05:33,840
Možná, že s je deklarován globálně.

112
00:05:33,840 --> 00:05:36,180
A tak ani nepotřebujete
předat je jako parametr.

113
00:05:36,180 --> 00:05:39,125
To je opět jen
obecný případ Push.

114
00:05:39,125 --> 00:05:41,000
A tam jsou různé
způsoby, jak k jeho provedení.

115
00:05:41,000 --> 00:05:42,810
Ale v tomto případě je naše
Push bude trvat

116
00:05:42,810 --> 00:05:48,540
dva argumenty, ukazatel zásobníku a
datový prvek typu hodnoty, celočíselné

117
00:05:48,540 --> 00:05:49,840
v tomto případě.

118
00:05:49,840 --> 00:05:52,100
>> Takže jsme deklarovali ů, my
řekl s.top rovná 0.

119
00:05:52,100 --> 00:05:55,969
Nyní pojďme tlačit
číslo 28 do zásobníku.

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

121
00:05:57,010 --> 00:05:59,600
No v současné době
stoh papíru je 0.

122
00:05:59,600 --> 00:06:01,350
A tak to, co je v podstatě
bude dít, je

123
00:06:01,350 --> 00:06:05,820
budeme držet číslo
28 do umístění pole 0.

124
00:06:05,820 --> 00:06:09,540
Docela jednoduché, vpravo, že
byl vrchol a teď jsme dobří jít.

125
00:06:09,540 --> 00:06:12,910
A pak musíme změnit to, co
horní část zásobníku bude.

126
00:06:12,910 --> 00:06:15,130
Tak, že příště
tlačíme prvek v,

127
00:06:15,130 --> 00:06:18,017
budeme ukládat do
umístění pole, pravděpodobně ne 0.

128
00:06:18,017 --> 00:06:20,100
Nechceme, aby přepsat
co jsme právě tam dal.

129
00:06:20,100 --> 00:06:23,510
A tak jsme si jen přesunout odshora 1.

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

131
00:06:24,890 --> 00:06:28,940
>> Nyní, pokud chceme dát další prvek
do zásobníku, že chceme, aby se zasadila 33,

132
00:06:28,940 --> 00:06:33,190
No teď jsme jen bude trvat 33
a dal ho na pole číslo umístění

133
00:06:33,190 --> 00:06:37,580
1, a poté změňte na vrchol našeho
stack být pole číslo umístění dvou.

134
00:06:37,580 --> 00:06:40,650
Takže pokud příště chceme
tlačit prvek do zásobníku,

135
00:06:40,650 --> 00:06:43,087
to bude dát v místě pole 2.

136
00:06:43,087 --> 00:06:44,420
A pojďme to udělat ještě jednou.

137
00:06:44,420 --> 00:06:45,753
Budeme tlačit 19 pryč z komínů.

138
00:06:45,753 --> 00:06:48,940
Dáme 19 v místě pole 2
a změnit na vrchol našeho stohu

139
00:06:48,940 --> 00:06:51,220
být umístění pole 3
takže pokud příště

140
00:06:51,220 --> 00:06:54,780
je třeba, aby se tlačit jsme dobří jít.

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

142
00:06:56,980 --> 00:06:57,830
A co objevovat?

143
00:06:57,830 --> 00:07:00,240
Takže popping je druh
protějšek tlačit.

144
00:07:00,240 --> 00:07:02,720
Je to, jak jsme se odstranit data ze zásobníku.

145
00:07:02,720 --> 00:07:04,610
A v sociální potřeby popových
udělat následující.

146
00:07:04,610 --> 00:07:07,600
Je třeba přijmout ukazatel na
zásobník, opět v obecném případě.

147
00:07:07,600 --> 00:07:10,480
V některých opačném případě byste mohli
prohlásily stoh globálně,

148
00:07:10,480 --> 00:07:13,910
v takovém případě nemusíte jej projít
V protože již má přístup k němu

149
00:07:13,910 --> 00:07:15,541
jako globální proměnné.

150
00:07:15,541 --> 00:07:17,040
Ale co jiného dělat, musíme udělat?

151
00:07:17,040 --> 00:07:21,000
Tak jsme se postupně
horní část zásobníku v tlačit,

152
00:07:21,000 --> 00:07:24,050
tak jsme pravděpodobně bude chtít
pro snížení horní část stohu

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

154
00:07:25,009 --> 00:07:26,800
A pak samozřejmě
jsme také bude chtít

155
00:07:26,800 --> 00:07:29,240
vrátit hodnotu, které jsme odstranit.

156
00:07:29,240 --> 00:07:32,125
Pokud jsme přidat prvky, chceme
dostat prvky se později,

157
00:07:32,125 --> 00:07:34,000
tak si pravděpodobně skutečně
Chcete je uložit, takže jsme

158
00:07:34,000 --> 00:07:36,490
ne jen odstranit z
stack, a pak dělat nic s nimi.

159
00:07:36,490 --> 00:07:38,500
Obecně platí když jsme
tlačení a praskání zde

160
00:07:38,500 --> 00:07:41,250
chceme uložit tento
Informace smysluplně

161
00:07:41,250 --> 00:07:43,250
a tak to neznamená, že
smysl jen odhodit to.

162
00:07:43,250 --> 00:07:46,380
Takže tato funkce by měla
pravděpodobně vrátit hodnotu k nám.

163
00:07:46,380 --> 00:07:51,040
>> Takže to je to, co prohlášení pro pop
může vypadat, jako by tam v levém horním rohu.

164
00:07:51,040 --> 00:07:53,870
Tato funkce vrací
Data typu hodnoty.

165
00:07:53,870 --> 00:07:56,320
Opět jsme byli s použitím
celá čísla v celém textu.

166
00:07:56,320 --> 00:08:01,916
A to přijímá ukazatel na stack jako
jeho jediným argumentem, nebo jediný parametr.

167
00:08:01,916 --> 00:08:03,040
Takže to, co se pop dělat?

168
00:08:03,040 --> 00:08:07,990
Řekněme, že chceme, aby teď
pop prvek pryč s.

169
00:08:07,990 --> 00:08:14,000
Takže pamatujte Řekl jsem, že zásobníky jsou poslední
in, first out, LIFO datových struktur.

170
00:08:14,000 --> 00:08:17,855
Který prvek se chystá
být odstraněna ze zásobníku?

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

172
00:08:21,780 --> 00:08:24,150
Věděli jste asi 19?

173
00:08:24,150 --> 00:08:25,290
Vzhledem k tomu, že budeš v pořádku.

174
00:08:25,290 --> 00:08:28,836
19 byla poslední element jsme přidali do
stack, když jsme tlačili na prvky,

175
00:08:28,836 --> 00:08:31,210
a tak to bude první
element, který se odstraní.

176
00:08:31,210 --> 00:08:34,780
Je to, jako kdybychom řekli 28, a
Pak jsme dali 33 na vrcholu toho,

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

178
00:08:36,659 --> 00:08:40,650
Jediný prvek můžeme sundat, je 19.

179
00:08:40,650 --> 00:08:45,019
>> Nyní v diagramu tady, co jsem udělal
je druh vymazán 19 z pole.

180
00:08:45,019 --> 00:08:46,810
To není ve skutečnosti
to, co budeme dělat.

181
00:08:46,810 --> 00:08:48,934
Jsme jen tak druhu
z předstírat, že tam není.

182
00:08:48,934 --> 00:08:51,441
Je to pořád tam v
že paměťové místo,

183
00:08:51,441 --> 00:08:54,190
ale my jsme jen tak ignorovat
změnou vrchol našeho 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 kdybychom teď tlačit
Dalším prvkem do zásobníku,

186
00:08:58,720 --> 00:09:00,720
že by v průběhu psát 19.

187
00:09:00,720 --> 00:09:03,990
>> Ale pojďme se projít potíží
mazání 19 ze zásobníku.

188
00:09:03,990 --> 00:09:05,830
Můžeme jen předstírat, že tam není.

189
00:09:05,830 --> 00:09:11,107
Pro účely stohu je to pryč, pokud
změníme horní být 2 namísto 3.

190
00:09:11,107 --> 00:09:12,690
Dobře, takže to bylo docela hodně to.

191
00:09:12,690 --> 00:09:15,080
To je vše, co potřebujete udělat,
pop prvek off.

192
00:09:15,080 --> 00:09:16,090
Udělejme to znovu.

193
00:09:16,090 --> 00:09:18,610
Takže jsem ho zvýrazněny červeně zde
naznačují, děláme další hovor.

194
00:09:18,610 --> 00:09:19,720
Chystáme se udělat to samé.

195
00:09:19,720 --> 00:09:20,803
>> Takže co se stane?

196
00:09:20,803 --> 00:09:23,670
No, budeme uchovávat
33 v x a jedeme

197
00:09:23,670 --> 00:09:26,217
pro změnu v horní části zásobníku 1.

198
00:09:26,217 --> 00:09:29,050
Takže kdybychom teď tlačit
prvek do zásobníku, který kterém jsme

199
00:09:29,050 --> 00:09:31,610
dělat právě teď,
co se bude dít

200
00:09:31,610 --> 00:09:36,367
se jdeme přepisování
array číslo umístění 1.

201
00:09:36,367 --> 00:09:38,950
Takže to 33, který byl druh vlevo
za které jsme před chvílí předstíral

202
00:09:38,950 --> 00:09:44,390
už tam není, jsme jen tak
to nandat a dal 40 tam místo.

203
00:09:44,390 --> 00:09:46,290
A pak samozřejmě,
od té doby jsme udělali tlak,

204
00:09:46,290 --> 00:09:48,780
jdeme pro zvýšení hodnoty
Vrchol zásobníku 1-2

205
00:09:48,780 --> 00:09:50,950
takže pokud bychom nyní přidat
Dalším prvkem bude to

206
00:09:50,950 --> 00:09:54,700
přejít do pole umístění číslo dvě.

207
00:09:54,700 --> 00:09:57,590
>> Nyní spojové seznamy jsou další
způsob, jak realizovat komíny.

208
00:09:57,590 --> 00:10:01,210
A je-li tato definice na straně
Obrazovka tady vypadá povědomě vám,

209
00:10:01,210 --> 00:10:04,260
je to proto, že vypadá skoro
přesně stejný, ve skutečnosti,

210
00:10:04,260 --> 00:10:07,790
je to docela hodně je přesně
stejné jako jednotlivě spojový seznam,

211
00:10:07,790 --> 00:10:11,990
Pokud si vzpomínáte z naší diskuse o
jednotlivě spojené seznamy v jiném videu.

212
00:10:11,990 --> 00:10:15,510
Jediné omezení zde
je pro nás jako programátoři,

213
00:10:15,510 --> 00:10:17,900
nejsme dovoleno
vložení nebo odstranění náhodně

214
00:10:17,900 --> 00:10:20,620
ze jednotlivě Google seznamu
které jsme mohli dříve udělat.

215
00:10:20,620 --> 00:10:25,820
Můžeme se teprve nyní vložit a odstranit z
přední nebo horní části spojeny

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

217
00:10:26,320 --> 00:10:28,028
To je opravdu jen
rozdíl ačkoli.

218
00:10:28,028 --> 00:10:29,700
To je jinak singly provázaný seznam.

219
00:10:29,700 --> 00:10:32,060
Je to jen omezení
nahrazovat sami na sebe

220
00:10:32,060 --> 00:10:35,770
jako programátoři, že
změní jej do zásobníku.

221
00:10:35,770 --> 00:10:39,280
>> Pravidlo je zde vždy udržovat
ukazatel na hlavu propojeného seznamu.

222
00:10:39,280 --> 00:10:41,520
Toto je samozřejmě obecně
Důležité pravidlo jako první.

223
00:10:41,520 --> 00:10:44,260
Pro jednotlivě spojeny seznam stejně se vám
potřebují pouze ukazatel na hlavě

224
00:10:44,260 --> 00:10:46,160
aby se, že
řetězec se odvolat

225
00:10:46,160 --> 00:10:48,596
ke každému druhému prvku
v připojeném seznamu.

226
00:10:48,596 --> 00:10:50,470
Ale je to zvláště
důležité s hromadu.

227
00:10:50,470 --> 00:10:52,386
A tak obecně, že jste
bude skutečně chtít

228
00:10:52,386 --> 00:10:54,090
Tento ukazatel být globální proměnná.

229
00:10:54,090 --> 00:10:56,574
Je to pravděpodobně bude
být ještě jednodušší, že cesta.

230
00:10:56,574 --> 00:10:58,240
Takže jaké jsou analogy tlačit a pop?

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

232
00:10:58,740 --> 00:11:01,812
Takže znovu tlačí je přidání
nový prvek do zásobníku.

233
00:11:01,812 --> 00:11:03,770
V seznamu, který Google
znamená, že budeme mít

234
00:11:03,770 --> 00:11:07,770
vytvořit nový uzel, že jsme
Přidáme do propojeného seznamu,

235
00:11:07,770 --> 00:11:10,500
a pak postupujte podle pokynů pečlivě
že jsme se již dříve nastínil

236
00:11:10,500 --> 00:11:16,050
v jednotlivě spojových seznamů přidat do
řetěz bez přerušení řetězce

237
00:11:16,050 --> 00:11:18,900
a ztrácí nebo orphaning jakýkoli
prvky Google seznamu.

238
00:11:18,900 --> 00:11:21,820
A to je v podstatě, co to
malá kapka textu tam shrnuje.

239
00:11:21,820 --> 00:11:23,740
A pojďme se podívat
se na to jako diagram.

240
00:11:23,740 --> 00:11:24,823
>> Tak tady je náš provázaný seznam.

241
00:11:24,823 --> 00:11:26,620
To současně obsahuje čtyři prvky.

242
00:11:26,620 --> 00:11:30,420
A dokonaleji Tady je náš
stack obsahující čtyři prvky.

243
00:11:30,420 --> 00:11:36,030
A řekněme, že chceme nyní
tlačit nové položky na tomto zásobníku.

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

245
00:11:39,792 --> 00:11:41,000
Tak co budeme dělat?

246
00:11:41,000 --> 00:11:43,420
Tak zaprvé, že budeme
malloc prostor, dynamicky

247
00:11:43,420 --> 00:11:45,411
přidělit prostor pro nový uzel.

248
00:11:45,411 --> 00:11:48,160
A samozřejmě okamžitě po
uděláme volání jsme vždy malloc

249
00:11:48,160 --> 00:11:52,989
ujistěte se, že pro kontrolu null,
protože pokud bychom dostali null zpátky

250
00:11:52,989 --> 00:11:54,280
tam byl nějaký problém.

251
00:11:54,280 --> 00:11:57,570
Nechceme, aby dereference tomuto null
Ukazatel nebo budete trpět poruchu seg.

252
00:11:57,570 --> 00:11:58,510
To není dobré.

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

254
00:11:59,760 --> 00:12:01,260
Budeme předpokládat, že jsme měli úspěch zde.

255
00:12:01,260 --> 00:12:06,090
Chystáme se dát do 12
pole data tohoto uzlu.

256
00:12:06,090 --> 00:12:11,570
Teď vzpomínáš si, které z našich ukazatelů
přesune příští takže neporušují řetěz?

257
00:12:11,570 --> 00:12:15,100
Máme několik možností, ale zde
jediná, která to bude v bezpečí

258
00:12:15,100 --> 00:12:19,330
je stanovit další ukazatele na novinky
přejděte na starou hlavu seznamu

259
00:12:19,330 --> 00:12:21,360
nebo to, co bude brzy
stará hlava seznamu.

260
00:12:21,360 --> 00:12:23,610
A teď, že všechny naše
prvky jsou připoutal spolu,

261
00:12:23,610 --> 00:12:27,370
můžeme jen přesunout seznam na bod
na stejné místo, že nová dělá.

262
00:12:27,370 --> 00:12:33,550
A my jsme teď skutečně prosazovalo
Novým prvkem na přední straně zásobníku.

263
00:12:33,550 --> 00:12:36,420
>> Chcete-li pop chceme jen
smazat, že první prvek.

264
00:12:36,420 --> 00:12:38,150
A tak podstatě to, co
musíme udělat tady,

265
00:12:38,150 --> 00:12:40,050
dobře musíme najít druhý prvek.

266
00:12:40,050 --> 00:12:43,540
Nakonec, že ​​se stane novým
hlavu poté, co jsme odstranit první jeden.

267
00:12:43,540 --> 00:12:47,300
Takže jen musíme začít od
začátek, pohybovat jedním dopředu.

268
00:12:47,300 --> 00:12:50,340
Poté, co máme držet na jednom
vpřed, kde jsme v současné době

269
00:12:50,340 --> 00:12:53,850
jsme můžete odstranit první bezpečně
a pak můžeme jen přesunout hlavou

270
00:12:53,850 --> 00:12:57,150
poukázat na to, co bylo
druhý termín a pak nyní

271
00:12:57,150 --> 00:12:59,170
je první po tom
Uzel byl smazán.

272
00:12:59,170 --> 00:13:01,160
>> Takže znovu, přičemž se podívat
na to jako diagram my

273
00:13:01,160 --> 00:13:05,022
Chcete nyní pop
prvek z tohoto zásobníku.

274
00:13:05,022 --> 00:13:05,730
Tak co budeme dělat?

275
00:13:05,730 --> 00:13:08,188
Tak jsme to jako první hodlá vytvořit
nový ukazatel, který se děje

276
00:13:08,188 --> 00:13:10,940
poukázat na stejném místě jako hlava.

277
00:13:10,940 --> 00:13:13,790
Budeme to jedno místo přesunout
vpřed tím, že říká trav rovná

278
00:13:13,790 --> 00:13:17,510
trav další například, který
by postupovat ten, trav ukazatel

279
00:13:17,510 --> 00:13:19,324
polohy dopředu.

280
00:13:19,324 --> 00:13:21,240
Teď, když máme
držet na první prvek

281
00:13:21,240 --> 00:13:24,573
přes ukazatele s názvem seznamu a
Druhý prvek prostřednictvím ukazatele nazvaný

282
00:13:24,573 --> 00:13:28,692
trav, můžeme bezpečně smazat, že
první prvek ze zásobníku

283
00:13:28,692 --> 00:13:30,650
bez ztráty zbytku
řetězu, protože jsme

284
00:13:30,650 --> 00:13:32,358
mít způsob, jak odkazovat
k druhému prvku

285
00:13:32,358 --> 00:13:34,780
předá prostřednictvím z
ukazatel nazvaný trav.

286
00:13:34,780 --> 00:13:37,100
>> Takže teď se můžeme osvobodit tento uzel.

287
00:13:37,100 --> 00:13:38,404
Můžeme osvobodit seznam.

288
00:13:38,404 --> 00:13:41,320
A pak vše, co potřebujete udělat, je nyní
přesunout seznam bodu na stejné místo

289
00:13:41,320 --> 00:13:44,482
že trav dělá, a my jsme tak nějak zpátky
kde jsme začali, než jsme se tlačil 12

290
00:13:44,482 --> 00:13:45,690
na prvním místě, doprava.

291
00:13:45,690 --> 00:13:46,940
To je přesně tam, kde jsme byli.

292
00:13:46,940 --> 00:13:48,840
Měli jsme čtyřprvková zásobníku.

293
00:13:48,840 --> 00:13:49,690
Přidali jsme pětinu.

294
00:13:49,690 --> 00:13:51,910
Prosadili jsme pětinu
prvek na, a pak jsme

295
00:13:51,910 --> 00:13:55,980
vyskočila, že v poslední době
přidán element zpátky.

296
00:13:55,980 --> 00:13:58,816
>> To je opravdu docela hodně
všechno, co je na komíny.

297
00:13:58,816 --> 00:14:00,190
Můžete je implementovat jako pole.

298
00:14:00,190 --> 00:14:01,815
Můžete je implementovat jako propojené seznamy.

299
00:14:01,815 --> 00:14:04,810
Tam jsou, samozřejmě, ostatní
způsoby, jak je také realizovat.

300
00:14:04,810 --> 00:14:09,060
V podstatě důvod, proč bychom použít
zásobníky je udržet dat takovým způsobem,

301
00:14:09,060 --> 00:14:12,090
že naposledy přidané
prvkem je první věc, kterou jsme

302
00:14:12,090 --> 00:14:14,980
bude chtít vrátit.

303
00:14:14,980 --> 00:14:17,900
Jsem Doug Lloyd, to je cs50.

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