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

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: Todo ben,
por iso, este punto está

3
00:00:05,990 --> 00:00:09,020
probablemente bastante familiar
con matrices e listas ligadas

4
00:00:09,020 --> 00:00:10,950
que é a dous primario
estruturas de datos que nós

5
00:00:10,950 --> 00:00:16,810
falou por manter conxuntos de
datos de tipos de datos similares organizado.

6
00:00:16,810 --> 00:00:19,080
>> Agora imos falar
sobre unha parella de variacións

7
00:00:19,080 --> 00:00:20,330
en matrices e listas ligadas.

8
00:00:20,330 --> 00:00:22,362
Neste vídeo imos
para falar pilas.

9
00:00:22,362 --> 00:00:25,320
Especificamente imos falar
sobre unha estrutura de datos denominada pila.

10
00:00:25,320 --> 00:00:28,510
Teña en conta que de discusións previas
sobre punteiros e memoria,

11
00:00:28,510 --> 00:00:32,060
que a pila tamén o é
nomear a un segmento de memoria

12
00:00:32,060 --> 00:00:34,980
onde estaticamente declarado
memoria memory-- que

13
00:00:34,980 --> 00:00:38,730
nome, variables que nome, et
cadros cetera e función que tamén

14
00:00:38,730 --> 00:00:41,000
hai cadros de pila de chamadas.

15
00:00:41,000 --> 00:00:45,421
Polo tanto, esta é unha estrutura de datos pila
non un segmento de pila de memoria.

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

17
00:00:45,920 --> 00:00:46,890
>> Pero o que é unha pila?

18
00:00:46,890 --> 00:00:49,220
Por iso, é practicamente só un
tipo especial de estrutura

19
00:00:49,220 --> 00:00:51,190
que mantén os datos de forma organizada.

20
00:00:51,190 --> 00:00:53,760
E hai dous moi
formas comúns para poñer en práctica

21
00:00:53,760 --> 00:00:57,380
pilas usando dúas estruturas de datos
que xa está familiarizado con,

22
00:00:57,380 --> 00:01:00,340
matrices e listas ligadas.

23
00:01:00,340 --> 00:01:04,430
O que fai unha pila especial é o
xeito en que podemos poñer información

24
00:01:04,430 --> 00:01:08,200
na pila, eo xeito que
eliminar a información a partir do conxunto.

25
00:01:08,200 --> 00:01:11,600
En particular coas pilas
a regra é só o máis

26
00:01:11,600 --> 00:01:15,830
recentemente elemento engadido pode ser eliminado.

27
00:01:15,830 --> 00:01:17,660
>> Entón, pense nisto como se fose unha pila.

28
00:01:17,660 --> 00:01:21,170
Estamos acumulando información
enriba de si,

29
00:01:21,170 --> 00:01:24,271
e só a cousa na parte superior
do conxunto pode ser borrada.

30
00:01:24,271 --> 00:01:27,020
Non podemos eliminar a cousa por baixo
porque todo o demais sería

31
00:01:27,020 --> 00:01:28,020
colapso e caer.

32
00:01:28,020 --> 00:01:32,580
Entón, nós realmente estamos a construír unha pila que
entón, temos que eliminar peza por peza.

33
00:01:32,580 --> 00:01:36,590
Debido a iso, xeralmente se refiren
para unha pila LIFO como unha estrutura,

34
00:01:36,590 --> 00:01:38,940
último a entrar, primeiro en saír.

35
00:01:38,940 --> 00:01:42,290
LIFO, último a entrar, primeiro en saír.

36
00:01:42,290 --> 00:01:45,635
>> Así, debido a esta restrición
como a información pode ser engadida aos

37
00:01:45,635 --> 00:01:49,080
e eliminar a partir dunha pila, non hai realmente
só dúas cousas que podemos facer cunha pila.

38
00:01:49,080 --> 00:01:52,010
Podemos empurrar, que é a
termo que usan para engadir

39
00:01:52,010 --> 00:01:55,130
un novo elemento ao cume do
pila, a pila ou se non existe

40
00:01:55,130 --> 00:01:58,550
e estamos a crear a partir de cero,
crear a pila primeiro

