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

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: U redu,
tako da po ovom trenutku koji ste

3
00:00:05,990 --> 00:00:09,020
vjerojatno prilično upoznat
s polja i povezane liste

4
00:00:09,020 --> 00:00:10,950
koji je dva primarna
strukture podataka koje smo

5
00:00:10,950 --> 00:00:16,810
govorio o za čuvanje seta
Podaci sličnih tipova podataka u organizaciji.

6
00:00:16,810 --> 00:00:19,080
>> Sada ćemo razgovarati
o nekoliko varijacija

7
00:00:19,080 --> 00:00:20,330
na polja i povezane liste.

8
00:00:20,330 --> 00:00:22,362
U ovom videu ćemo
razgovarati o dimnjaka.

9
00:00:22,362 --> 00:00:25,320
Naime ćemo razgovarati
o struktura podataka naziva stog.

10
00:00:25,320 --> 00:00:28,510
Podsjetimo iz prethodnih rasprava
O upućuje i memoriju,

11
00:00:28,510 --> 00:00:32,060
da je stog je također
ime za segment memorije

12
00:00:32,060 --> 00:00:34,980
gdje statički proglasio
memory-- memorije koja vas

13
00:00:34,980 --> 00:00:38,730
ime, varijable koje ime, i
cetera i funkcija okviri koje smo također

14
00:00:38,730 --> 00:00:41,000
Poziv stoga okviri postoje.

15
00:00:41,000 --> 00:00:45,421
Dakle, to je struktura stog podataka
Ne snop segment memorije.

16
00:00:45,421 --> 00:00:45,920
U REDU.

17
00:00:45,920 --> 00:00:46,890
>> No, ono što je stog?

18
00:00:46,890 --> 00:00:49,220
Dakle, to je prilično mnogo samo
posebna vrsta strukture

19
00:00:49,220 --> 00:00:51,190
koji održava podatke na organiziran način.

20
00:00:51,190 --> 00:00:53,760
A tu je dvije vrlo
uobičajene načine za provedbu

21
00:00:53,760 --> 00:00:57,380
hrpe pomoću dvije strukture podataka
da smo već upoznati s,

22
00:00:57,380 --> 00:01:00,340
polja i povezane liste.

23
00:01:00,340 --> 00:01:04,430
Što čini stog posebna je
Način na koji smo stavili podatke

24
00:01:04,430 --> 00:01:08,200
u stog, a način na koji se
ukloniti podatke iz dimnjaka.

25
00:01:08,200 --> 00:01:11,600
Posebno s hrpom
pravilo je samo najviše

26
00:01:11,600 --> 00:01:15,830
Nedavno dodan element može biti uklonjena.

27
00:01:15,830 --> 00:01:17,660
>> Dakle, razmišljam o tome kao da je snop.

28
00:01:17,660 --> 00:01:21,170
Mi piling podatke
na vrhu sebi,

29
00:01:21,170 --> 00:01:24,271
a samo stvar na vrhu
pilota može biti uklonjena.

30
00:01:24,271 --> 00:01:27,020
Ne možemo ukloniti stvar ispod
jer sve drugo bi

31
00:01:27,020 --> 00:01:28,020
propasti i pasti.

32
00:01:28,020 --> 00:01:32,580
Tako smo zapravo gradi stog da
ćemo onda morati ukloniti komad po komad.

33
00:01:32,580 --> 00:01:36,590
Zbog toga smo često odnose
na stog kao LIFO strukture,

34
00:01:36,590 --> 00:01:38,940
trajati u, prvi van.

35
00:01:38,940 --> 00:01:42,290
LIFO, trajati u, prvi van.

36
00:01:42,290 --> 00:01:45,635
>> Dakle, zbog ovog ograničenja
Kako informacije mogu se dodati

37
00:01:45,635 --> 00:01:49,080
i uklonjen iz dimnjaka, tu je stvarno
samo dvije stvari koje možete učiniti s hrpom.

38
00:01:49,080 --> 00:01:52,010
Možemo gurnuti, koji je
Izraz koji koristimo za dodavanje

39
00:01:52,010 --> 00:01:55,130
novi element na vrhu
stog, ili ako je stog ne postoji

