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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Molt bé,
així que en aquest punt estàs

3
00:00:05,990 --> 00:00:09,020
probablement bastant familiaritzat
amb matrius i llistes enllaçades

4
00:00:09,020 --> 00:00:10,950
que és el de dos primària
estructures de dades que hem

5
00:00:10,950 --> 00:00:16,810
parlat de mantenir conjunts de
dades de tipus de dades similars organitzada.

6
00:00:16,810 --> 00:00:19,080
>> Ara anem a parlar
voltant d'un parell de variacions

7
00:00:19,080 --> 00:00:20,330
en matrius i llistes enllaçades.

8
00:00:20,330 --> 00:00:22,362
En aquest vídeo anem
per parlar de les piles.

9
00:00:22,362 --> 00:00:25,320
En concret parlarem
sobre una estructura de dades anomenada una pila.

10
00:00:25,320 --> 00:00:28,510
Recordeu que en els debats anteriors
sobre els punters i memòria,

11
00:00:28,510 --> 00:00:32,060
que la pila és també el
nomenar per a un segment de la memòria

12
00:00:32,060 --> 00:00:34,980
on declara estàticament
memòria memory-- que

13
00:00:34,980 --> 00:00:38,730
nom, variables que vostè nom, et
marcs cetera i funció que també

14
00:00:38,730 --> 00:00:41,000
existeixen marcs de pila de trucades.

15
00:00:41,000 --> 00:00:45,421
Així que aquesta és una estructura de dades de la pila
no és un segment de pila de la memòria.

16
00:00:45,421 --> 00:00:45,920
D'ACORD.

17
00:00:45,920 --> 00:00:46,890
>> Però, ¿què és una pila?

18
00:00:46,890 --> 00:00:49,220
Així que és pràcticament només una
tipus especial d'estructura

19
00:00:49,220 --> 00:00:51,190
que manté les dades d'una manera organitzada.

20
00:00:51,190 --> 00:00:53,760
I hi ha dues molt
formes comunes d'implementar

21
00:00:53,760 --> 00:00:57,380
piles utilitzant dues estructures de dades
que ja estem familiaritzats,

22
00:00:57,380 --> 00:01:00,340
matrius i llistes enllaçades.

23
00:01:00,340 --> 00:01:04,430
Què fa un especial de pila és el
manera en què posem la informació

24
00:01:04,430 --> 00:01:08,200
a la pila, i la forma en què
eliminar la informació de la pila.

25
00:01:08,200 --> 00:01:11,600
En particular amb les piles
la regla és només el més

26
00:01:11,600 --> 00:01:15,830
recentment element afegit es pot treure.

27
00:01:15,830 --> 00:01:17,660
>> Així que pensar-hi com si fos una pila.

28
00:01:17,660 --> 00:01:21,170
Estem acumulant informació
a la part superior de la mateixa,

29
00:01:21,170 --> 00:01:24,271
i només la cosa a la part superior
de la pila es pot treure.

30
00:01:24,271 --> 00:01:27,020
No podem treure la cosa sota
perquè tota la resta ho faria

31
00:01:27,020 --> 00:01:28,020
col·lapsar i caure.

32
00:01:28,020 --> 00:01:32,580
Així que realment estem construint una pila que
llavors hem d'eliminar peça per peça.

33
00:01:32,580 --> 00:01:36,590
A causa d'això ens referim comunament
a una pila com una estructura LIFO,

34
00:01:36,590 --> 00:01:38,940
últim en entrar, primer en sortir.

35
00:01:38,940 --> 00:01:42,290
LIFO, últim en entrar, primer a sortir.

36
00:01:42,290 --> 00:01:45,635
>> Així que a causa d'aquesta restricció en
com la informació pot ser afegit a

37
00:01:45,635 --> 00:01:49,080
i retirat d'una pila, no hi ha realment
només dues coses que poden fer amb una pila.

38
00:01:49,080 --> 00:01:52,010
Podem empènyer, que és el
terme que fem servir per afegir

39
00:01:52,010 --> 00:01:55,130
un nou element a la part superior de la
pila, o si la pila no existeix