41
00:01:58,550 --> 00:02:00,110
sería empurrar.

42
00:02:00,110 --> 00:02:04,990
E logo, pop, que é o tipo de CS
termo que usan para eliminar o máis recentemente

43
00:02:04,990 --> 00:02:08,330
elemento engadido dende o principio da pila.

44
00:02:08,330 --> 00:02:11,130
>> Entón, imos ollar para os dous
implementacións, en base tanto matriz

45
00:02:11,130 --> 00:02:13,120
e lista ligada baseado.

46
00:02:13,120 --> 00:02:14,870
E nós estamos indo a
comezar matriz baseada.

47
00:02:14,870 --> 00:02:19,990
Entón aquí está a idea básica que
a estrutura de datos pila matriz baseada

48
00:02:19,990 --> 00:02:21,140
sería semellante.

49
00:02:21,140 --> 00:02:23,740
Temos unha definición ingresaran aquí.

50
00:02:23,740 --> 00:02:27,790
Dentro de que temos dous membros
ou campos da estrutura.

51
00:02:27,790 --> 00:02:29,880
Temos unha matriz.

52
00:02:29,880 --> 00:02:32,400
E unha vez máis está a usar o
valor tipo de datos arbitrario.

53
00:02:32,400 --> 00:02:35,180
>> Polo tanto, este pode ser calquera tipo de datos,
int char ou algúns outros datos

54
00:02:35,180 --> 00:02:37,080
o tipo que creou anteriormente.

55
00:02:37,080 --> 00:02:39,861
Polo tanto, temos un conxunto de capacidade tamaño.

56
00:02:39,861 --> 00:02:44,010
Capacidade sendo unha libra constante definida,
quizais noutro lugar na nosa arquivo.

57
00:02:44,010 --> 00:02:47,550
Entón, observe xa con este particular
implantación estamos delimitador

58
00:02:47,550 --> 00:02:49,800
nos como era tipicamente
o caso matrices,

59
00:02:49,800 --> 00:02:53,170
que non pode cambiar o tamaño dinamicamente,
onde hai un número

60
00:02:53,170 --> 00:02:55,450
de elementos que máximo
podemos poñer na nosa pila.

61
00:02:55,450 --> 00:02:57,930
Neste caso, é elementos de capacidade.

62
00:02:57,930 --> 00:03:00,310
>> Tamén manter o control de
o principio da pila.

63
00:03:00,310 --> 00:03:04,350
O elemento é o máis
recentemente engadido á pila?

64
00:03:04,350 --> 00:03:07,470
E, así, manter o control de que
nunha variable chamada superior.

65
00:03:07,470 --> 00:03:11,692
E todo iso queda envolto en conxunto
para un novo tipo de datos chamado unha pila.

66
00:03:11,692 --> 00:03:13,400
E xa que son creados
este novo tipo de datos

67
00:03:13,400 --> 00:03:15,410
podemos tratala como
calquera outro tipo de datos.

68
00:03:15,410 --> 00:03:20,970
Podemos declarar pila s, así como
poderíamos facer int x, y ou carbón.

69
00:03:20,970 --> 00:03:22,990
E cando dicimos apilar
s, así que pasa

70
00:03:22,990 --> 00:03:26,420
é que obter un conxunto de
memoria reservada para nós.

71
00:03:26,420 --> 00:03:28,770
>> Neste caso capacidade
Eu parecer decidiu

72
00:03:28,770 --> 00:03:33,470
10 é porque eu teño un
única variable do tipo de pila

73
00:03:33,470 --> 00:03:35,320
que contén dous campos recordar.

74
00:03:35,320 --> 00:03:38,330
Unha matriz, neste caso vai
para ser unha matriz de números enteiros

75
00:03:38,330 --> 00:03:40,440
como é o caso na maioría das miñas exemplos.

76
00:03:40,440 --> 00:03:43,996
E outra variable enteira
capaz de almacenar o cumio,

77
00:03:43,996 --> 00:03:45,870
o engadido máis recentemente
para o elemento de pila.

78
00:03:45,870 --> 00:03:50,290
Así, unha única pila que nós
só mira como esta definido.