40
00:01:55,130 --> 00:01:58,550
a mi smo ga stvara od nule,
stvara snop na prvom mjestu

41
00:01:58,550 --> 00:02:00,110
će biti poduzetan.

42
00:02:00,110 --> 00:02:04,990
I onda pop, to je vrsta CS
Pojam koristimo ukloniti posljednje

43
00:02:04,990 --> 00:02:08,330
dodao elementa s vrha dimnjaka.

44
00:02:08,330 --> 00:02:11,130
>> Tako ćemo pogledati kako
implementacije, i niz temelji

45
00:02:11,130 --> 00:02:13,120
i povezani popis temelji.

46
00:02:13,120 --> 00:02:14,870
I idemo
početi s nizom temelji.

47
00:02:14,870 --> 00:02:19,990
Dakle ovdje je osnovna ideja o tome što
Niz temelji struktura snop podataka

48
00:02:19,990 --> 00:02:21,140
će izgledati.

49
00:02:21,140 --> 00:02:23,740
Imamo definiciju upisali ovdje.

50
00:02:23,740 --> 00:02:27,790
Unutar da imamo dva člana
ili područja strukture.

51
00:02:27,790 --> 00:02:29,880
Imamo niz.

52
00:02:29,880 --> 00:02:32,400
I opet sam pomoću
proizvoljna tip podataka vrijednost.

53
00:02:32,400 --> 00:02:35,180
>> Dakle, to može biti bilo koji tip podataka,
int char ili neke druge podatke

54
00:02:35,180 --> 00:02:37,080
upišite ste prethodno stvorili.

55
00:02:37,080 --> 00:02:39,861
Dakle, imamo niz veličine kapaciteta.

56
00:02:39,861 --> 00:02:44,010
Kapacitet se funta definirana stalna,
možda negdje drugdje u našoj datoteci.

57
00:02:44,010 --> 00:02:47,550
Dakle, primijetite već s ovom
Provedba smo granični

58
00:02:47,550 --> 00:02:49,800
sami kao što je obično
slučaj s polja,

59
00:02:49,800 --> 00:02:53,170
koji se ne može dinamički mijenjati veličinu,
gdje postoji određeni broj

60
00:02:53,170 --> 00:02:55,450
elemenata koji najviše
možemo staviti u našem stog.

61
00:02:55,450 --> 00:02:57,930
U ovom slučaju to je elemente kapaciteta.

62
00:02:57,930 --> 00:03:00,310
>> Također smo pratiti
na vrhu dimnjaka.

63
00:03:00,310 --> 00:03:04,350
Koji element je najviše
Nedavno dodani stog?

64
00:03:04,350 --> 00:03:07,470
I tako smo pratiti kako
u varijablu naziva vrhu.

65
00:03:07,470 --> 00:03:11,692
I sve to dobiva zamotan zajedno
u novu vrstu podataka naziva stog.

66
00:03:11,692 --> 00:03:13,400
I jednom smo stvorili
ovaj novi tip podataka

67
00:03:13,400 --> 00:03:15,410
možemo ga tretirati kao
bilo koje druge vrste podataka.

68
00:03:15,410 --> 00:03:20,970
Možemo proglasiti stog s, baš kao i
smo mogli učiniti int x, y ili char.

69
00:03:20,970 --> 00:03:22,990
A kada kažemo stog
e, i što se događa

70
00:03:22,990 --> 00:03:26,420
je smo dobili set
memorije izdvojiti za nas.

71
00:03:26,420 --> 00:03:28,770
>> U ovom slučaju svojstvu
Ja očito nisam odlučila

72
00:03:28,770 --> 00:03:33,470
10 jer sam dobio
jedna varijabla tipa stog

73
00:03:33,470 --> 00:03:35,320
koji sadrži dva polja sjetiti.

74
00:03:35,320 --> 00:03:38,330
Niz, u ovom slučaju ide
se niz brojeva

75
00:03:38,330 --> 00:03:40,440
kao što je slučaj u većini mojih primjera.

76
00:03:40,440 --> 00:03:43,996
I još jedna varijabla broj
sposoban za pohranu na vrhu,

77
00:03:43,996 --> 00:03:45,870
najviše je nedavno dodao
element dimnjaka.

78
00:03:45,870 --> 00:03:50,290
Dakle, jedan jedini snop što smo
Samo definirana izgleda ovako.