40
00:01:55,130 --> 00:01:58,550
i estem creant des de zero,
la creació de la pila en el primer lloc

41
00:01:58,550 --> 00:02:00,110
seria empènyer.

42
00:02:00,110 --> 00:02:04,990
I a continuació, el pop, que és el tipus de CS
terme que fem servir per treure el més recent

43
00:02:04,990 --> 00:02:08,330
element afegit des de la part superior de la pila.

44
00:02:08,330 --> 00:02:11,130
>> Així que anem a mirar a tots dos
implementacions, basat tant array

45
00:02:11,130 --> 00:02:13,120
i llista enllaçada amb base.

46
00:02:13,120 --> 00:02:14,870
I anem a
començar amb matriu basada.

47
00:02:14,870 --> 00:02:19,990
Així que aquí està la idea bàsica del que
l'estructura de dades basada en pila de conjunts

48
00:02:19,990 --> 00:02:21,140
es veuria així.

49
00:02:21,140 --> 00:02:23,740
Tenim una definició mecanografiada aquí.

50
00:02:23,740 --> 00:02:27,790
A l'interior de la qual tenim dos membres
o camps de l'estructura.

51
00:02:27,790 --> 00:02:29,880
Tenim una matriu.

52
00:02:29,880 --> 00:02:32,400
I una altra vegada estic fent servir el
valor de tipus de dades arbitraris.

53
00:02:32,400 --> 00:02:35,180
>> Així que aquest podria ser qualsevol tipus de dades,
int carbó o alguna altra dada

54
00:02:35,180 --> 00:02:37,080
escriu que ha creat anteriorment.

55
00:02:37,080 --> 00:02:39,861
Així que tenim una gran varietat de capacitat de mida.

56
00:02:39,861 --> 00:02:44,010
Capacitat de ser una lliura defineix constant,
potser en un altre lloc al nostre arxiu.

57
00:02:44,010 --> 00:02:47,550
Així que ja compta amb aquest particular
aplicació estem delimitador

58
00:02:47,550 --> 00:02:49,800
nosaltres mateixos com era normalment
en el cas d'arrays,

59
00:02:49,800 --> 00:02:53,170
que no podem canviar la mida de forma dinàmica,
on hi ha un cert nombre

60
00:02:53,170 --> 00:02:55,450
d'elements màxima que
podem posar a la nostra pila.

61
00:02:55,450 --> 00:02:57,930
En aquest cas es tracta d'elements de capacitat.

62
00:02:57,930 --> 00:03:00,310
>> També mantenim un registre de
la part superior de la pila.

63
00:03:00,310 --> 00:03:04,350
Quin element és el més
en data recent a la pila?

64
00:03:04,350 --> 00:03:07,470
I així fem un seguiment que
en una variable anomenada superior.

65
00:03:07,470 --> 00:03:11,692
I tot això s'embolica junts
en un nou tipus de dades anomenat una pila.

66
00:03:11,692 --> 00:03:13,400
I una vegada que vam ser creats
aquest nou tipus de dades

67
00:03:13,400 --> 00:03:15,410
podem tractar-ho com
qualsevol altre tipus de dades.

68
00:03:15,410 --> 00:03:20,970
Podem declarar pila s, igual que
podríem fer int x, o de carbó i.

69
00:03:20,970 --> 00:03:22,990
I quan diem apilem
s, així el que succeeix

70
00:03:22,990 --> 00:03:26,420
està obtenim un conjunt de
de memòria reservat per a nosaltres.

71
00:03:26,420 --> 00:03:28,770
>> En aquest cas, la capacitat
Pel que sembla, he decidit

72
00:03:28,770 --> 00:03:33,470
és 10 perquè tinc un
única variable de tipus pila

73
00:03:33,470 --> 00:03:35,320
que conté dos camps recorden.

74
00:03:35,320 --> 00:03:38,330
Una matriu, en aquest cas va
ser una matriu d'enters

75
00:03:38,330 --> 00:03:40,440
com és el cas en la majoria dels meus exemples.

76
00:03:40,440 --> 00:03:43,996
I una altra variable sencera
capaç d'emmagatzemar la part superior,