79
00:03:50,290 --> 00:03:53,190
É unha caixa que contén
unha matriz de 10 que

80
00:03:53,190 --> 00:03:57,280
serán enteiros, neste caso, e
outra variable enteira alí en verde

81
00:03:57,280 --> 00:04:00,010
para indicar a parte superior do conxunto.

82
00:04:00,010 --> 00:04:02,600
>> Para axustar a parte superior da
pila nós só dicir s.top.

83
00:04:02,600 --> 00:04:04,890
Isto é como nós acceder a un
campo dun recall estrutura.

84
00:04:04,890 --> 00:04:10,460
s.top é igual a 0 efectivamente
fai isto para a pila.

85
00:04:10,460 --> 00:04:12,960
Entón, de novo, temos dúas operacións
que pode realizar-se agora.

86
00:04:12,960 --> 00:04:14,270
Podemos empurrar e podemos pop.

87
00:04:14,270 --> 00:04:15,635
Imos comezar con pulo.

88
00:04:15,635 --> 00:04:18,260
Unha vez máis, empurrando é a adición dun novo
elemento para arriba da pila.

89
00:04:18,260 --> 00:04:21,460
>> Entón, o que necesitamos facer en
esa matriz implementación baseada?

90
00:04:21,460 --> 00:04:23,210
Ben, en xeral, a
función push vai

91
00:04:23,210 --> 00:04:26,160
a necesidade de aceptar un
punteiro para a pila.

92
00:04:26,160 --> 00:04:28,610
Agora tome un segundo e pensar sobre iso.

93
00:04:28,610 --> 00:04:32,840
Por que iríamos querer aceptar
un punteiro para a pila?

94
00:04:32,840 --> 00:04:36,830
Teña en conta que de vídeos anteriores sobre
ámbito de variables e punteiros,

95
00:04:36,830 --> 00:04:42,350
o que acontecería se nós só enviado
pila, s, no canto de como un parámetro?

96
00:04:42,350 --> 00:04:45,770
O que sería realmente pasou alí dentro?

97
00:04:45,770 --> 00:04:49,430
Lembre que estamos creando unha copia
cando pasalo a unha función

98
00:04:49,430 --> 00:04:51,160
a menos que usar punteiros.

99
00:04:51,160 --> 00:04:55,380
E así esta función empurrar necesidades
para aceptar un punteiro para a pila

100
00:04:55,380 --> 00:04:59,160
de xeito que estamos realmente cambiando
a pila pretendemos cambiar.

101
00:04:59,160 --> 00:05:03,060
>> A outra cousa impulso probablemente quere
aceptar é un elemento de datos do valor tipo.

102
00:05:03,060 --> 00:05:06,970
Neste caso, de novo, un número enteiro que
nós estamos indo a engadir ao principio da pila.

103
00:05:06,970 --> 00:05:08,680
Entón, nós temos os nosos dous parámetros.

104
00:05:08,680 --> 00:05:11,310
Que imos
agora facer dentro impulso?

105
00:05:11,310 --> 00:05:14,860
Ben, simplemente, nós só estamos indo para engadir
que o elemento de parte superior do conxunto

106
00:05:14,860 --> 00:05:22,860
e, a continuación, cambiar o lugar onde a parte superior
a pila é, iso é punto alto valor.

107
00:05:22,860 --> 00:05:25,639
Entón é iso que unha función
declaración para push

108
00:05:25,639 --> 00:05:27,680
pode parecer nun
baseada en array implementación.

109
00:05:27,680 --> 00:05:30,967
>> De novo, isto non é unha regra dura e rápida
que pode cambiar iso e ter

110
00:05:30,967 --> 00:05:32,050
que varían de formas diferentes.

111
00:05:32,050 --> 00:05:33,840
Quizais s é declarado globalmente.

112
00:05:33,840 --> 00:05:36,180
E para que non precisa aínda
para pasalo é como un parámetro.

113
00:05:36,180 --> 00:05:39,125
Esta é só unha outra vez
caso xeral para push.

114
00:05:39,125 --> 00:05:41,000
E hai diferentes
formas de implementar lo.