79
00:03:50,290 --> 00:03:53,190
To je kutija
niz od 10 što

80
00:03:53,190 --> 00:03:57,280
će biti integers u ovom slučaju i
još jedna varijabla ima cijeli zeleno

81
00:03:57,280 --> 00:04:00,010
ukazati na vrhu dimnjaka.

82
00:04:00,010 --> 00:04:02,600
>> Za postavljanje vrhu
stog mi samo reći s.top.

83
00:04:02,600 --> 00:04:04,890
Tako ćemo pristupiti
Područje opoziva strukture.

84
00:04:04,890 --> 00:04:10,460
s.top jednak 0 učinkovito
to čini na naše stog.

85
00:04:10,460 --> 00:04:12,960
Dakle, opet imamo dvije operacije
da možemo obaviti danas.

86
00:04:12,960 --> 00:04:14,270
Možemo gurnuti i mi možemo pop.

87
00:04:14,270 --> 00:04:15,635
Počnimo s pritiskom.

88
00:04:15,635 --> 00:04:18,260
Opet, pritom je dodao novi
Element na vrhu snopa.

89
00:04:18,260 --> 00:04:21,460
>> Dakle, ono što trebamo učiniti u
ovaj niz se temelji primjena?

90
00:04:21,460 --> 00:04:23,210
Pa općenito
funkcija push ide

91
00:04:23,210 --> 00:04:26,160
morati prihvatiti
pokazivač na stog.

92
00:04:26,160 --> 00:04:28,610
Sada uzmi drugi i razmišljati o tome.

93
00:04:28,610 --> 00:04:32,840
Zašto bi želimo prihvatiti
pokazivač na stog?

94
00:04:32,840 --> 00:04:36,830
Podsjetimo iz prethodnih videa na
promjenjiva opseg i naputke,

95
00:04:36,830 --> 00:04:42,350
što će se dogoditi ako mi samo poslali
stog, s dosta u kao parametar?

96
00:04:42,350 --> 00:04:45,770
Što bi zapravo biti donesen tamo?

97
00:04:45,770 --> 00:04:49,430
Zapamti mi stvara kopiju
kad smo ga proći u funkciji

98
00:04:49,430 --> 00:04:51,160
osim ako koristimo naputke.

99
00:04:51,160 --> 00:04:55,380
I tako ova funkcija gurnuti potrebama
prihvatiti pokazivač na stog

100
00:04:55,380 --> 00:04:59,160
tako da smo zapravo mijenja
stog namjeravamo mijenjati.

101
00:04:59,160 --> 00:05:03,060
>> Druga stvar gurati vjerojatno želi
prihvatiti je element podataka tipa vrijednosti.

102
00:05:03,060 --> 00:05:06,970
U tom slučaju, jednom, cijeli broj koji
ćemo dodati na vrhu dimnjaka.

103
00:05:06,970 --> 00:05:08,680
Dakle, imamo naše dvije parametre.

104
00:05:08,680 --> 00:05:11,310
Što ćemo
Sada to unutar pritiskom?

105
00:05:11,310 --> 00:05:14,860
Pa, jednostavno, samo ćemo dodati
taj element na vrhu snopa

106
00:05:14,860 --> 00:05:22,860
a zatim promijenite gdje vrh
snop je da s točke vrh vrijednosti.

107
00:05:22,860 --> 00:05:25,639
Dakle, to je ono funkcija
prijava za guranje

108
00:05:25,639 --> 00:05:27,680
možda izgledati u
Niz-based implementacije.

109
00:05:27,680 --> 00:05:30,967
>> Opet to nije teško i brzo pravilo
koji bi mogao promijeniti ovaj i imaju

110
00:05:30,967 --> 00:05:32,050
varira na različite načine.

111
00:05:32,050 --> 00:05:33,840
Možda je proglašen na globalnoj razini.

112
00:05:33,840 --> 00:05:36,180
I tako da ne morate čak ni
proći što je kao parametar.

113
00:05:36,180 --> 00:05:39,125
To je opet samo
Općenito slučaj za guranje.

114
00:05:39,125 --> 00:05:41,000
A tu su i različite
načina da ga provede.

