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

2
00:00:04,074 --> 00:00:05,990
DOUG Lloyd: Hyvä,
joten tässä kohdassa olet

3
00:00:05,990 --> 00:00:09,020
luultavasti tuttuja
jossa paneelit ja liittyvät luettelot

4
00:00:09,020 --> 00:00:10,950
joka on kaksi pääasiallista
tietorakenteita olemme

5
00:00:10,950 --> 00:00:16,810
puhui pitää sarjaa
tiedot samankaltaisten tietotyyppejä järjestetty.

6
00:00:16,810 --> 00:00:19,080
>> Nyt aiomme puhua
noin pari muunnelmia

7
00:00:19,080 --> 00:00:20,330
koskevat taulukot ja linkitettyjen listojen.

8
00:00:20,330 --> 00:00:22,362
Tässä videossa olemme menossa
puhua pinot.

9
00:00:22,362 --> 00:00:25,320
Erityisesti aiomme puhua
noin datarakenne kutsutaan pino.

10
00:00:25,320 --> 00:00:28,510
Recall aiempiin keskusteluihin
noin viitteitä ja muisti,

11
00:00:28,510 --> 00:00:32,060
että pino on myös
nimenne segmentin muistia

12
00:00:32,060 --> 00:00:34,980
jossa staattisesti ilmoitettu
memory-- muisti, että olet

13
00:00:34,980 --> 00:00:38,730
nimi, muuttujat annat nimeksi, et
niin edelleen ja toiminta kehyksiä, jotka olemme myös

14
00:00:38,730 --> 00:00:41,000
kutsupino kehyksiä olemassa.

15
00:00:41,000 --> 00:00:45,421
Joten tämä on pino tietorakenne
ei pino segmentti muistia.

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

17
00:00:45,920 --> 00:00:46,890
>> Mutta mikä on pino?

18
00:00:46,890 --> 00:00:49,220
Joten se on aika paljon vain
erikoinen rakenne

19
00:00:49,220 --> 00:00:51,190
joka ylläpitää tietoja järjestäytyneesti.

20
00:00:51,190 --> 00:00:53,760
Ja siellä on kaksi hyvin
yhteinen tapoja toteuttaa

21
00:00:53,760 --> 00:00:57,380
pinot kahdella tietorakenteita
että olemme jo tuttuja,

22
00:00:57,380 --> 00:01:00,340
taulukot ja linkitettyjen listojen.

23
00:01:00,340 --> 00:01:04,430
Mikä tekee pino erityinen on
miten laitamme tiedot

24
00:01:04,430 --> 00:01:08,200
pinoon, ja tapaamme
poistaa tietoja pinosta.

25
00:01:08,200 --> 00:01:11,600
Erityisesti pinot
sääntö on vain kaikkein

26
00:01:11,600 --> 00:01:15,830
viimeksi lisätyt elementti voidaan poistaa.

27
00:01:15,830 --> 00:01:17,660
>> Joten ajattele sitä niin kuin se on pino.

28
00:01:17,660 --> 00:01:21,170
Olemme paalutus tiedot
itsensä päälle,

29
00:01:21,170 --> 00:01:24,271
ja vain asia yläreunassa
paalun voidaan poistaa.

30
00:01:24,271 --> 00:01:27,020
Emme voi poistaa asia alla
koska kaikki muu olisi

31
00:01:27,020 --> 00:01:28,020
romahtaa ja kaatua.

32
00:01:28,020 --> 00:01:32,580
Joten me todella olemme rakentamassa pinon
Sitten täytyy poistaa pala palalta.

33
00:01:32,580 --> 00:01:36,590
Tämän vuoksi me yleensä viitataan
pinoon niin LIFO rakenne,

34
00:01:36,590 --> 00:01:38,940
last in, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, last in, first out.

36
00:01:42,290 --> 00:01:45,635
>> Joten koska tämä rajoitus
miten tieto voidaan lisätä

37
00:01:45,635 --> 00:01:49,080
ja poistetaan pinosta, siellä oikeastaan
vain kaksi asiaa voimme tehdä pino.

38
00:01:49,080 --> 00:01:52,010
Voimme työntää, joka on
termi käytämme lisäämiseen

39
00:01:52,010 --> 00:01:55,130
uusi elementti alkuun
pino, tai jos pino ei ole olemassa

40
00:01:55,130 --> 00:01:58,550
ja Luomme sitä tyhjästä,
luodaan pino ensinnäkin