77
00:03:43,996 --> 00:03:45,870
més recentment afegit
element a la pila.

78
00:03:45,870 --> 00:03:50,290
Així que una sola pila del que
només s'assembla a aquesta definit.

79
00:03:50,290 --> 00:03:53,190
És una caixa que conté
una sèrie de 10 ho

80
00:03:53,190 --> 00:03:57,280
seran nombres enters en aquest cas, i
una altra variable sencera allà en verd

81
00:03:57,280 --> 00:04:00,010
per indicar la part superior de la pila.

82
00:04:00,010 --> 00:04:02,600
>> Per establir la part superior de la
pila només diem s.top.

83
00:04:02,600 --> 00:04:04,890
Aquesta és la forma en què accedim a una
camp d'una estructura de retir.

84
00:04:04,890 --> 00:04:10,460
s.top és igual a 0 eficaçment
Fa això a la nostra pila.

85
00:04:10,460 --> 00:04:12,960
Així que de nou tenim dues operacions
que podem dur a terme ara.

86
00:04:12,960 --> 00:04:14,270
Podem empènyer i podem pop.

87
00:04:14,270 --> 00:04:15,635
Anem a començar amb empenta.

88
00:04:15,635 --> 00:04:18,260
Un cop més, empenyent és l'addició d'un nou
element a la part superior de la pila.

89
00:04:18,260 --> 00:04:21,460
>> Llavors, què fem el que necessitem fer en
aquesta matriu d'implementació basada?

90
00:04:21,460 --> 00:04:23,210
Bé en general
la funció d'empenta es va

91
00:04:23,210 --> 00:04:26,160
a haver de acceptar una
punter a la pila.

92
00:04:26,160 --> 00:04:28,610
Ara pren-te un segon i pensar-hi.

93
00:04:28,610 --> 00:04:32,840
Per què voldríem acceptar
un punter a la pila?

94
00:04:32,840 --> 00:04:36,830
Recordeu que en els vídeos anteriors sobre
abast i punters variables,

95
00:04:36,830 --> 00:04:42,350
¿Què passaria si ens enviem
pila, s en lloc de com un paràmetre?

96
00:04:42,350 --> 00:04:45,770
El que en realitat es va passar aquí?

97
00:04:45,770 --> 00:04:49,430
Recordeu que estem creant una còpia
quan es passa a una funció

98
00:04:49,430 --> 00:04:51,160
llevat que utilitzem punters.

99
00:04:51,160 --> 00:04:55,380
I així aquesta funció empènyer necessitats
per acceptar un punter a la pila

100
00:04:55,380 --> 00:04:59,160
pel que en realitat estem canviant
la pila tenim la intenció de canviar.

101
00:04:59,160 --> 00:05:03,060
>> L'altra cosa empenta probablement vol
acceptar és un element de dades de valor de tipus.

102
00:05:03,060 --> 00:05:06,970
En aquest cas, de nou, un nombre enter que
anem a afegir a la part superior de la pila.

103
00:05:06,970 --> 00:05:08,680
Així que tenim els nostres dos paràmetres.

104
00:05:08,680 --> 00:05:11,310
Què farem
ara fer dins d'empenta?

105
00:05:11,310 --> 00:05:14,860
Bé, simplement, només anem a afegir
aquest element a la part superior de la pila

106
00:05:14,860 --> 00:05:22,860
i després canviar a la part superior de
la pila és, que s dot valor superior.

107
00:05:22,860 --> 00:05:25,639
Així que això és el que una funció
declaració d'empenta

108
00:05:25,639 --> 00:05:27,680
podria semblar en un
basada en arranjaments d'implementació.

109
00:05:27,680 --> 00:05:30,967
>> De nou, això no és una regla dura i ràpida
que podria canviar això i tenir

110
00:05:30,967 --> 00:05:32,050
que varien en diferents maneres.

111
00:05:32,050 --> 00:05:33,840
Potser s es declara globalment.

112
00:05:33,840 --> 00:05:36,180
I pel que ni tan sols cal
passar és com un paràmetre.

113
00:05:36,180 --> 00:05:39,125
Això és de nou només una
cas general per empènyer.