115
00:05:41,000 --> 00:05:42,810
No, u ovom slučaju naš
Pritisni će potrajati

116
00:05:42,810 --> 00:05:48,540
dva argumenta, pointer na hrpu i
element podataka tipa integer vrijednost,

117
00:05:48,540 --> 00:05:49,840
u ovom slučaju.

118
00:05:49,840 --> 00:05:52,100
>> Tako smo proglasili S, mi
rekao s.top jednak 0.

119
00:05:52,100 --> 00:05:55,969
Sada gurnite
Broj 28 na stog.

120
00:05:55,969 --> 00:05:57,010
Pa što to znači?

121
00:05:57,010 --> 00:05:59,600
Pa trenutno
vrhu snopa 0.

122
00:05:59,600 --> 00:06:01,350
I tako ono što je u osnovi
će se dogoditi je

123
00:06:01,350 --> 00:06:05,820
ćemo staviti broj
28 u polja položaj 0.

124
00:06:05,820 --> 00:06:09,540
Prilično jednostavan, zar ne, da je
bio vrh, a sada smo si dobar to ići.

125
00:06:09,540 --> 00:06:12,910
I onda moramo promijeniti ono što
na vrhu dimnjaka će biti.

126
00:06:12,910 --> 00:06:15,130
Tako da sljedeći put
guramo element u,

127
00:06:15,130 --> 00:06:18,017
ćemo ga pohraniti u
Položaj polje, vjerojatno nije 0.

128
00:06:18,017 --> 00:06:20,100
Mi ne želite prebrisati
što smo upravo tamo stavili.

129
00:06:20,100 --> 00:06:23,510
I tako ćemo samo premjestiti na vrh na 1.

130
00:06:23,510 --> 00:06:24,890
To vjerojatno ima smisla.

131
00:06:24,890 --> 00:06:28,940
>> Sada, ako želimo staviti još jedan element
na stog, kažu želimo gurati 33,

132
00:06:28,940 --> 00:06:33,190
i sad mi samo uzeti 33
i staviti ga na mjesto broj polja

133
00:06:33,190 --> 00:06:37,580
1, a zatim promijenite vrhu naše
stog se niz lokacija broj dva.

134
00:06:37,580 --> 00:06:40,650
Dakle, ako sljedeći put želimo
gurati element na stog,

135
00:06:40,650 --> 00:06:43,087
to će se staviti u položaj 2 polja.

136
00:06:43,087 --> 00:06:44,420
I neka je učiniti da se još jednom.

137
00:06:44,420 --> 00:06:45,753
Mi ćemo gurnuti 19 off od hrpe.

138
00:06:45,753 --> 00:06:48,940
Mi ćemo staviti 19 u polja položaju 2
i promijeniti na vrhu naše stog

139
00:06:48,940 --> 00:06:51,220
se niz lokacija 3
pa ako se sljedeći put

140
00:06:51,220 --> 00:06:54,780
trebate napraviti poticaj da si dobar to ići.

141
00:06:54,780 --> 00:06:56,980
>> U redu, tako da je gura u malom.

142
00:06:56,980 --> 00:06:57,830
Što je iskakanje?

143
00:06:57,830 --> 00:07:00,240
Dakle iskakanje je vrsta
kolega na guranje.

144
00:07:00,240 --> 00:07:02,720
To je kako smo ukloniti podatke iz dimnjaka.

145
00:07:02,720 --> 00:07:04,610
I općenito pop potrebama
učiniti sljedeće.

146
00:07:04,610 --> 00:07:07,600
To treba prihvatiti pokazivač do
stog, opet u općenitom slučaju.

147
00:07:07,600 --> 00:07:10,480
U nekom drugom slučaju možda
proglasio stog na globalnoj razini,

148
00:07:10,480 --> 00:07:13,910
u tom slučaju ne morate proći
u jer već ima pristup do njega

149
00:07:13,910 --> 00:07:15,541
kao globalna varijabla.

150
00:07:15,541 --> 00:07:17,040
Ali onda što još trebamo napraviti?

151
00:07:17,040 --> 00:07:21,000
Pa smo se povećavati
vrh dimnjaka u guranje,

152
00:07:21,000 --> 00:07:24,050
tako da smo vjerojatno idući u ištanje
da dekrementirati vrhu snopa