115
00:05:41,000 --> 00:05:42,810
Pero, neste caso, o noso
pulo levará

116
00:05:42,810 --> 00:05:48,540
dous argumentos, un punteiro para unha pila e
un elemento de datos do valor tipo, número enteiro

117
00:05:48,540 --> 00:05:49,840
neste caso.

118
00:05:49,840 --> 00:05:52,100
>> Por iso, declarou s, nós
dixo s.top é igual a 0.

119
00:05:52,100 --> 00:05:55,969
Agora imos empurrar o
número 28 na pila.

120
00:05:55,969 --> 00:05:57,010
Ben, o que significa isto?

121
00:05:57,010 --> 00:05:59,600
Ben actualmente o
parte superior da pila é 0.

122
00:05:59,600 --> 00:06:01,350
E entón o que é basicamente
ocorrerá é

123
00:06:01,350 --> 00:06:05,820
nós estamos indo a furar o número
28 en array local 0.

124
00:06:05,820 --> 00:06:09,540
Moi sinxelo, non, que
foi a top e agora somos bos de ir.

125
00:06:09,540 --> 00:06:12,910
E entón temos que cambiar o que
o principio da pila será.

126
00:06:12,910 --> 00:06:15,130
De xeito que a próxima vez
que empurra un elemento,

127
00:06:15,130 --> 00:06:18,017
nós estamos indo a almacena-lo
localización matriz, probablemente non 0.

128
00:06:18,017 --> 00:06:20,100
Non queremos substituír
o que acabamos de poñer alí.

129
00:06:20,100 --> 00:06:23,510
E por iso imos mover a parte superior a 1.

130
00:06:23,510 --> 00:06:24,890
Isto probablemente ten sentido.

131
00:06:24,890 --> 00:06:28,940
>> Agora, se queremos poñer outro elemento
na pila, dicir que queremos empurrar 33,

132
00:06:28,940 --> 00:06:33,190
ben, agora estamos só vai levar 33
e poñelas en número de localización matriz

133
00:06:33,190 --> 00:06:37,580
1, e, a continuación, cambiar o cume da nosa
apilar para ser matriz número local dous.

134
00:06:37,580 --> 00:06:40,650
Entón, se a próxima vez que quere
empurrar un elemento na pila,

135
00:06:40,650 --> 00:06:43,087
vai ser colocadas no lugar da matriz 2.

136
00:06:43,087 --> 00:06:44,420
E imos facelo unha vez máis.

137
00:06:44,420 --> 00:06:45,753
Imos empurrar 19 fóra das pilas.

138
00:06:45,753 --> 00:06:48,940
Nós imos poñer 19 en situación matriz 2
e cambie o principio da nosa pila

139
00:06:48,940 --> 00:06:51,220
para ser localización matriz 3
por iso, a próxima vez nós

140
00:06:51,220 --> 00:06:54,780
cómpre facer un esforzo que está preparado para ir.

141
00:06:54,780 --> 00:06:56,980
>> OK, así que tendo en poucas palabras.

142
00:06:56,980 --> 00:06:57,830
O que sobre o estalo?

143
00:06:57,830 --> 00:07:00,240
Entón popping é o tipo de
contrapartida para empurrar.

144
00:07:00,240 --> 00:07:02,720
É así que eliminar os datos do conxunto.

145
00:07:02,720 --> 00:07:04,610
E en necesidades pop xerais
para facer o seguinte.

146
00:07:04,610 --> 00:07:07,600
Debes aceptar un punteiro para o
Pila, de novo, no caso xeral.

147
00:07:07,600 --> 00:07:10,480
Nalgún outro caso, pode
declarar a pila globalmente,

148
00:07:10,480 --> 00:07:13,910
caso en que non precisa pasalo
no sistema porque xa ten acceso a el

149
00:07:13,910 --> 00:07:15,541
como unha variable global.

150
00:07:15,541 --> 00:07:17,040
Pero entón o que máis facer o que necesitamos facer?

151
00:07:17,040 --> 00:07:21,000
Ben, fomos incrementando
o principio da pila no impulso,