41
00:01:58,550 --> 00:02:00,110
olisi ajaa.

42
00:02:00,110 --> 00:02:04,990
Ja sitten pop, että on sellainen CS
termi käytämme poistaa viimeksi

43
00:02:04,990 --> 00:02:08,330
lisätään elementti ylhäältä pinon.

44
00:02:08,330 --> 00:02:11,130
>> Joten olemme menossa katsomaan molemmat
toteutukset, molemmat array perustuu

45
00:02:11,130 --> 00:02:13,120
ja linkitetty lista perustuu.

46
00:02:13,120 --> 00:02:14,870
Ja aiomme
aloittaa array perustuu.

47
00:02:14,870 --> 00:02:19,990
Joten tässä on perusajatus, mitä
array perustuu pino tietorakennetta

48
00:02:19,990 --> 00:02:21,140
näyttäisi.

49
00:02:21,140 --> 00:02:23,740
Meillä kirjoitetut määritelmä täällä.

50
00:02:23,740 --> 00:02:27,790
Sisältä että meillä on kaksi jäsentä
tai kenttiä rakenteen.

51
00:02:27,790 --> 00:02:29,880
Meillä jono.

52
00:02:29,880 --> 00:02:32,400
Ja taas olen käyttäen
mielivaltaista tietotyyppi arvo.

53
00:02:32,400 --> 00:02:35,180
>> Joten tämä voisi olla mikä tahansa tietotyyppi,
int char tai eräitä muita tietoja

54
00:02:35,180 --> 00:02:37,080
Kirjoita olet aiemmin luonut.

55
00:02:37,080 --> 00:02:39,861
Joten meillä on taulukon koko kapasiteetin.

56
00:02:39,861 --> 00:02:44,010
Kapasiteetti punta määritelty vakio,
ehkä jossain muualla meidän tiedostoon.

57
00:02:44,010 --> 00:02:47,550
Niin huomaa jo tämän tietyn
täytäntöönpano olemme rajaava

58
00:02:47,550 --> 00:02:49,800
itsemme oli tyypillisesti
tapauksessa paneelit,

59
00:02:49,800 --> 00:02:53,170
joita emme voi dynaamisesti muuttaa,
missä on joitakin

60
00:02:53,170 --> 00:02:55,450
elementtien maksimi että
voimme laittaa meidän pinon.

61
00:02:55,450 --> 00:02:57,930
Tässä tapauksessa se on kapasiteettia elementtejä.

62
00:02:57,930 --> 00:03:00,310
>> Olemme myös seurata
pinon.

63
00:03:00,310 --> 00:03:04,350
Mikä elementti on kaikkein
äskettäin lisätä pinoon?

64
00:03:04,350 --> 00:03:07,470
Ja niin me seurata, että
muuttujaan nimeltä alkuun.

65
00:03:07,470 --> 00:03:11,692
Ja kaikki tämä saa käärittynä yhteen
uuteen tietotyyppi nimeltään pino.

66
00:03:11,692 --> 00:03:13,400
Ja kun me luoneet
tämä uusi tietotyyppi

67
00:03:13,400 --> 00:03:15,410
voimme käsitellä sitä kuin
muita tietoja tyyppi.

68
00:03:15,410 --> 00:03:20,970
Voimme julistaa pino s, kuten
voisimme tehdä int x, tai char y.

69
00:03:20,970 --> 00:03:22,990
Ja kun me sanomme pino
s, hyvin, mitä tapahtuu

70
00:03:22,990 --> 00:03:26,420
on saamme joukko
muisti varattu meille.

71
00:03:26,420 --> 00:03:28,770
>> Tässä tapauksessa kapasiteettia
Olen ilmeisesti päättänyt

72
00:03:28,770 --> 00:03:33,470
on 10 koska minulla
yhden muuttujan tyypin pinon

73
00:03:33,470 --> 00:03:35,320
joka sisältää kaksi kenttää muistaa.

74
00:03:35,320 --> 00:03:38,330
Array, tässä tapauksessa on menossa
olla joukko kokonaislukuja

75
00:03:38,330 --> 00:03:40,440
kuten on laita suurimman osan esimerkeistä.

76
00:03:40,440 --> 00:03:43,996
Ja toinen kokonaisluku muuttuja
kykenee tallentamaan alkuun,

77
00:03:43,996 --> 00:03:45,870
viimeksi lisätyt
elementti pino.