114
00:05:39,125 --> 00:05:41,000
I hi ha diferents
maneres de posar-ho en pràctica.

115
00:05:41,000 --> 00:05:42,810
Però en aquest cas la nostra
empenta va a prendre

116
00:05:42,810 --> 00:05:48,540
dos arguments, un punter a una pila i
un element de dades de valor de tipus, nombre enter

117
00:05:48,540 --> 00:05:49,840
en aquest cas.

118
00:05:49,840 --> 00:05:52,100
>> Així que vam declarar s, ens
va dir s.top és igual a 0.

119
00:05:52,100 --> 00:05:55,969
Ara anem a empènyer el
el número 28 a la pila.

120
00:05:55,969 --> 00:05:57,010
Bé, què vol dir això?

121
00:05:57,010 --> 00:05:59,600
Bé actualment la
part superior de la pila és 0.

122
00:05:59,600 --> 00:06:01,350
I així, el que és, bàsicament,
passarà és

123
00:06:01,350 --> 00:06:05,820
anem a enganxar el nombre
28 en la ubicació array 0.

124
00:06:05,820 --> 00:06:09,540
Bastant senzill, correcte, que
era la part superior i ara som bons per anar.

125
00:06:09,540 --> 00:06:12,910
I llavors hem de canviar el que
la part superior de la pila ha de ser.

126
00:06:12,910 --> 00:06:15,130
Així que la propera vegada
empenyem un element,

127
00:06:15,130 --> 00:06:18,017
anem a guardar-lo en
ubicació array, probablement no 0.

128
00:06:18,017 --> 00:06:20,100
No volem sobreescriure
el que acabem de posar allà.

129
00:06:20,100 --> 00:06:23,510
I així només haurem de moure la part superior a 1.

130
00:06:23,510 --> 00:06:24,890
Això probablement té sentit.

131
00:06:24,890 --> 00:06:28,940
>> Ara bé, si volem posar un altre element
a la pila, diem que volem empènyer 33,

132
00:06:28,940 --> 00:06:33,190
Bé, ara només anem a prendre 33
i el va posar al nombre d'ubicació de matriu

133
00:06:33,190 --> 00:06:37,580
1, i després canviar la part superior de la nostra
apilar ser ubicació matriu número dos.

134
00:06:37,580 --> 00:06:40,650
Així que si la propera vegada que volem
empènyer un element a la pila,

135
00:06:40,650 --> 00:06:43,087
que va ser posat en un lloc matriu 2.

136
00:06:43,087 --> 00:06:44,420
I farem això un cop més.

137
00:06:44,420 --> 00:06:45,753
Ens empenyem 19 fora de les piles.

138
00:06:45,753 --> 00:06:48,940
Anem a posar 19 a la localització matriu 2
i canviar la part superior de la nostra pila

139
00:06:48,940 --> 00:06:51,220
ser ubicació matriu 3
per la qual cosa si la propera vegada que anem de

140
00:06:51,220 --> 00:06:54,780
que hagi de fer un esforç que estem bé per anar.

141
00:06:54,780 --> 00:06:56,980
>> OK, així que això és empènyer en poques paraules.

142
00:06:56,980 --> 00:06:57,830
Què hi ha d'esclatar?

143
00:06:57,830 --> 00:07:00,240
Així que fa esclatar és el tipus de
contrapartida a empènyer.

144
00:07:00,240 --> 00:07:02,720
És la forma en què ens vam treure les dades de la pila.

145
00:07:02,720 --> 00:07:04,610
I en pop necessitats generals
a fer el següent.

146
00:07:04,610 --> 00:07:07,600
Es necessita acceptar un punter a la
apilar, de nou en el cas general.

147
00:07:07,600 --> 00:07:10,480
En un altre cas, vostè pot ser
han declarat la pila a nivell mundial,

148
00:07:10,480 --> 00:07:13,910
en aquest cas no és necessari per passar-ho
a perquè ja té accés a la mateixa

149
00:07:13,910 --> 00:07:15,541
com una variable global.

150
00:07:15,541 --> 00:07:17,040
Però llavors què més hem de fer?