152
00:07:21,000 --> 00:07:24,050
así que estamos probablemente vai querer
para diminuír o principio da pila

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

154
00:07:25,009 --> 00:07:26,800
E despois, claro
estamos tamén vai querer

155
00:07:26,800 --> 00:07:29,240
para voltar o valor que eliminar.

156
00:07:29,240 --> 00:07:32,125
Se estamos engadindo elementos, queremos
para obter elementos para fóra máis tarde,

157
00:07:32,125 --> 00:07:34,000
nós probablemente verdade
quere almacena-los polo que

158
00:07:34,000 --> 00:07:36,490
non só borralos do
apilar e despois non facer nada con eles.

159
00:07:36,490 --> 00:07:38,500
Xeralmente, se somos
empurrando e estalado aquí

160
00:07:38,500 --> 00:07:41,250
queremos almacenar este
información de forma significativa

161
00:07:41,250 --> 00:07:43,250
e por iso non fai
sentido só descartalo lo.

162
00:07:43,250 --> 00:07:46,380
Así, esta función debe
probablemente voltar un valor para nós.

163
00:07:46,380 --> 00:07:51,040
>> Entón é iso que unha declaración de pop
pode parecer que hai na parte superior esquerda.

164
00:07:51,040 --> 00:07:53,870
Esta función devolve
datos de valor tipo.

165
00:07:53,870 --> 00:07:56,320
Unha vez máis nós estivemos usando
enteiros todo.

166
00:07:56,320 --> 00:08:01,916
E acepta un punteiro para unha pila como
o seu único argumento ou parámetro único.

167
00:08:01,916 --> 00:08:03,040
Entón, o que é pop vai facer?

168
00:08:03,040 --> 00:08:07,990
Digamos que queremos agora
pop un elemento fóra de s.

169
00:08:07,990 --> 00:08:14,000
Entón lembre, eu dixen que pilas son pasado
in, first out, estruturas de datos LIFO.

170
00:08:14,000 --> 00:08:17,855
Cal elemento vai
ser eliminado da pila?

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

172
00:08:21,780 --> 00:08:24,150
Será que adiviña 19?

173
00:08:24,150 --> 00:08:25,290
Porque estaría ben.

174
00:08:25,290 --> 00:08:28,836
19 foi o último elemento que engade ao
apilar cando estabamos empurrando elementos,

175
00:08:28,836 --> 00:08:31,210
e por iso vai para o primeiro
elemento que é eliminado.

176
00:08:31,210 --> 00:08:34,780
É coma se dixésemos 28, e
entón imos poñer 33 enriba dela,

177
00:08:34,780 --> 00:08:36,659
e poñemos 19 enriba diso.

178
00:08:36,659 --> 00:08:40,650
O único elemento que podemos sacar é de 19.

179
00:08:40,650 --> 00:08:45,019
>> Agora no diagrama aquí o que eu fixen
é unha especie de borrada 19 desde a matriz.

180
00:08:45,019 --> 00:08:46,810
Iso non é certo,
o que imos facer.

181
00:08:46,810 --> 00:08:48,934
Nós só estamos indo a tipo
de finxir que non está alí.

182
00:08:48,934 --> 00:08:51,441
El aínda está alí en
que a localización de memoria,

183
00:08:51,441 --> 00:08:54,190
pero nós só estamos indo a ignore-lo
cambiando o principio da pila noso

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

185
00:08:56,080 --> 00:08:58,720
Entón, se nós estabamos a empurrar agora
outro elemento na pila,

186
00:08:58,720 --> 00:09:00,720
que ía sobre escribir 19.

187
00:09:00,720 --> 00:09:03,990
>> Pero non imos pasar pola dificultade
exclusión de 19 desde a pila.

188
00:09:03,990 --> 00:09:05,830
Podemos só finxir que non está alí.

189
00:09:05,830 --> 00:09:11,107
Para fins da pila é ir se
mudarmos a top para ser 2 en vez de 3.

190
00:09:11,107 --> 00:09:12,690
Todo ben, entón iso foi moi bonito iso.

191
00:09:12,690 --> 00:09:15,080
Isto é todo o que necesitamos facer
a pop un elemento fóra.