153
00:07:24,050 --> 00:07:25,009
pop, zar ne?

154
00:07:25,009 --> 00:07:26,800
I onda, naravno,
također ćete želite

155
00:07:26,800 --> 00:07:29,240
vratiti vrijednosti koje smo uklonili.

156
00:07:29,240 --> 00:07:32,125
Ako ste se dodavanjem elemenata, želimo
dobiti elemente iz kasnije,

157
00:07:32,125 --> 00:07:34,000
vjerojatno je zapravo
želite ih spremiti tako da

158
00:07:34,000 --> 00:07:36,490
ne samo ih izbrisati iz
stog a zatim učinite ništa s njima.

159
00:07:36,490 --> 00:07:38,500
Općenito, ako smo
guranje i iskakanje ovdje

160
00:07:38,500 --> 00:07:41,250
želimo pohraniti
Informacije na smislen način

161
00:07:41,250 --> 00:07:43,250
pa to ne čine
smisla samo ga odbaciti.

162
00:07:43,250 --> 00:07:46,380
Dakle, ova funkcija trebala
vjerojatno vratiti vrijednost za nas.

163
00:07:46,380 --> 00:07:51,040
>> Dakle, to je ono što je deklaracija za pop
Možda izgleda kao da se u gornjem lijevom.

164
00:07:51,040 --> 00:07:53,870
Ova funkcija vraća
Podaci tipa vrijednosti.

165
00:07:53,870 --> 00:07:56,320
Opet smo bili pomoću
integers tijekom.

166
00:07:56,320 --> 00:08:01,916
I to prihvaća pokazivač na stog kao
njezin jedini argument ili jedini parametar.

167
00:08:01,916 --> 00:08:03,040
Dakle, ono što je pop učiniti?

168
00:08:03,040 --> 00:08:07,990
Recimo da želimo sada
pop element off s.

169
00:08:07,990 --> 00:08:14,000
Dakle, zapamtite što sam rekao da su prošle hrpe
u, prvi van, LIFO strukture podataka.

170
00:08:14,000 --> 00:08:17,855
Element koji će
ukloniti iz dimnjaka?

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

172
00:08:21,780 --> 00:08:24,150
Jeste li pogoditi 19?

173
00:08:24,150 --> 00:08:25,290
Zato što bi u pravu.

174
00:08:25,290 --> 00:08:28,836
19 je bio posljednji element dodali smo na
stog kad smo pritom elemente na,

175
00:08:28,836 --> 00:08:31,210
pa to će prvi
element koji dobiva uklonjen.

176
00:08:31,210 --> 00:08:34,780
To je kao da smo rekli 28, a
onda smo stavili 33 na vrhu,

177
00:08:34,780 --> 00:08:36,659
i stavili smo 19 na vrhu toga.

178
00:08:36,659 --> 00:08:40,650
Jedini element koji možemo poletjeti je 19.

179
00:08:40,650 --> 00:08:45,019
>> Sada u dijagramu ovdje ono što sam učinio
je vrsta izbrisani 19 iz polja.

180
00:08:45,019 --> 00:08:46,810
To nije zapravo
što ćemo učiniti.

181
00:08:46,810 --> 00:08:48,934
Samo ćemo se vrste
od pretvarati da ne postoji.

182
00:08:48,934 --> 00:08:51,441
To je još uvijek tamo u
to mjesto u memoriji,

183
00:08:51,441 --> 00:08:54,190
ali mi jednostavno ide ignorirati
promjenom vrh našeg dimnjaka

184
00:08:54,190 --> 00:08:56,080
od toga 3 na 2.

185
00:08:56,080 --> 00:08:58,720
Dakle, ako bismo sada gurnuti
još jedan element na stack,

186
00:08:58,720 --> 00:09:00,720
to bi više pisati 19.

187
00:09:00,720 --> 00:09:03,990
>> Ali nemojmo ići kroz nevolje
brisanja 19 iz dimnjaka.

188
00:09:03,990 --> 00:09:05,830
Mi samo možemo se pretvarati da ne postoji.

189
00:09:05,830 --> 00:09:11,107
Za potrebe stog što je otišao, ako
mijenjamo vrh da bude 2 umjesto 3.