78
00:03:45,870 --> 00:03:50,290
Joten yksi pino mitä me
aivan määritelty näyttää seuraavalta.

79
00:03:50,290 --> 00:03:53,190
Se on laatikko sisältää
joukko 10 mitä

80
00:03:53,190 --> 00:03:57,280
on kokonaislukuja tässä tapauksessa ja
toinen kokonaisluku muuttuja siellä vihreä

81
00:03:57,280 --> 00:04:00,010
osoittamaan pinon päälle.

82
00:04:00,010 --> 00:04:02,600
>> Asettaa alkuun
pino me vain sanoa s.top.

83
00:04:02,600 --> 00:04:04,890
Näin saimme pääsyn
alan rakenne muistuttaa.

84
00:04:04,890 --> 00:04:10,460
s.top ollessa 0 tehokkaasti
ei tämä meidän pinoon.

85
00:04:10,460 --> 00:04:12,960
Joten jälleen meillä on kaksi toimintaa
että voimme tehdä nyt.

86
00:04:12,960 --> 00:04:14,270
Emme voi työntää ja voimme pop.

87
00:04:14,270 --> 00:04:15,635
Aloitetaan push.

88
00:04:15,635 --> 00:04:18,260
Jälleen työntää lisää uuden
elementti päällimmäinen.

89
00:04:18,260 --> 00:04:21,460
>> Joten mitä me tarvitsemme tehdä
tämän taulukon toteutuksesta?

90
00:04:21,460 --> 00:04:23,210
Hyvin yleisesti
push-toiminnon on menossa

91
00:04:23,210 --> 00:04:26,160
tarvitse hyväksyä
osoitin pino.

92
00:04:26,160 --> 00:04:28,610
Nyt ottaa toisen ja miettiä sitä.

93
00:04:28,610 --> 00:04:32,840
Miksi haluamme hyväksyä
osoitin pino?

94
00:04:32,840 --> 00:04:36,830
Recall edellinen videoita
kiikaritähtäimellä ja osoittimia,

95
00:04:36,830 --> 00:04:42,350
mitä tapahtuisi, jos me vain lähetetään
pino, s pikemminkin kuin parametri?

96
00:04:42,350 --> 00:04:45,770
Mitä todella välitetään siellä?

97
00:04:45,770 --> 00:04:49,430
Muista Luomme kopio
kun välitämme sen funktio

98
00:04:49,430 --> 00:04:51,160
ellemme käytä osoittimia.

99
00:04:51,160 --> 00:04:55,380
Ja niin tämä toiminto työntää tarpeisiin
hyväksyä osoitin pinoon

100
00:04:55,380 --> 00:04:59,160
niin että olemme todella muuttuu
pino aiomme muuttaa.

101
00:04:59,160 --> 00:05:03,060
>> Toinen asia push varmaan haluaa
hyväksyä on tieto tyypin arvo.

102
00:05:03,060 --> 00:05:06,970
Tässä tapauksessa, jälleen, kokonaisluku, joka
aiomme lisätä huipulle pinon.

103
00:05:06,970 --> 00:05:08,680
Joten meillä meidän kahden parametrit.

104
00:05:08,680 --> 00:05:11,310
Mitä aiomme
nyt tehdä sisällä push?

105
00:05:11,310 --> 00:05:14,860
No, yksinkertaisesti, me vain aio lisätä
että elementti huipulle pinon

106
00:05:14,860 --> 00:05:22,860
ja sitten muuttaa, jos alkuun
pino on, että s piste alkuun arvo.

107
00:05:22,860 --> 00:05:25,639
Joten tämä on mitä funktio
ilmoitus push

108
00:05:25,639 --> 00:05:27,680
voisi näyttää vuonna
array-pohjainen toteuttamista.

109
00:05:27,680 --> 00:05:30,967
>> Tämäkään ei ole kova ja nopea sääntö
että voisit muuttaa tätä ja on

110
00:05:30,967 --> 00:05:32,050
se vaihtelee eri tavoin.

111
00:05:32,050 --> 00:05:33,840
Ehkä s julistetaan maailmanlaajuisesti.

112
00:05:33,840 --> 00:05:36,180
Ja niin sinun ei tarvitse edes
siirtää se on parametrina.

113
00:05:36,180 --> 00:05:39,125
Tämä on jälleen vain
Yleinen tapaus push.

114
00:05:39,125 --> 00:05:41,000
Ja on olemassa erilaisia
tapoja toteuttaa se.