192
00:09:15,080 --> 00:09:16,090
Imos facelo de novo.

193
00:09:16,090 --> 00:09:18,610
Entón, eu teño resaltado en vermello aquí para
indican que estamos a facer outra chamada.

194
00:09:18,610 --> 00:09:19,720
Nós imos facer o mesmo.

195
00:09:19,720 --> 00:09:20,803
>> Entón, o que vai pasar?

196
00:09:20,803 --> 00:09:23,670
Ben, nós estamos indo a almacenar
33 en x e imos

197
00:09:23,670 --> 00:09:26,217
para cambiar o cume da pila para 1.

198
00:09:26,217 --> 00:09:29,050
Así que, se fósemos agora a empurrar un
elemento na pila que somos

199
00:09:29,050 --> 00:09:31,610
vai facer agora,
o que vai pasar

200
00:09:31,610 --> 00:09:36,367
é que imos eliminar
matriz número de localización 1.

201
00:09:36,367 --> 00:09:38,950
Así que 33 que era unha especie de esquerda
detrás de que só finxiu

202
00:09:38,950 --> 00:09:44,390
non está alí, nós só estamos indo
a espancar-lo e poñer alí en vez de 40.

203
00:09:44,390 --> 00:09:46,290
E despois, claro,
sempre que fixemos un empurrón,

204
00:09:46,290 --> 00:09:48,780
imos incrementar o
parte superior do conxunto a partir do 1 de 2

205
00:09:48,780 --> 00:09:50,950
de xeito que se engaden-se agora
outro elemento que vai

206
00:09:50,950 --> 00:09:54,700
entrar matriz número local dous.

207
00:09:54,700 --> 00:09:57,590
>> Agora listas ligadas son outro
forma de aplicar pilas.

208
00:09:57,590 --> 00:10:01,210
E, se esta definición no
pantalla aquí parece familiar para ti,

209
00:10:01,210 --> 00:10:04,260
é porque parece case
exactamente o mesmo, de feito,

210
00:10:04,260 --> 00:10:07,790
el practicamente é o
mesmo como unha lista vinculada illadamente,

211
00:10:07,790 --> 00:10:11,990
se se lembra da nosa discusión sobre
listas individualmente ligados no outro vídeo.

212
00:10:11,990 --> 00:10:15,510
A única limitación aquí
é para nós como programadores,

213
00:10:15,510 --> 00:10:17,900
non estamos autorizados a
inserir ou eliminar azar

214
00:10:17,900 --> 00:10:20,620
da lista vinculada illadamente
que anteriormente podían facer.

215
00:10:20,620 --> 00:10:25,820
Agora só pode inserir e eliminar da
dianteira ou a parte superior do ligada

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

217
00:10:26,320 --> 00:10:28,028
Isto é realmente o único
diferenza aínda.

218
00:10:28,028 --> 00:10:29,700
Esta é outra forma de lista vinculada illadamente.

219
00:10:29,700 --> 00:10:32,060
É só a restrición
substituíndo en nós mesmos

220
00:10:32,060 --> 00:10:35,770
como programadores que
cambia-lo nunha pila.

221
00:10:35,770 --> 00:10:39,280
>> A regra aquí é manter sempre unha
Punteiro para a cabeza dunha lista ligada.

222
00:10:39,280 --> 00:10:41,520
Este é, naturalmente, un xeral
regra importante en primeiro lugar.

223
00:10:41,520 --> 00:10:44,260
Para illadamente lista ligada de forma
só precisa dun punteiro para a cabeza

224
00:10:44,260 --> 00:10:46,160
de xeito que teñen
cadea de poder encamiñar

225
00:10:46,160 --> 00:10:48,596
para todos os outros elementos
na lista vinculada.

226
00:10:48,596 --> 00:10:50,470
Pero é especialmente
importante cunha pila.

227
00:10:50,470 --> 00:10:52,386
E de modo xeral, é
vai realmente queren

228
00:10:52,386 --> 00:10:54,090
este punteiro para ser unha variable global.

229
00:10:54,090 --> 00:10:56,574
El probablemente vai
ser aínda máis fácil desa maneira.