151
00:07:17,040 --> 00:07:21,000
Bé ens incrementant
la part superior de la pila en empenta,

152
00:07:21,000 --> 00:07:24,050
així que estem probablement voldrà
per disminuir la part superior de la pila

153
00:07:24,050 --> 00:07:25,009
en el pop, no?

154
00:07:25,009 --> 00:07:26,800
I després, per descomptat,
també anem a voler

155
00:07:26,800 --> 00:07:29,240
per tornar el valor que eliminem.

156
00:07:29,240 --> 00:07:32,125
Si estem afegint elements, volem
per obtenir elements a terme més endavant,

157
00:07:32,125 --> 00:07:34,000
és probable que en realitat
voler guardar així que

158
00:07:34,000 --> 00:07:36,490
no simplement eliminar-los de la
apilar i després no fer res amb ells.

159
00:07:36,490 --> 00:07:38,500
Generalment si som
empenyent i fent esclatar aquí

160
00:07:38,500 --> 00:07:41,250
volem emmagatzemar aquesta
la informació d'una manera significativa

161
00:07:41,250 --> 00:07:43,250
i pel que no fa
sentit simplement descartar-ho.

162
00:07:43,250 --> 00:07:46,380
Així que aquesta funció ha de
probablement retornar un valor per a nosaltres.

163
00:07:46,380 --> 00:07:51,040
>> Així que això és el que una declaració de pop
podria semblar que hi ha a la part superior esquerra.

164
00:07:51,040 --> 00:07:53,870
Aquesta funció retorna
les dades de valor de tipus.

165
00:07:53,870 --> 00:07:56,320
Una vegada que hem estat utilitzant
sencers llarg.

166
00:07:56,320 --> 00:08:01,916
I accepta un punter a una pila com
el seu únic argument o paràmetre únic.

167
00:08:01,916 --> 00:08:03,040
Llavors, què és el pop va a fer?

168
00:08:03,040 --> 00:08:07,990
Diguem que volem ara
pop un element fora de s.

169
00:08:07,990 --> 00:08:14,000
Llavors recordo que vaig dir que les piles estan última
In, First Out, estructures de dades LIFO.

170
00:08:14,000 --> 00:08:17,855
Quin element es va a
ser retirat de la pila?

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

172
00:08:21,780 --> 00:08:24,150
Sabia vostè endevina 19?

173
00:08:24,150 --> 00:08:25,290
Perquè estaríem en la veritat.

174
00:08:25,290 --> 00:08:28,836
19 va ser l'últim element que afegim a la
apilar quan estàvem empenyent elements en,

175
00:08:28,836 --> 00:08:31,210
i pel que va a la primera
element que aconsegueix tret.

176
00:08:31,210 --> 00:08:34,780
És com si diguéssim 28, i
a continuació, posem 33 a la part superior de la mateixa,

177
00:08:34,780 --> 00:08:36,659
i vam posar 19 per sobre d'això.

178
00:08:36,659 --> 00:08:40,650
L'únic element que podem treure és 19.

179
00:08:40,650 --> 00:08:45,019
>> Ara al diagrama aquí el que he fet
és una espècie d'esborrat 19 de la matriu.

180
00:08:45,019 --> 00:08:46,810
Això no és realitat
el que farem.

181
00:08:46,810 --> 00:08:48,934
Només anem a classe
de pretendre que no hi és.

182
00:08:48,934 --> 00:08:51,441
És encara allà a
aquesta ubicació de memòria,

183
00:08:51,441 --> 00:08:54,190
però només anem a ignorar
canviant la part superior de la nostra pila

184
00:08:54,190 --> 00:08:56,080
de ser 3 a 2.

185
00:08:56,080 --> 00:08:58,720
Així que si haguéssim de ara empènyer
un altre element a la pila,

186
00:08:58,720 --> 00:09:00,720
seria més d'escriure 19.

187
00:09:00,720 --> 00:09:03,990
>> Però no cal passar per la molèstia
19 de eliminar-lo de la pila.

188
00:09:03,990 --> 00:09:05,830
Només podem pretendre que no hi és.