115
00:05:41,000 --> 00:05:42,810
Mutta tässä tapauksessa meidän
push vie

116
00:05:42,810 --> 00:05:48,540
kaksi argumenttia, osoitin pino ja
tieto tyypin arvo, kokonaisluku

117
00:05:48,540 --> 00:05:49,840
tässä tapauksessa.

118
00:05:49,840 --> 00:05:52,100
>> Joten me julisti s, me
sanoi s.top ollessa 0.

119
00:05:52,100 --> 00:05:55,969
Nyt työnnä
numero 28 pinoon.

120
00:05:55,969 --> 00:05:57,010
No mitä se tarkoittaa?

121
00:05:57,010 --> 00:05:59,600
No tällä hetkellä
pinon on 0.

122
00:05:59,600 --> 00:06:01,350
Ja niin mitä pohjimmiltaan
tulee tapahtumaan on

123
00:06:01,350 --> 00:06:05,820
aiomme pysyä numero
28 osaksi array sijainti 0.

124
00:06:05,820 --> 00:06:09,540
Melko yksinkertainen, oikea, että
oli alkuun ja nyt olemme hyvä mennä.

125
00:06:09,540 --> 00:06:12,910
Ja sitten meidän täytyy muuttaa mitä
päällimmäinen on.

126
00:06:12,910 --> 00:06:15,130
Niin että seuraavan kerran
me push elementti,

127
00:06:15,130 --> 00:06:18,017
aiomme tallentaa sen
array sijainti, luultavasti ei 0.

128
00:06:18,017 --> 00:06:20,100
Emme halua korvata
mitä me vain laittaa sinne.

129
00:06:20,100 --> 00:06:23,510
Ja niin me vain siirtyä ylhäältä 1.

130
00:06:23,510 --> 00:06:24,890
Että luultavasti järkevää.

131
00:06:24,890 --> 00:06:28,940
>> Nyt jos haluamme laittaa toinen elementti
pinoon, että haluamme ajaa 33,

132
00:06:28,940 --> 00:06:33,190
No nyt me vain vie 33
ja laita se array sijainti numero

133
00:06:33,190 --> 00:06:37,580
1, ja sitten muuttaa kärkeen
pino olla valikoimaan Sijainti numero kaksi.

134
00:06:37,580 --> 00:06:40,650
Joten jos seuraavan kerran haluamme
push elementti pinoon,

135
00:06:40,650 --> 00:06:43,087
se tulee laittaa array sijainti 2.

136
00:06:43,087 --> 00:06:44,420
Ja tehdään se vielä kerran.

137
00:06:44,420 --> 00:06:45,753
Me ajaa 19 pois pinot.

138
00:06:45,753 --> 00:06:48,940
Laitamme 19 array sijainti 2
ja muuttaa kärkeen pinon

139
00:06:48,940 --> 00:06:51,220
olla array sijainti 3
joten jos seuraavan kerran

140
00:06:51,220 --> 00:06:54,780
täytyy tehdä push olemme hyvä mennä.

141
00:06:54,780 --> 00:06:56,980
>> OK, niin se työntää pähkinänkuoressa.

142
00:06:56,980 --> 00:06:57,830
Entä popping?

143
00:06:57,830 --> 00:07:00,240
Joten popping on eräänlainen
vastine työntää.

144
00:07:00,240 --> 00:07:02,720
Se miten me poistaa tietoja pino.

145
00:07:02,720 --> 00:07:04,610
Ja yleensä pop tarpeisiin
tehdä seuraavaa.

146
00:07:04,610 --> 00:07:07,600
Se tarvitsee hyväksyä osoitin
pino, jälleen yleisessä tapauksessa.

147
00:07:07,600 --> 00:07:10,480
Joissakin muissa tapauksessa saatat
ovat ilmoittaneet pino maailmanlaajuisesti,

148
00:07:10,480 --> 00:07:13,910
jolloin sinun ei tarvitse siirtää sitä
koska siihen on jo pääsy siihen

149
00:07:13,910 --> 00:07:15,541
kuten globaali muuttuja.

150
00:07:15,541 --> 00:07:17,040
Mutta sitten mitä muuta meidän täytyy tehdä?

151
00:07:17,040 --> 00:07:21,000
No olimme monesko
pinon push,

152
00:07:21,000 --> 00:07:24,050
joten olemme luultavasti menossa haluavat
dekrementoidaan pinon päälle

153
00:07:24,050 --> 00:07:25,009
pop, eikö?