190
00:09:11,107 --> 00:09:12,690
U redu, tako da je uglavnom to.

191
00:09:12,690 --> 00:09:15,080
To je sve što trebamo učiniti
pop element off.

192
00:09:15,080 --> 00:09:16,090
Idemo to učiniti opet.

193
00:09:16,090 --> 00:09:18,610
Pa sam ga istaknute crvenom bojom ovdje da
ukazuju činimo drugi poziv.

194
00:09:18,610 --> 00:09:19,720
Mi ćemo učiniti istu stvar.

195
00:09:19,720 --> 00:09:20,803
>> Dakle, što će se dogoditi?

196
00:09:20,803 --> 00:09:23,670
Pa, idemo za pohranu
33 u X i idemo

197
00:09:23,670 --> 00:09:26,217
za promjenu vrhu snopa do 1.

198
00:09:26,217 --> 00:09:29,050
Tako da, ako smo sada gurne
Element u stog što smo

199
00:09:29,050 --> 00:09:31,610
učiniti upravo sada,
što će se dogoditi

200
00:09:31,610 --> 00:09:36,367
se idemo prebrisati
Niz položaj broj 1.

201
00:09:36,367 --> 00:09:38,950
Tako da 33 koja je vrsta ostavi
iza toga smo samo pretvarao

202
00:09:38,950 --> 00:09:44,390
ne postoji više, samo mi ide
to clobber i staviti 40 tamo umjesto.

203
00:09:44,390 --> 00:09:46,290
I onda, naravno,
jer smo napravili gurati,

204
00:09:46,290 --> 00:09:48,780
ćemo povećajte
vrhu snopa 1-2

205
00:09:48,780 --> 00:09:50,950
tako da ako mi sada dodati
još jedan element da će

206
00:09:50,950 --> 00:09:54,700
ići u polja mjesto broj dva.

207
00:09:54,700 --> 00:09:57,590
>> Sada povezani popisi su drugi
način provoditi hrpe.

208
00:09:57,590 --> 00:10:01,210
A ako ovoj definiciji as
Zaslon ovdje izgleda poznato na vas,

209
00:10:01,210 --> 00:10:04,260
to je zato što izgleda gotovo
isti, u stvari,

210
00:10:04,260 --> 00:10:07,790
to prilično mnogo je točno
Isto kao popis za pojedinačno povezani,

211
00:10:07,790 --> 00:10:11,990
ako sjetiti iz naše rasprave o
pojedinačno povezane liste u drugom videu.

212
00:10:11,990 --> 00:10:15,510
Jedino ograničenje ovdje
je za nas kao programera,

213
00:10:15,510 --> 00:10:17,900
nećemo dopustiti da
umetanje ili brisanje slučajno

214
00:10:17,900 --> 00:10:20,620
Na popisu pojedinačno povezan
koje smo prethodno mogli učiniti.

215
00:10:20,620 --> 00:10:25,820
Možemo tek sada umetnuti i izbrisati iz
prednje ili na vrhu povezani

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

217
00:10:26,320 --> 00:10:28,028
To je stvarno jedini
Razlika ipak.

218
00:10:28,028 --> 00:10:29,700
To je inače List pojedinačno povezani.

219
00:10:29,700 --> 00:10:32,060
To je samo ograničenje
zamijenivši na sebe

220
00:10:32,060 --> 00:10:35,770
kao programera koji
ga mijenja u stog.

221
00:10:35,770 --> 00:10:39,280
>> Pravilo je da se ovdje uvijek održavati
pokazivač na glavu popisa povezane.

222
00:10:39,280 --> 00:10:41,520
To je, naravno, općenito
važno pravilo prvi.

223
00:10:41,520 --> 00:10:44,260
Za pojedinačno povezani ionako vam popis
samo trebate pokazivač u glavu

224
00:10:44,260 --> 00:10:46,160
kako bi se taj
lanac moći uputiti

225
00:10:46,160 --> 00:10:48,596
na svakom drugom elementu
na popisu povezane.

226
00:10:48,596 --> 00:10:50,470
Ali to je osobito
važno s hrpom.

227
00:10:50,470 --> 00:10:52,386
I tako uglavnom si
će zapravo žele

228
00:10:52,386 --> 00:10:54,090
ovo pokazivač se globalna varijabla.