189
00:09:05,830 --> 00:09:11,107
A l'efecte de la pila que s'ha anat si
canviem la part superior per ser 2 en lloc de 3.

190
00:09:11,107 --> 00:09:12,690
Molt bé, així que això va ser més o menys la mateixa.

191
00:09:12,690 --> 00:09:15,080
Això és tot el que necessitem fer
perquè aparegui un element fora.

192
00:09:15,080 --> 00:09:16,090
Anem a fer-ho de nou.

193
00:09:16,090 --> 00:09:18,610
Així que he destacat en vermell per
indiquem que estem fent una altra trucada.

194
00:09:18,610 --> 00:09:19,720
Anem a fer el mateix.

195
00:09:19,720 --> 00:09:20,803
>> Llavors, què passarà?

196
00:09:20,803 --> 00:09:23,670
Bé, anem a emmagatzemar
33 en x i anem

197
00:09:23,670 --> 00:09:26,217
per canviar la part superior de la pila a 1.

198
00:09:26,217 --> 00:09:29,050
Així que si fóssim ara per empènyer un
element a la pila que estem

199
00:09:29,050 --> 00:09:31,610
farem en aquest moment,
el que va a succeir

200
00:09:31,610 --> 00:09:36,367
Som nosaltres anem sobreescriptura
ubicació matriu número 1.

201
00:09:36,367 --> 00:09:38,950
Així que el 33 que va ser una espècie d'esquerra
darrere que acabem fingim

202
00:09:38,950 --> 00:09:44,390
¿No hi ha més, només estem anant
per donar-li una pallissa i posar 40 al seu lloc.

203
00:09:44,390 --> 00:09:46,290
I després, per descomptat,
des que vam fer una empenta,

204
00:09:46,290 --> 00:09:48,780
incrementarem el
superior de la pila 1-2

205
00:09:48,780 --> 00:09:50,950
de manera que si ara afegim
un altre element que va a

206
00:09:50,950 --> 00:09:54,700
anar a la ubicació matriu número dos.

207
00:09:54,700 --> 00:09:57,590
>> Ara llistes enllaçades són una altra
manera d'implementar les piles.

208
00:09:57,590 --> 00:10:01,210
I si aquesta definició al
pantalla d'aquí sembla familiar a vostè,

209
00:10:01,210 --> 00:10:04,260
és perquè es veu gairebé
exactament de la mateixa, de fet,

210
00:10:04,260 --> 00:10:07,790
que pràcticament és exactament el
mateix que una llista enllaçada,

211
00:10:07,790 --> 00:10:11,990
si vostè recorda de la nostra discussió de
simplement enllaçada llistes en un altre vídeo.

212
00:10:11,990 --> 00:10:15,510
L'única restricció aquí
és per a nosaltres com a programadors,

213
00:10:15,510 --> 00:10:17,900
que no se'ns permet
inserir o eliminar atzar

214
00:10:17,900 --> 00:10:20,620
de la llista simplement enllaçada
que podríem fer amb anterioritat.

215
00:10:20,620 --> 00:10:25,820
Podem només ara inserir i eliminar de
el front o la part superior de l'vinculats

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

217
00:10:26,320 --> 00:10:28,028
Això és realment l'única
diferència però.

218
00:10:28,028 --> 00:10:29,700
Això és el contrari d'una llista enllaçada.

219
00:10:29,700 --> 00:10:32,060
No és més que la restricció
reemplaçant en nosaltres mateixos

220
00:10:32,060 --> 00:10:35,770
com programadors que
canvia en una pila.

221
00:10:35,770 --> 00:10:39,280
>> La regla aquí és mantenir sempre una
punter al capdavant d'una llista enllaçada.

222
00:10:39,280 --> 00:10:41,520
Això és per suposat un general
regla important primer.

223
00:10:41,520 --> 00:10:44,260
Per separat llista enllaçada de totes maneres
Només cal un punter al capdavant

224
00:10:44,260 --> 00:10:46,160
amb la finalitat de tenir aquesta
cadena de poder referir-

225
00:10:46,160 --> 00:10:48,596
per a tots els altres elements
en la llista enllaçada.

226
00:10:48,596 --> 00:10:50,470
Però és sobretot
important amb una pila.