230
00:10:56,574 --> 00:10:58,240
Entón, cales son os análogos de push e pop?

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

232
00:10:58,740 --> 00:11:01,812
Entón, empurrando de novo é a suma de
un elemento novo para a pila.

233
00:11:01,812 --> 00:11:03,770
Nunha lista vinculada que
significa que nós imos ter

234
00:11:03,770 --> 00:11:07,770
para crear un novo nodo que somos
vai engadir na lista ligada,

235
00:11:07,770 --> 00:11:10,500
e, a continuación, siga os pasos coidadosos
que temos delineado anteriormente

236
00:11:10,500 --> 00:11:16,050
en listas individualmente ligados ao engadir lo á
a cadea sen romper a cadea

237
00:11:16,050 --> 00:11:18,900
e perder ou orfandade calquera
elementos da lista ligada.

238
00:11:18,900 --> 00:11:21,820
E iso é basicamente o que iso
pouco blob de texto alí resume.

239
00:11:21,820 --> 00:11:23,740
E imos dar un ollo
para el como un diagrama.

240
00:11:23,740 --> 00:11:24,823
>> Entón aquí está a nosa lista ligada.

241
00:11:24,823 --> 00:11:26,620
Contén catro elementos simultaneamente.

242
00:11:26,620 --> 00:11:30,420
E máis perfectamente aquí está a nosa
apilar contén catro elementos.

243
00:11:30,420 --> 00:11:36,030
E digamos que queremos agora
empurrar un novo elemento para esta pila.

244
00:11:36,030 --> 00:11:39,792
E quero empurrar un novo
elemento cuxo valor de datos é de 12.

245
00:11:39,792 --> 00:11:41,000
Ben, o que imos facer?

246
00:11:41,000 --> 00:11:43,420
Ben, primeiro imos
espazo malloc, dinamicamente

247
00:11:43,420 --> 00:11:45,411
reservar espazo para un novo nodo.

248
00:11:45,411 --> 00:11:48,160
E, por suposto, inmediatamente despois
facemos unha chamada a malloc sempre

249
00:11:48,160 --> 00:11:52,989
asegúrese de comprobar a null,
porque se nós ficássemos nula de volta

250
00:11:52,989 --> 00:11:54,280
houbo algún tipo de problema.

251
00:11:54,280 --> 00:11:57,570
Non queremos eliminar a referencia que nulo
punteiro ou vai sufrir un fallo seg.

252
00:11:57,570 --> 00:11:58,510
Iso non é bo.

253
00:11:58,510 --> 00:11:59,760
Entón, nós temos malloced do nó.

254
00:11:59,760 --> 00:12:01,260
Imos asumir que tivemos éxito aquí.

255
00:12:01,260 --> 00:12:06,090
Nós imos poñer 12 en
O campo de datos dese nodo.

256
00:12:06,090 --> 00:12:11,570
Agora se lembra cal dos nosos punteiros
move seguinte polo tanto, non romper a cadea?

257
00:12:11,570 --> 00:12:15,100
Temos un par de opcións aquí, pero
o único que vai ser seguro

258
00:12:15,100 --> 00:12:19,330
é definir noticia próximo punteiro para
apunte ao antigo xefe da lista

259
00:12:19,330 --> 00:12:21,360
ou o que en breve será o
antigo cabeza da lista.

260
00:12:21,360 --> 00:12:23,610
E agora que todo o noso
elementos son encadeados,

261
00:12:23,610 --> 00:12:27,370
podemos lista só mover apuntar
para o mesmo lugar que fai novo.

262
00:12:27,370 --> 00:12:33,550
E nós temos agora efectivamente empurrou un
novo elemento para a fronte da pila.

263
00:12:33,550 --> 00:12:36,420
>> Para pop nós só queremos
eliminar ese primeiro elemento.

264
00:12:36,420 --> 00:12:38,150
E así, basicamente o que
temos que facer aquí,

265
00:12:38,150 --> 00:12:40,050
ben temos que atopar o segundo elemento.

266
00:12:40,050 --> 00:12:43,540
Finalmente, que se converteu no novo
cabeza despois de eliminar a primeira.