154
00:07:25,009 --> 00:07:26,800
Ja sitten tietenkin
olemme myös menossa haluavat

155
00:07:26,800 --> 00:07:29,240
palauttaa arvon että poistamme.

156
00:07:29,240 --> 00:07:32,125
Jos lisäämme elementtejä, haluamme
päästä elementit ulos myöhemmin,

157
00:07:32,125 --> 00:07:34,000
me luultavasti todella
haluat tallentaa niitä niin me

158
00:07:34,000 --> 00:07:36,490
älä vain poista ne
pino ja sitten tehdä mitään heidän kanssaan.

159
00:07:36,490 --> 00:07:38,500
Yleensä jos olemme
työntämällä ja popping täällä

160
00:07:38,500 --> 00:07:41,250
haluamme säilyttää tämän
tiedot tarkoituksenmukaisella tavalla

161
00:07:41,250 --> 00:07:43,250
ja niin se ei tee
järkeä vain hävittää sen.

162
00:07:43,250 --> 00:07:46,380
Joten tämä toiminto olisi
luultavasti palata arvo meille.

163
00:07:46,380 --> 00:07:51,040
>> Joten tämä on mitä ilmoitus pop
voisi näyttää siellä ylhäällä vasemmalla.

164
00:07:51,040 --> 00:07:53,870
Tämä toiminto palauttaa
data tyypin arvo.

165
00:07:53,870 --> 00:07:56,320
Jälleen olemme olleet käyttäen
kokonaislukuja kaikkialla.

166
00:07:56,320 --> 00:08:01,916
Ja se hyväksyy osoittimen pinon
sen ainoa argumentti tai ainoa parametri.

167
00:08:01,916 --> 00:08:03,040
Joten mitä on pop aikoo tehdä?

168
00:08:03,040 --> 00:08:07,990
Sanotaan haluamme nyt
pop elementti pois s.

169
00:08:07,990 --> 00:08:14,000
Joten muistakaa Sanoin, että pinot ovat viime
in, first out, LIFO tietorakenteita.

170
00:08:14,000 --> 00:08:17,855
Joka elementti on menossa
poistetaan pinosta?

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

172
00:08:21,780 --> 00:08:24,150
Arvasit 19?

173
00:08:24,150 --> 00:08:25,290
Koska olisit oikeassa.

174
00:08:25,290 --> 00:08:28,836
19 oli viimeinen elementti lisäsimme
pino kun olimme työntää elementtejä,

175
00:08:28,836 --> 00:08:31,210
ja niin se tulee ensimmäinen
elementti, joka saa poistaa.

176
00:08:31,210 --> 00:08:34,780
Aivan kuin sanoimme 28, ja
sitten laittaa 33 sen päälle,

177
00:08:34,780 --> 00:08:36,659
ja laitamme 19 päälle, että.

178
00:08:36,659 --> 00:08:40,650
Ainoa elementti voimme ottaa pois on 19.

179
00:08:40,650 --> 00:08:45,019
>> Nyt kaavion täällä, mitä olen tehnyt
on eräänlainen poistetaan 19 jono.

180
00:08:45,019 --> 00:08:46,810
Se ei ole oikeastaan
mitä aiomme tehdä.

181
00:08:46,810 --> 00:08:48,934
Olemme juuri menossa eräänlainen
ja teeskennellä se ei ole siellä.

182
00:08:48,934 --> 00:08:51,441
Se on edelleen siellä
että muistipaikka,

183
00:08:51,441 --> 00:08:54,190
mutta me vain aio sivuuttaa sitä
muuttamalla alkuun meidän pinon

184
00:08:54,190 --> 00:08:56,080
olemasta 3-2.

185
00:08:56,080 --> 00:08:58,720
Joten jos me nyt työntää
toinen elementti pinoon,

186
00:08:58,720 --> 00:09:00,720
se yli kirjoittaa 19.

187
00:09:00,720 --> 00:09:03,990
>> Mutta älkäämme käydä läpi ongelmia
poistamisen 19 pinosta.

188
00:09:03,990 --> 00:09:05,830
Voimme vain teeskennellä se ei ole siellä.

189
00:09:05,830 --> 00:09:11,107
Varten pinon se on mennyt, jos
muutamme alkuun olevan 2 sijasta 3.

190
00:09:11,107 --> 00:09:12,690
Selvä, joten se oli aika paljon se.

191
00:09:12,690 --> 00:09:15,080
Siinä kaikki meidän täytyy tehdä
pop elementti pois.