227
00:10:50,470 --> 00:10:52,386
I així, en general, vostè és
va a realment vol

228
00:10:52,386 --> 00:10:54,090
aquest punter a una variable global.

229
00:10:54,090 --> 00:10:56,574
Probablement va
serà encara més fàcil d'aquesta manera.

230
00:10:56,574 --> 00:10:58,240
Quins són els anàlegs d'empenta i el pop?

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

232
00:10:58,740 --> 00:11:01,812
Així empenyent de nou és l'addició de
un nou element a la pila.

233
00:11:01,812 --> 00:11:03,770
En una llista enllaçada que
vol dir que tindrem

234
00:11:03,770 --> 00:11:07,770
per crear un nou node que estem
va afegir a la llista enllaçada,

235
00:11:07,770 --> 00:11:10,500
i després seguiu els passos curosos
que hem esbossat anteriorment

236
00:11:10,500 --> 00:11:16,050
en les llistes lligades senzilles per afegir-lo a
la cadena sense trencar la cadena

237
00:11:16,050 --> 00:11:18,900
i perdre o orfes qualsevol
elements de la llista enllaçada.

238
00:11:18,900 --> 00:11:21,820
I això és bàsicament el que
petita bombolla de text allà resumeix.

239
00:11:21,820 --> 00:11:23,740
I anem a fer una ullada
en ell com un diagrama.

240
00:11:23,740 --> 00:11:24,823
>> Així que aquí està la nostra llista enllaçada.

241
00:11:24,823 --> 00:11:26,620
És al mateix temps conté quatre elements.

242
00:11:26,620 --> 00:11:30,420
I més perfectament aquí està la nostra
apilar conté quatre elements.

243
00:11:30,420 --> 00:11:36,030
I diguem que ara volem
impulsar un nou element en aquesta pila.

244
00:11:36,030 --> 00:11:39,792
I volem impulsar una nova
element el valor és 12.

245
00:11:39,792 --> 00:11:41,000
Bé, què farem?

246
00:11:41,000 --> 00:11:43,420
Bé primer que anem a
espai malloc, dinàmicament

247
00:11:43,420 --> 00:11:45,411
assignar espai per a un nou node.

248
00:11:45,411 --> 00:11:48,160
I, per descomptat, immediatament després
fem una crida a malloc sempre

249
00:11:48,160 --> 00:11:52,989
vos de comprovar nul·la,
perquè si arribem nul·la volta

250
00:11:52,989 --> 00:11:54,280
hi havia algun tipus de problema.

251
00:11:54,280 --> 00:11:57,570
No volem eliminar la referència que nul·la
punter o que patiran una fallada seg.

252
00:11:57,570 --> 00:11:58,510
Això no és bo.

253
00:11:58,510 --> 00:11:59,760
Per a això hem malloced del node.

254
00:11:59,760 --> 00:12:01,260
Anem a suposar que hem tingut èxit aquí.

255
00:12:01,260 --> 00:12:06,090
Anem a posar 12 a
el camp de dades de dit node.

256
00:12:06,090 --> 00:12:11,570
Ara Què recordes quin dels nostres punters
Mou següent, així que no trenquem la cadena?

257
00:12:11,570 --> 00:12:15,100
Tenim un parell d'opcions aquí, però
l'únic que va a estar fora de perill

258
00:12:15,100 --> 00:12:19,330
és establir notícies proper punter a
punt a la vella cap de llista

259
00:12:19,330 --> 00:12:21,360
o el que aviat serà el
antic cap de la llista.

260
00:12:21,360 --> 00:12:23,610
I ara que tot el nostre
elements estan encadenats junts,

261
00:12:23,610 --> 00:12:27,370
només podem moure la llista d'assenyalar
al mateix lloc que el nou fa.

262
00:12:27,370 --> 00:12:33,550
I ara hem portat efectivament una
nou element en la part frontal de la pila.

263
00:12:33,550 --> 00:12:36,420
>> Per aparèixer només volem
esborrar aquest primer element.

264
00:12:36,420 --> 00:12:38,150
I així que bàsicament el que
hem de fer aquí,