267
00:12:43,540 --> 00:12:47,300
Entón, só necesitamos comezar a partir de
o inicio, move un para adiante.

268
00:12:47,300 --> 00:12:50,340
Unha vez que temos un soto nun
á fronte de onde estamos actualmente

269
00:12:50,340 --> 00:12:53,850
somos nós pode eliminar a primeira con seguridade
e entón podemos simplemente mover a cabeza

270
00:12:53,850 --> 00:12:57,150
para apuntar para o que era o
segundo mandato e, a continuación, agora

271
00:12:57,150 --> 00:12:59,170
é a primeira que despois
nó foi eliminado.

272
00:12:59,170 --> 00:13:01,160
>> Entón, de novo, dando un ollo
para el como un diagrama de nós

273
00:13:01,160 --> 00:13:05,022
quere agora un pop
elemento fora da pila.

274
00:13:05,022 --> 00:13:05,730
Entón, o que facemos?

275
00:13:05,730 --> 00:13:08,188
Ben, imos primeiro en crear
un novo punteiro que está pasando

276
00:13:08,188 --> 00:13:10,940
para apuntar para o mesmo lugar como a cabeza.

277
00:13:10,940 --> 00:13:13,790
Estamos indo para movelo unha posición
para adiante dicindo iguais trav

278
00:13:13,790 --> 00:13:17,510
trav próxima, por exemplo, que
avanzaría a un punteiro trav

279
00:13:17,510 --> 00:13:19,324
posición para adiante.

280
00:13:19,324 --> 00:13:21,240
Agora que temos un
soster o primeiro elemento

281
00:13:21,240 --> 00:13:24,573
a través da lista punteiro chamado, ea
segundo elemento a través dun chamado punteiro

282
00:13:24,573 --> 00:13:28,692
trav podemos eliminar con seguridade que
primeiro elemento a partir do conxunto

283
00:13:28,692 --> 00:13:30,650
sen perder o resto
da cadea porque

284
00:13:30,650 --> 00:13:32,358
ten un xeito de referirse
para o segundo elemento

285
00:13:32,358 --> 00:13:34,780
transmitir a través do
punteiro chamado trav.

286
00:13:34,780 --> 00:13:37,100
>> Entón agora podemos liberar ese nó.

287
00:13:37,100 --> 00:13:38,404
Podemos liberar lista.

288
00:13:38,404 --> 00:13:41,320
E entón todo o que necesitamos facer agora é
lista mover apuntar ao mesmo lugar

289
00:13:41,320 --> 00:13:44,482
trav que fai, e nós somos tipo de volta
onde comezamos antes que empuxou 12

290
00:13:44,482 --> 00:13:45,690
sobre, en primeiro lugar, á dereita.

291
00:13:45,690 --> 00:13:46,940
Este é onde estabamos.

292
00:13:46,940 --> 00:13:48,840
Tivemos esa pila de catro elementos.

293
00:13:48,840 --> 00:13:49,690
Nós engadimos un quinto.

294
00:13:49,690 --> 00:13:51,910
Nós empurramos unha quinta
elemento, e entón nós

295
00:13:51,910 --> 00:13:55,980
estalou que, máis recentemente,
elemento engadido de volta ao ancho.

296
00:13:55,980 --> 00:13:58,816
>> Isto é realmente moi bonito
todo o que hai para pilas.

297
00:13:58,816 --> 00:14:00,190
Pode implementar las como matrices.

298
00:14:00,190 --> 00:14:01,815
Pode implementar las como listas ligadas.

299
00:14:01,815 --> 00:14:04,810
Existen, por suposto, outros
formas de implementar las tamén.

300
00:14:04,810 --> 00:14:09,060
Basicamente, a razón nós usariamos
pilas é manter os datos, de tal xeito

301
00:14:09,060 --> 00:14:12,090
o que máis recentemente engadido
elemento é o primeiro que somos

302
00:14:12,090 --> 00:14:14,980
Vai querer volver.

303
00:14:14,980 --> 00:14:17,900
Eu son Doug Lloyd, este é CS50.

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