192
00:09:15,080 --> 00:09:16,090
Tehdään se uudestaan.

193
00:09:16,090 --> 00:09:18,610
Joten olen korostanut sen punaisella täällä
osoittavat Teemme toisen puhelun.

194
00:09:18,610 --> 00:09:19,720
Aiomme tehdä sama asia.

195
00:09:19,720 --> 00:09:20,803
>> Joten mitä tulee tapahtumaan?

196
00:09:20,803 --> 00:09:23,670
No, me aiomme säilyttää
33 x ja olemme menossa

197
00:09:23,670 --> 00:09:26,217
muuttaa päällimmäinen 1.

198
00:09:26,217 --> 00:09:29,050
Niin että jos me nyt työntää
elementin pinon johon olemme

199
00:09:29,050 --> 00:09:31,610
aikoo tehdä juuri nyt,
mitä tulee tapahtumaan

200
00:09:31,610 --> 00:09:36,367
on aiomme päälleäänittävän
array Sijainti numero 1.

201
00:09:36,367 --> 00:09:38,950
Jotta 33 joka oli tavallaan jäljellä
takana me vain teeskenteli

202
00:09:38,950 --> 00:09:44,390
jota ei enää ole, me vain menossa
jotta hakata sitä ja laittaa 40 siellä sijaan.

203
00:09:44,390 --> 00:09:46,290
Ja sitten tietenkin,
koska teimme push,

204
00:09:46,290 --> 00:09:48,780
aiomme kasvattaa
pinon 1-2

205
00:09:48,780 --> 00:09:50,950
niin että jos me nyt lisätä
toinen elementti se tulee

206
00:09:50,950 --> 00:09:54,700
mennä array Sijainti numero kaksi.

207
00:09:54,700 --> 00:09:57,590
>> Nyt liittyvät luettelot ovat toinen
tapa toteuttaa pinot.

208
00:09:57,590 --> 00:10:01,210
Ja jos tämän määritelmän
screen täällä näyttää tutulta,

209
00:10:01,210 --> 00:10:04,260
se johtuu se näyttää melkein
täsmälleen sama, itse asiassa,

210
00:10:04,260 --> 00:10:07,790
se aika paljon on täsmälleen
sama kuin yksinään linkitetty lista,

211
00:10:07,790 --> 00:10:11,990
Jos muistatte meidän keskustelua
yksittäin sidoksissa luetteloita toinen video.

212
00:10:11,990 --> 00:10:15,510
Ainoa rajoitus tässä
on meille ohjelmoijille,

213
00:10:15,510 --> 00:10:17,900
emme saa
lisätä tai poistaa satunnaisesti

214
00:10:17,900 --> 00:10:20,620
alkaen yksittäin linkitetyn listan
jota voisimme aiemmin tehdä.

215
00:10:20,620 --> 00:10:25,820
Voimme vain nyt lisätä ja poistaa
etu- tai yläosan linkitetyn

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

217
00:10:26,320 --> 00:10:28,028
Se on todella ainoa
ero kuitenkin.

218
00:10:28,028 --> 00:10:29,700
Tämä on muuten yksittäin linkitetyn listan.

219
00:10:29,700 --> 00:10:32,060
Se on vain rajoitus
korvaa itsellemme

220
00:10:32,060 --> 00:10:35,770
kuten ohjelmoijille, että
muuttuu sen pinoon.

221
00:10:35,770 --> 00:10:39,280
>> Sääntö täällä on aina säilyttää
osoitin johtaja linkitetyn listan.

222
00:10:39,280 --> 00:10:41,520
Tämä on tietysti yleisesti
tärkeä sääntö ensin.

223
00:10:41,520 --> 00:10:44,260
Saat yksittäin linkitetty lista muutenkin sinua
tarvitsee vain osoitin päähän

224
00:10:44,260 --> 00:10:46,160
jotta on, että
ketju voitava siirtää

225
00:10:46,160 --> 00:10:48,596
joka toinen elementti
vuonna linkitetty lista.

226
00:10:48,596 --> 00:10:50,470
Mutta se on erityisen
tärkeää pino.

227
00:10:50,470 --> 00:10:52,386
Ja niin yleensä olet
menossa todella haluavat

228
00:10:52,386 --> 00:10:54,090
tämä osoitin on globaali muuttuja.

229
00:10:54,090 --> 00:10:56,574
Se luultavasti
olla jopa helpompaa näin.