265
00:12:38,150 --> 00:12:40,050
així que hem de trobar el segon element.

266
00:12:40,050 --> 00:12:43,540
Amb el temps que es convertirà en el nou
cap després esborrem la primera.

267
00:12:43,540 --> 00:12:47,300
Així que només hem de començar des
Al principi, moure un avanç.

268
00:12:47,300 --> 00:12:50,340
Una vegada que tenim un celler en un
endavant d'on estem actualment

269
00:12:50,340 --> 00:12:53,850
som podem eliminar la primera d'elles amb seguretat
i després ens podem moure el cap

270
00:12:53,850 --> 00:12:57,150
per apuntar-se al que va ser el
segon mandat i llavors ara

271
00:12:57,150 --> 00:12:59,170
és el primer després d'això
node ha estat eliminat.

272
00:12:59,170 --> 00:13:01,160
>> Així que de nou, fent una ullada
en ell com un diagrama que

273
00:13:01,160 --> 00:13:05,022
volen ara un element
element fora d'aquesta pila.

274
00:13:05,022 --> 00:13:05,730
Llavors, què fem?

275
00:13:05,730 --> 00:13:08,188
Bé estem primer crearà
un nou punter que està passant

276
00:13:08,188 --> 00:13:10,940
per assenyalar el mateix lloc que el cap.

277
00:13:10,940 --> 00:13:13,790
Anem a moure-una posició
cap endavant dient iguals trav

278
00:13:13,790 --> 00:13:17,510
trav proper per exemple, que
avançaria el punter trav un sol

279
00:13:17,510 --> 00:13:19,324
posició avançada.

280
00:13:19,324 --> 00:13:21,240
Ara que tenim un
mantenir-se en el primer element

281
00:13:21,240 --> 00:13:24,573
a través de la llista de punters cridat, i la
segon element a través d'un punter anomenat

282
00:13:24,573 --> 00:13:28,692
trav, podem eliminar amb seguretat que
primer element de la pila

283
00:13:28,692 --> 00:13:30,650
sense perdre la resta
de la cadena perquè

284
00:13:30,650 --> 00:13:32,358
tenir una manera de referir
al segon element

285
00:13:32,358 --> 00:13:34,780
reenviar a través de la
punter anomenat trav.

286
00:13:34,780 --> 00:13:37,100
>> Així que ara podem alliberar aquest node.

287
00:13:37,100 --> 00:13:38,404
Podem alliberar llista.

288
00:13:38,404 --> 00:13:41,320
I llavors tot el que necessitem fer ara és
moure la llista a punt al mateix lloc

289
00:13:41,320 --> 00:13:44,482
que trav fa, i estem espècie de tornada
on vam començar abans empenyem 12

290
00:13:44,482 --> 00:13:45,690
en en el primer lloc, a la dreta.

291
00:13:45,690 --> 00:13:46,940
Això és exactament on érem.

292
00:13:46,940 --> 00:13:48,840
Hem tingut aquest quatre elements de la pila.

293
00:13:48,840 --> 00:13:49,690
Hem afegit un cinquè.

294
00:13:49,690 --> 00:13:51,910
Empenyem un cinquè
element, i després ens

295
00:13:51,910 --> 00:13:55,980
aparegut recentment que la majoria
element afegit de marxa enrere.

296
00:13:55,980 --> 00:13:58,816
>> Això és realment més o menys
tot el que hi ha a piles.

297
00:13:58,816 --> 00:14:00,190
Es pot implementar com matrius.

298
00:14:00,190 --> 00:14:01,815
Es pot implementar com llistes enllaçades.

299
00:14:01,815 --> 00:14:04,810
Hi ha, per descomptat, una altra
formes de posar-les en pràctica també.

300
00:14:04,810 --> 00:14:09,060
Bàsicament, la raó per la qual usaríem
piles és mantenir les dades de tal manera

301
00:14:09,060 --> 00:14:12,090
que el més recentment afegit
element és el primer que estem

302
00:14:12,090 --> 00:14:14,980
voldrà tornar.

303
00:14:14,980 --> 00:14:17,900
Sóc Doug Lloyd, això és CS50.

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