229
00:10:54,090 --> 00:10:56,574
Vjerojatno će
biti još lakše na taj način.

230
00:10:56,574 --> 00:10:58,240
Pa što su analozi guranje i pop?

231
00:10:58,240 --> 00:10:58,740
Tako je.

232
00:10:58,740 --> 00:11:01,812
Pa opet gura se dodavanjem
novi element na stack.

233
00:11:01,812 --> 00:11:03,770
Na popisu povezani da
znači da ćemo imati

234
00:11:03,770 --> 00:11:07,770
stvoriti novi čvor koji smo
će dodati na popis povezani,

235
00:11:07,770 --> 00:11:10,500
a zatim slijedite korake pažljive
koje smo prethodno navedeno

236
00:11:10,500 --> 00:11:16,050
u pojedinačno povezanim popisima biste ga dodali na
lanac bez razbijanje lanca

237
00:11:16,050 --> 00:11:18,900
i gubitka ili orphaning bilo
Elementi popisa povezani.

238
00:11:18,900 --> 00:11:21,820
I to je zapravo ono koje
Malo blob teksta postoji sažima.

239
00:11:21,820 --> 00:11:23,740
I neka je pogledati
na to kao dijagram.

240
00:11:23,740 --> 00:11:24,823
>> Dakle, ovdje je naš popis povezani.

241
00:11:24,823 --> 00:11:26,620
On istodobno sadrži četiri elementa.

242
00:11:26,620 --> 00:11:30,420
I više savršeno ovdje je naš
stog sadrži četiri elementa.

243
00:11:30,420 --> 00:11:36,030
I recimo da sada žele
guranje nove stavke na ovu hrpu.

244
00:11:36,030 --> 00:11:39,792
I želimo gurati novi
Stavka čijim podacima je vrijednost 12.

245
00:11:39,792 --> 00:11:41,000
Pa što ćemo učiniti?

246
00:11:41,000 --> 00:11:43,420
Pa prvo ćemo
malloc prostor, dinamički

247
00:11:43,420 --> 00:11:45,411
izdvojiti prostor za novi čvor.

248
00:11:45,411 --> 00:11:48,160
I naravno odmah nakon
smo uputili poziv da mi se uvijek malloc

249
00:11:48,160 --> 00:11:52,989
pobrinite se da provjerite za ništa,
jer ako smo null natrag

250
00:11:52,989 --> 00:11:54,280
postoji neka vrsta problema.

251
00:11:54,280 --> 00:11:57,570
Mi ne želimo dereference tom null
pokazivač ili ćete trpjeti grešku SEG.

252
00:11:57,570 --> 00:11:58,510
To nije dobro.

253
00:11:58,510 --> 00:11:59,760
Tako smo malloced čvora.

254
00:11:59,760 --> 00:12:01,260
Mi ćemo pretpostaviti da smo imali uspjeha ovdje.

255
00:12:01,260 --> 00:12:06,090
Idemo staviti 12 u
polje podataka tog čvora.

256
00:12:06,090 --> 00:12:11,570
Sada Sjećate li se koji od naših pokazivača
se sada tako da ne razbiti lanac?

257
00:12:11,570 --> 00:12:15,100
Imamo nekoliko mogućnosti, ali ovdje
jedini koji će se sigurno

258
00:12:15,100 --> 00:12:19,330
je postaviti sljedeća vijest pokazivač
točka na staru glavu na popis

259
00:12:19,330 --> 00:12:21,360
ili što će uskoro biti
Stari šef na popisu.

260
00:12:21,360 --> 00:12:23,610
I sada da svi naši
elementi ulancane,

261
00:12:23,610 --> 00:12:27,370
mi samo može kretati popis ukazati
na istom mjestu da nova radi.

262
00:12:27,370 --> 00:12:33,550
I sada smo uspješno gurnuo
Novi element na prednjem dijelu dimnjaka.

263
00:12:33,550 --> 00:12:36,420
>> Da mi pop jednostavno želite
izbrišite taj prvi element.

264
00:12:36,420 --> 00:12:38,150
I tako u osnovi ono
moramo učiniti ovdje,

265
00:12:38,150 --> 00:12:40,050
i moramo naći drugi element.