230
00:10:56,574 --> 00:10:58,240
Mitkä ovat analogeja push ja pop?

231
00:10:58,240 --> 00:10:58,740
Oikea.

232
00:10:58,740 --> 00:11:01,812
Joten työntää taas on lisännyt
uusi elementti pino.

233
00:11:01,812 --> 00:11:03,770
Vuonna linkitetty lista, joka
tarkoittaa, että menossa on

234
00:11:03,770 --> 00:11:07,770
luoda uusi solmu, että olemme
menossa lisätä osaksi linkitetty lista,

235
00:11:07,770 --> 00:11:10,500
ja noudata varovaisia ​​askelia
että olemme edellä on selostettu

236
00:11:10,500 --> 00:11:16,050
vuonna yksittäin linkitettyjen listojen lisätä sen
ketju rikkomatta ketjua

237
00:11:16,050 --> 00:11:18,900
ja menettämättä tai orpoutumista tahansa
elementtejä linkitetyn listan.

238
00:11:18,900 --> 00:11:21,820
Ja se on periaatteessa mitä että
pikku möykky tekstiä siellä tiivistää.

239
00:11:21,820 --> 00:11:23,740
Ja lähdetään katsomaan
sitä kuin kaavio.

240
00:11:23,740 --> 00:11:24,823
>> Joten tässä on meidän linkitetty lista.

241
00:11:24,823 --> 00:11:26,620
Se samanaikaisesti sisältää neljä osatekijää.

242
00:11:26,620 --> 00:11:30,420
Ja täydellisemmin tässä meidän
pino sisältää neljä elementtejä.

243
00:11:30,420 --> 00:11:36,030
Ja sanotaanko haluamme nyt
työntää uusi kohde päälle tämä pino.

244
00:11:36,030 --> 00:11:39,792
Ja haluamme työntää uusi
Tuote, jonka data-arvo on 12.

245
00:11:39,792 --> 00:11:41,000
No mitä aiomme tehdä?

246
00:11:41,000 --> 00:11:43,420
No ensimmäinen aiomme
malloc tila, dynaamisesti

247
00:11:43,420 --> 00:11:45,411
jakaa tilaa uusi solmu.

248
00:11:45,411 --> 00:11:48,160
Ja tietenkin heti
me soittaa malloc me aina

249
00:11:48,160 --> 00:11:52,989
varmista tarkistaa null,
koska jos meillä null takaisin

250
00:11:52,989 --> 00:11:54,280
siellä oli jonkinlainen ongelma.

251
00:11:54,280 --> 00:11:57,570
Emme halua dereference että null
osoitin tai tulet kärsimään seg vika.

252
00:11:57,570 --> 00:11:58,510
Tuo ei ole hyvä.

253
00:11:58,510 --> 00:11:59,760
Joten olemme malloced solmun.

254
00:11:59,760 --> 00:12:01,260
Oletamme meillä on ollut menestys täällä.

255
00:12:01,260 --> 00:12:06,090
Aiomme laittaa 12 otetaan
datakentässä, että solmun.

256
00:12:06,090 --> 00:12:11,570
Nyt te muistatte joka meidän osoittimia
siirtyy ensi joten emme katkaisemiseksi?

257
00:12:11,570 --> 00:12:15,100
Meillä on pari vaihtoehtoa täällä, mutta
ainoa, joka tulee olemaan turvallinen

258
00:12:15,100 --> 00:12:19,330
on asettaa uutinen ensi osoitin
kohta vanhaan johtaja luettelon

259
00:12:19,330 --> 00:12:21,360
tai mitä pian
vanha pää luettelon.

260
00:12:21,360 --> 00:12:23,610
Ja nyt, että meidän kaikkien
elementit ketjuttaa,

261
00:12:23,610 --> 00:12:27,370
voimme vain siirtyä luettelon kohtaan
samaan paikkaan, että uudet ei.

262
00:12:27,370 --> 00:12:33,550
Ja olemme nyt käytännössä ajanut
uusi elementti päälle edessä pinon.

263
00:12:33,550 --> 00:12:36,420
>> Pop me vain haluamme
poistaa että ensimmäinen elementti.

264
00:12:36,420 --> 00:12:38,150
Ja niin periaatteessa mitä
meidän on tehtävä täällä,

265
00:12:38,150 --> 00:12:40,050
hyvin meidän täytyy löytää toinen elementti.

266
00:12:40,050 --> 00:12:43,540
Lopulta että tulee uusi
pää kun olemme poistaa ensimmäinen.

267
00:12:43,540 --> 00:12:47,300
Joten meidän täytyy vain aloittaa
alusta, siirtyä yksi eteenpäin.

268
00:12:47,300 --> 00:12:50,340
Kun meillä otteen yksi
eteenpäin siitä, missä olemme tällä hetkellä

269
00:12:50,340 --> 00:12:53,850
ovat voimme poistaa ensimmäinen turvallisesti
ja sitten voimme vain siirtää pään

270
00:12:53,850 --> 00:12:57,150
osoittamaan, mikä oli
Toinen termi ja sitten nyt

271
00:12:57,150 --> 00:12:59,170
on ensimmäinen sen jälkeen
solmu on poistettu.

272
00:12:59,170 --> 00:13:01,160
>> Joten jälleen, kun tarkastellaan
sitä kun kaavio me

273
00:13:01,160 --> 00:13:05,022
haluavat nyt pop
elementti pois tähän pinoon.

274
00:13:05,022 --> 00:13:05,730
Joten mitä me teemme?

275
00:13:05,730 --> 00:13:08,188
No me ensin luomassa
uusi osoitin, joka menee

276
00:13:08,188 --> 00:13:10,940
osoittamaan samaan paikkaan kuin pää.

277
00:13:10,940 --> 00:13:13,790
Aiomme siirtää sen yhden paikan
eteenpäin sanomalla Trav tasavertaisten

278
00:13:13,790 --> 00:13:17,510
trav ensi esimerkiksi, joka
edistäisi Trav osoitin yksi

279
00:13:17,510 --> 00:13:19,324
asentoon eteenpäin.

280
00:13:19,324 --> 00:13:21,240
Nyt kun meillä
pitää ensimmäisen elementin

281
00:13:21,240 --> 00:13:24,573
kautta osoitin kutsutaan luettelo, ja
Toinen elementti läpi osoitin nimeltään

282
00:13:24,573 --> 00:13:28,692
trav, voimme turvallisesti poistaa että
ensimmäinen elementti pinosta

283
00:13:28,692 --> 00:13:30,650
menettämättä loput
Ketjun koska me

284
00:13:30,650 --> 00:13:32,358
on tapa viitata
toiseen osaan

285
00:13:32,358 --> 00:13:34,780
välittämään tavalla
osoitin kutsutaan trav.

286
00:13:34,780 --> 00:13:37,100
>> Joten nyt voimme vapauttaa että solmu.

287
00:13:37,100 --> 00:13:38,404
Voimme ilmainen luettelo.

288
00:13:38,404 --> 00:13:41,320
Ja sitten kaikki meidän täytyy tehdä nyt on
Siirrä lista viittaavat samaan paikkaan

289
00:13:41,320 --> 00:13:44,482
että trav tekee, ja olemme tavallaan takaisin
jossa aloitimme ennen kuin työnsi 12

290
00:13:44,482 --> 00:13:45,690
on ensimmäinen paikka, oikea.

291
00:13:45,690 --> 00:13:46,940
Juuri tässä me olimme.

292
00:13:46,940 --> 00:13:48,840
Meillä oli tämän neljän elementin pino.

293
00:13:48,840 --> 00:13:49,690
Lisäsimme viidesosa.

294
00:13:49,690 --> 00:13:51,910
Työnsimme viidesosa
elementin, ja sitten me

295
00:13:51,910 --> 00:13:55,980
piipahti että viimeksi
lisätty elementti perääntymään.

296
00:13:55,980 --> 00:13:58,816
>> Se on oikeastaan ​​aika paljon
kaikki on pinot.

297
00:13:58,816 --> 00:14:00,190
Voit toteuttaa ne taulukot.

298
00:14:00,190 --> 00:14:01,815
Voit toteuttaa ne liittyvät luettelot.

299
00:14:01,815 --> 00:14:04,810
On, tietenkin, muiden
tapoja toteuttaa niitä.

300
00:14:04,810 --> 00:14:09,060
Periaatteessa syystä käyttäisi
pinot on ylläpitää dataa siten,

301
00:14:09,060 --> 00:14:12,090
että viimeksi lisätyt
elementti on ensimmäinen asia olemme

302
00:14:12,090 --> 00:14:14,980
menossa halua saada takaisin.

303
00:14:14,980 --> 00:14:17,900
Olen Doug Lloyd, tämä on CS50.

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