266
00:12:40,050 --> 00:12:43,540
Na kraju da će postati novi
glavu nakon što izbrišete prvi.

267
00:12:43,540 --> 00:12:47,300
Dakle, samo mi treba početi od
početak, kretati jedan naprijed.

268
00:12:47,300 --> 00:12:50,340
Nakon što smo dobili držite na jednom
naprijed gdje smo trenutno

269
00:12:50,340 --> 00:12:53,850
jesmo možete izbrisati prvi sigurno
a onda mi samo možemo pomaknuti glavu

270
00:12:53,850 --> 00:12:57,150
ukazati na ono što je bio
Drugi pojam, a onda sada

271
00:12:57,150 --> 00:12:59,170
je prvi nakon toga
čvor je izbrisana.

272
00:12:59,170 --> 00:13:01,160
>> Pa opet, uzimajući pogled
na to kao dijagram smo

273
00:13:01,160 --> 00:13:05,022
želim sada pop
Element s ovog stog.

274
00:13:05,022 --> 00:13:05,730
Dakle, što nam je činiti?

275
00:13:05,730 --> 00:13:08,188
Pa mi smo prvi će stvoriti
novi pokazivač što se događa

276
00:13:08,188 --> 00:13:10,940
ukazati na istom mjestu kao i glave.

277
00:13:10,940 --> 00:13:13,790
Ćemo ga pomaknuti za jedno mjesto
naprijed rekavši Trav equals

278
00:13:13,790 --> 00:13:17,510
Trav sljedeći primjer, koji
će unaprijediti Trav pokazivač jedan

279
00:13:17,510 --> 00:13:19,324
Položaj naprijed.

280
00:13:19,324 --> 00:13:21,240
Sada kada smo dobili
držite na prvom elementu

281
00:13:21,240 --> 00:13:24,573
kroz pokazivač naziva liste, a
drugi element kroz pokazivač naziva

282
00:13:24,573 --> 00:13:28,692
trav, sa sigurnošću možemo izbrisati to
Prvi element iz dimnjaka

283
00:13:28,692 --> 00:13:30,650
bez gubljenja ostalo
lanca, jer mi

284
00:13:30,650 --> 00:13:32,358
su način da se odnosi
na drugi element

285
00:13:32,358 --> 00:13:34,780
proslijediti putem od
pokazivač zove Trav.

286
00:13:34,780 --> 00:13:37,100
>> Tako sada možemo osloboditi taj čvor.

287
00:13:37,100 --> 00:13:38,404
Mi možemo besplatno popis.

288
00:13:38,404 --> 00:13:41,320
I onda sve što trebate učiniti je
premjestiti popis točku na istom mjestu

289
00:13:41,320 --> 00:13:44,482
da trav radi, a mi smo nekako vratiti
gdje smo počeli prije gurnuo 12

290
00:13:44,482 --> 00:13:45,690
na prvo mjesto, zar ne.

291
00:13:45,690 --> 00:13:46,940
To je točno gdje smo bili.

292
00:13:46,940 --> 00:13:48,840
Imali smo četiri elementa stog.

293
00:13:48,840 --> 00:13:49,690
Dodali smo petinu.

294
00:13:49,690 --> 00:13:51,910
Gurnuo mi petinu
Element, a zatim smo

295
00:13:51,910 --> 00:13:55,980
ubaci koji je nedavno
dodao elemente back off.

296
00:13:55,980 --> 00:13:58,816
>> To je stvarno prilično mnogo
sve što se gomila.

297
00:13:58,816 --> 00:14:00,190
Možete ih implementirati kao polja.

298
00:14:00,190 --> 00:14:01,815
Možete ih implementirati kao povezane liste.

299
00:14:01,815 --> 00:14:04,810
Postoji, naravno, drugi
načine kako ih implementirati kao dobro.

300
00:14:04,810 --> 00:14:09,060
Uglavnom je razlog što će koristiti
hrpe je održavanje podataka na takav način

301
00:14:09,060 --> 00:14:12,090
da je nedavno dodao
element je prva stvar smo

302
00:14:12,090 --> 00:14:14,980
će htjeti vratiti.

303
00:14:14,980 --> 00:14:17,900
Ja sam Doug Lloyd, ovo je cs50.

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