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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Muy bien,
así que en este punto estás

3
00:00:05,990 --> 00:00:09,020
probablemente bastante familiarizado
con matrices y listas enlazadas

4
00:00:09,020 --> 00:00:10,950
que es el de dos primaria
estructuras de datos que hemos

5
00:00:10,950 --> 00:00:16,810
hablado de mantener conjuntos de
datos de tipos de datos similares organizada.

6
00:00:16,810 --> 00:00:19,080
>> Ahora vamos a hablar
alrededor de un par de variaciones

7
00:00:19,080 --> 00:00:20,330
en matrices y listas enlazadas.

8
00:00:20,330 --> 00:00:22,362
En este video vamos
para hablar de las pilas.

9
00:00:22,362 --> 00:00:25,320
En concreto vamos a hablar
sobre una estructura de datos llamada una pila.

10
00:00:25,320 --> 00:00:28,510
Recuerde que en los debates anteriores
acerca de los punteros y memoria,

11
00:00:28,510 --> 00:00:32,060
que la pila es también el
nombrar para un segmento de la memoria

12
00:00:32,060 --> 00:00:34,980
donde declara estáticamente
memoria memory-- que

13
00:00:34,980 --> 00:00:38,730
nombre, variables que usted nombre, et
marcos cetera y función que también

14
00:00:38,730 --> 00:00:41,000
existen marcos de pila de llamadas.

15
00:00:41,000 --> 00:00:45,421
Así que esta es una estructura de datos de la pila
no es un segmento de pila de la memoria.

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

17
00:00:45,920 --> 00:00:46,890
>> Pero, ¿qué es una pila?

18
00:00:46,890 --> 00:00:49,220
Así que es prácticamente sólo una
tipo especial de estructura

19
00:00:49,220 --> 00:00:51,190
que mantiene los datos de una manera organizada.

20
00:00:51,190 --> 00:00:53,760
Y hay dos muy
formas comunes de implementar

21
00:00:53,760 --> 00:00:57,380
pilas utilizando dos estructuras de datos
que ya estamos familiarizados,

22
00:00:57,380 --> 00:01:00,340
matrices y listas enlazadas.

23
00:01:00,340 --> 00:01:04,430
¿Qué hace un especial de pila es el
manera en que ponemos la información

24
00:01:04,430 --> 00:01:08,200
en la pila, y la forma en que
eliminar la información de la pila.

25
00:01:08,200 --> 00:01:11,600
En particular con las pilas
la regla es sólo el más

26
00:01:11,600 --> 00:01:15,830
recientemente elemento añadido se puede quitar.

27
00:01:15,830 --> 00:01:17,660
>> Así que pensar en ello como si fuera una pila.

28
00:01:17,660 --> 00:01:21,170
Estamos acumulando información
en la parte superior de la misma,

29
00:01:21,170 --> 00:01:24,271
y sólo la cosa en la parte superior
de la pila se puede quitar.

30
00:01:24,271 --> 00:01:27,020
No podemos quitar la cosa debajo
porque todo lo demás lo haría

31
00:01:27,020 --> 00:01:28,020
colapsar y caer.

32
00:01:28,020 --> 00:01:32,580
Así que realmente estamos construyendo una pila que
entonces tenemos que eliminar pieza por pieza.

33
00:01:32,580 --> 00:01:36,590
Debido a esto nos referimos comúnmente
a una pila como una estructura LIFO,

34
00:01:36,590 --> 00:01:38,940
último en entrar primero en salir.

35
00:01:38,940 --> 00:01:42,290
LIFO, último en entrar, primero en salir.

36
00:01:42,290 --> 00:01:45,635
>> Así que debido a esta restricción en
cómo la información puede ser añadido a

37
00:01:45,635 --> 00:01:49,080
y retirado de una pila, no hay realmente
sólo dos cosas que pueden hacer con una pila.

38
00:01:49,080 --> 00:01:52,010
Podemos empujar, que es el
término que usamos para añadir

39
00:01:52,010 --> 00:01:55,130
un nuevo elemento a la parte superior de la
pila, o si la pila no existe

40
00:01:55,130 --> 00:01:58,550
y estamos creando desde cero,
la creación de la pila en el primer lugar

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

42
00:02:00,110 --> 00:02:04,990
Y a continuación, el pop, que es el tipo de CS
término que usamos para quitar el más reciente

43
00:02:04,990 --> 00:02:08,330
elemento añadido desde la parte superior de la pila.

44
00:02:08,330 --> 00:02:11,130
>> Así que vamos a mirar a ambos
implementaciones, basado tanto array

45
00:02:11,130 --> 00:02:13,120
y lista enlazada con base.

46
00:02:13,120 --> 00:02:14,870
Y vamos a
comenzar con matriz basada.

47
00:02:14,870 --> 00:02:19,990
Así que aquí está la idea básica de lo que
la estructura de datos basada en pila de conjuntos

48
00:02:19,990 --> 00:02:21,140
se vería así.

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

50
00:02:23,740 --> 00:02:27,790
En el interior de la que tenemos dos miembros
o campos de la estructura.

51
00:02:27,790 --> 00:02:29,880
Tenemos una matriz.

52
00:02:29,880 --> 00:02:32,400
Y otra vez estoy usando el
valor de tipo de datos arbitrarios.

53
00:02:32,400 --> 00:02:35,180
>> Así que este podría ser cualquier tipo de datos,
int carbón o algún otro dato

54
00:02:35,180 --> 00:02:37,080
escribe que ha creado anteriormente.

55
00:02:37,080 --> 00:02:39,861
Así que tenemos una gran variedad de capacidad de tamaño.

56
00:02:39,861 --> 00:02:44,010
Capacidad de ser una libra define constante,
tal vez en otro lugar en nuestro archivo.

57
00:02:44,010 --> 00:02:47,550
Así que ya cuenta con este particular
aplicación estamos delimitador

58
00:02:47,550 --> 00:02:49,800
nosotros mismos como era normalmente
en el caso de arrays,

59
00:02:49,800 --> 00:02:53,170
que no podemos cambiar el tamaño de forma dinámica,
donde hay un cierto número

60
00:02:53,170 --> 00:02:55,450
de elementos máxima que
podemos poner en nuestra pila.

61
00:02:55,450 --> 00:02:57,930
En este caso se trata de elementos de capacidad.

62
00:02:57,930 --> 00:03:00,310
>> También mantenemos un registro de
la parte superior de la pila.

63
00:03:00,310 --> 00:03:04,350
¿Qué elemento es el más
en fecha reciente a la pila?

64
00:03:04,350 --> 00:03:07,470
Y así hacemos un seguimiento de que
en una variable llamada superior.

65
00:03:07,470 --> 00:03:11,692
Y todo esto se envuelve juntos
en un nuevo tipo de datos llamado una pila.

66
00:03:11,692 --> 00:03:13,400
Y una vez que fuimos creados
este nuevo tipo de datos

67
00:03:13,400 --> 00:03:15,410
podemos tratarlo como
cualquier otro tipo de datos.

68
00:03:15,410 --> 00:03:20,970
Podemos declarar pila s, al igual que
podríamos hacer int x, o de carbón y.

69
00:03:20,970 --> 00:03:22,990
Y cuando decimos apilamos
s, así lo que sucede

70
00:03:22,990 --> 00:03:26,420
está obtenemos un conjunto de
de memoria reservado para nosotros.

71
00:03:26,420 --> 00:03:28,770
>> En este caso, la capacidad
Al parecer, he decidido

72
00:03:28,770 --> 00:03:33,470
es 10 porque tengo un
única variable de tipo pila

73
00:03:33,470 --> 00:03:35,320
que contiene dos campos recuerdan.

74
00:03:35,320 --> 00:03:38,330
Una matriz, en este caso va
ser una matriz de enteros

75
00:03:38,330 --> 00:03:40,440
como es el caso en la mayoría de mis ejemplos.

76
00:03:40,440 --> 00:03:43,996
Y otra variable entera
capaz de almacenar la parte superior,

77
00:03:43,996 --> 00:03:45,870
más recientemente añadido
elemento a la pila.

78
00:03:45,870 --> 00:03:50,290
Así que una sola pila de lo que
sólo se parece a esta definido.

79
00:03:50,290 --> 00:03:53,190
Es una caja que contiene
una serie de 10 lo

80
00:03:53,190 --> 00:03:57,280
serán números enteros en este caso, y
otra variable entera allí en verde

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

82
00:04:00,010 --> 00:04:02,600
>> Para establecer la parte superior de la
pila sólo decimos s.top.

83
00:04:02,600 --> 00:04:04,890
Esa es la forma en que accedemos a una
campo de una estructura de retiro.

84
00:04:04,890 --> 00:04:10,460
s.top es igual a 0 eficazmente
Hace esto a nuestra pila.

85
00:04:10,460 --> 00:04:12,960
Así que de nuevo tenemos dos operaciones
que podemos llevar a cabo ahora.

86
00:04:12,960 --> 00:04:14,270
Podemos empujar y podemos pop.

87
00:04:14,270 --> 00:04:15,635
Vamos a empezar con empuje.

88
00:04:15,635 --> 00:04:18,260
Una vez más, empujando es la adición de un nuevo
elemento a la parte superior de la pila.

89
00:04:18,260 --> 00:04:21,460
>> Entonces, ¿qué hacemos lo que necesitamos hacer en
esta matriz de implementación basada?

90
00:04:21,460 --> 00:04:23,210
Bueno en general
la función de empuje se va

91
00:04:23,210 --> 00:04:26,160
a tener que aceptar una
puntero a la pila.

92
00:04:26,160 --> 00:04:28,610
Ahora tómate un segundo y pensar en ello.

93
00:04:28,610 --> 00:04:32,840
¿Por qué querríamos aceptar
un puntero a la pila?

94
00:04:32,840 --> 00:04:36,830
Recuerde que en los videos anteriores sobre
alcance y punteros variables,

95
00:04:36,830 --> 00:04:42,350
¿qué pasaría si nos enviamos
pila, s en lugar de como un parámetro?

96
00:04:42,350 --> 00:04:45,770
Lo que en realidad se pasó ahí?

97
00:04:45,770 --> 00:04:49,430
Recuerde que estamos creando una copia
cuando se pasa a una función

98
00:04:49,430 --> 00:04:51,160
a menos que utilicemos punteros.

99
00:04:51,160 --> 00:04:55,380
Y así esta función empujar necesidades
para aceptar un puntero a la pila

100
00:04:55,380 --> 00:04:59,160
por lo que en realidad estamos cambiando
la pila tenemos la intención de cambiar.

101
00:04:59,160 --> 00:05:03,060
>> La otra cosa empuje probablemente quiere
aceptar es un elemento de datos de valor de tipo.

102
00:05:03,060 --> 00:05:06,970
En este caso, de nuevo, un número entero que
vamos a añadir a la parte superior de la pila.

103
00:05:06,970 --> 00:05:08,680
Así que tenemos nuestros dos parámetros.

104
00:05:08,680 --> 00:05:11,310
¿Qué vamos a
ahora hacer dentro de empuje?

105
00:05:11,310 --> 00:05:14,860
Bueno, simplemente, sólo vamos a añadir
ese elemento a la parte superior de la pila

106
00:05:14,860 --> 00:05:22,860
y luego cambiar en la parte superior de
la pila es, que s dot valor superior.

107
00:05:22,860 --> 00:05:25,639
Así que esto es lo que una función
declaración de empuje

108
00:05:25,639 --> 00:05:27,680
podría parecer en un
basada en arreglos de implementación.

109
00:05:27,680 --> 00:05:30,967
>> De nuevo, esto no es una regla dura y rápida
que podría cambiar esto y tener

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

111
00:05:32,050 --> 00:05:33,840
Tal vez s se declara globalmente.

112
00:05:33,840 --> 00:05:36,180
Y por lo que ni siquiera es necesario
pasar es como un parámetro.

113
00:05:36,180 --> 00:05:39,125
Esto es de nuevo sólo una
caso general para empujar.

114
00:05:39,125 --> 00:05:41,000
Y hay diferentes
maneras de ponerlo en práctica.

115
00:05:41,000 --> 00:05:42,810
Pero en este caso nuestra
empuje va a tomar

116
00:05:42,810 --> 00:05:48,540
dos argumentos, un puntero a una pila y
un elemento de datos de valor de tipo, número entero

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

118
00:05:49,840 --> 00:05:52,100
>> Así que declaramos s, nos
dijo s.top es igual a 0.

119
00:05:52,100 --> 00:05:55,969
Ahora vamos a empujar el
el número 28 en la pila.

120
00:05:55,969 --> 00:05:57,010
Bueno, ¿qué quiere decir eso?

121
00:05:57,010 --> 00:05:59,600
Bueno actualmente la
parte superior de la pila es 0.

122
00:05:59,600 --> 00:06:01,350
Y así, lo que es, básicamente,
va a pasar es

123
00:06:01,350 --> 00:06:05,820
vamos a pegar el número
28 en la ubicación array 0.

124
00:06:05,820 --> 00:06:09,540
Bastante sencillo, correcto, que
era la parte superior y ahora somos buenos para ir.

125
00:06:09,540 --> 00:06:12,910
Y entonces tenemos que cambiar lo que
la parte superior de la pila será.

126
00:06:12,910 --> 00:06:15,130
Así que la próxima vez
empujamos un elemento,

127
00:06:15,130 --> 00:06:18,017
vamos a guardarlo en
ubicación array, probablemente no 0.

128
00:06:18,017 --> 00:06:20,100
No queremos sobrescribir
lo que acabamos de poner allí.

129
00:06:20,100 --> 00:06:23,510
Y así sólo tendremos que mover la parte superior a 1.

130
00:06:23,510 --> 00:06:24,890
Eso probablemente tiene sentido.

131
00:06:24,890 --> 00:06:28,940
>> Ahora bien, si queremos poner otro elemento
en la pila, decimos que queremos empujar 33,

132
00:06:28,940 --> 00:06:33,190
Bueno, ahora sólo vamos a tomar 33
y lo puso en el número de ubicación de matriz

133
00:06:33,190 --> 00:06:37,580
1, y después cambiar la parte superior de nuestra
apilar ser ubicación matriz número dos.

134
00:06:37,580 --> 00:06:40,650
Así que si la próxima vez que queremos
empujar un elemento en la pila,

135
00:06:40,650 --> 00:06:43,087
que va a ser puesto en un lugar matriz 2.

136
00:06:43,087 --> 00:06:44,420
Y vamos a hacer eso una vez más.

137
00:06:44,420 --> 00:06:45,753
Nos empujamos 19 fuera de las pilas.

138
00:06:45,753 --> 00:06:48,940
Vamos a poner 19 en la localización matriz 2
y cambiar la parte superior de nuestra pila

139
00:06:48,940 --> 00:06:51,220
ser ubicación matriz 3
por lo que si la próxima vez que vayamos de

140
00:06:51,220 --> 00:06:54,780
que tenga que hacer un esfuerzo que estamos bien para ir.

141
00:06:54,780 --> 00:06:56,980
>> OK, así que eso es empujar en pocas palabras.

142
00:06:56,980 --> 00:06:57,830
¿Qué hay de estallar?

143
00:06:57,830 --> 00:07:00,240
Así que hace estallar es el tipo de
contrapartida a empujar.

144
00:07:00,240 --> 00:07:02,720
Es la forma en que nos quitamos los datos de la pila.

145
00:07:02,720 --> 00:07:04,610
Y en pop necesidades generales
a hacer lo siguiente.

146
00:07:04,610 --> 00:07:07,600
Se necesita aceptar un puntero a la
apilar, de nuevo en el caso general.

147
00:07:07,600 --> 00:07:10,480
En otro caso, usted puede ser
han declarado la pila a nivel mundial,

148
00:07:10,480 --> 00:07:13,910
en cuyo caso no es necesario para pasarlo
en porque ya tiene acceso a la misma

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

150
00:07:15,541 --> 00:07:17,040
Pero entonces ¿qué más tenemos que hacer?

151
00:07:17,040 --> 00:07:21,000
Bueno nos incrementando
la parte superior de la pila en empuje,

152
00:07:21,000 --> 00:07:24,050
así que estamos probablemente va a querer
para disminuir la parte 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
Y luego, por supuesto,
también vamos a querer

155
00:07:26,800 --> 00:07:29,240
para devolver el valor que eliminemos.

156
00:07:29,240 --> 00:07:32,125
Si estamos agregando elementos, queremos
para obtener elementos a cabo más adelante,

157
00:07:32,125 --> 00:07:34,000
es probable que en realidad
querer guardarlos así que

158
00:07:34,000 --> 00:07:36,490
no simplemente eliminarlos de la
apilar y luego no hacer nada con ellos.

159
00:07:36,490 --> 00:07:38,500
Generalmente si somos
empujando y haciendo estallar aquí

160
00:07:38,500 --> 00:07:41,250
queremos almacenar esta
la información de una manera significativa

161
00:07:41,250 --> 00:07:43,250
y por lo que no hace
sentido simplemente descartarlo.

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

163
00:07:46,380 --> 00:07:51,040
>> Así que esto es lo que una declaración de pop
podría parecer que hay en la parte superior izquierda.

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

165
00:07:53,870 --> 00:07:56,320
Una vez que hemos estado usando
enteros largo.

166
00:07:56,320 --> 00:08:01,916
Y acepta un puntero a una pila como
su único argumento o parámetro único.

167
00:08:01,916 --> 00:08:03,040
Entonces, ¿qué es el pop va a hacer?

168
00:08:03,040 --> 00:08:07,990
Digamos que queremos ahora
pop un elemento fuera de s.

169
00:08:07,990 --> 00:08:14,000
Entonces recuerdo que dije que las pilas están última
In, First Out, estructuras de datos LIFO.

170
00:08:14,000 --> 00:08:17,855
¿Qué elemento se va a
ser retirado de la pila?

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

172
00:08:21,780 --> 00:08:24,150
¿Sabía usted adivina 19?

173
00:08:24,150 --> 00:08:25,290
Porque estaríamos en lo cierto.

174
00:08:25,290 --> 00:08:28,836
19 fue el último elemento que agregamos a la
apilar cuando estábamos empujando elementos en,

175
00:08:28,836 --> 00:08:31,210
y por lo que va a la primera
elemento que consigue quitado.

176
00:08:31,210 --> 00:08:34,780
Es como si dijéramos 28, y
a continuación, ponemos 33 en la parte superior de la misma,

177
00:08:34,780 --> 00:08:36,659
y pusimos 19 por encima de eso.

178
00:08:36,659 --> 00:08:40,650
El único elemento que podemos sacar es 19.

179
00:08:40,650 --> 00:08:45,019
>> Ahora en el diagrama aquí lo que he hecho
es una especie de borrado 19 de la matriz.

180
00:08:45,019 --> 00:08:46,810
Eso no es realidad
lo que vamos a hacer.

181
00:08:46,810 --> 00:08:48,934
Sólo vamos a clase
de pretender que no está ahí.

182
00:08:48,934 --> 00:08:51,441
Es todavía allí en
esa ubicación de memoria,

183
00:08:51,441 --> 00:08:54,190
pero sólo vamos a ignorarlo
cambiando la parte superior de nuestra pila

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

185
00:08:56,080 --> 00:08:58,720
Así que si tuviéramos que ahora empujar
otro elemento en la pila,

186
00:08:58,720 --> 00:09:00,720
sería más de escribir 19.

187
00:09:00,720 --> 00:09:03,990
>> Pero no hay que pasar por la molestia
19 de eliminarlo de la pila.

188
00:09:03,990 --> 00:09:05,830
Sólo podemos pretender que no está ahí.

189
00:09:05,830 --> 00:09:11,107
A los efectos de la pila que se ha ido si
cambiamos la parte superior para ser 2 en lugar de 3.

190
00:09:11,107 --> 00:09:12,690
Muy bien, así que eso fue más o menos la misma.

191
00:09:12,690 --> 00:09:15,080
Eso es todo lo que necesitamos hacer
para que aparezca un elemento fuera.

192
00:09:15,080 --> 00:09:16,090
Hagámoslo de nuevo.

193
00:09:16,090 --> 00:09:18,610
Así que he destacado en rojo para
indicamos que estamos haciendo otra llamada.

194
00:09:18,610 --> 00:09:19,720
Vamos a hacer lo mismo.

195
00:09:19,720 --> 00:09:20,803
>> Entonces, ¿qué va a pasar?

196
00:09:20,803 --> 00:09:23,670
Bueno, vamos a almacenar
33 en x y vamos

197
00:09:23,670 --> 00:09:26,217
para cambiar la parte superior de la pila a 1.

198
00:09:26,217 --> 00:09:29,050
Así que si fuéramos ahora para empujar un
elemento en la pila que estamos

199
00:09:29,050 --> 00:09:31,610
vamos a hacer en este momento,
Qué va a pasar

200
00:09:31,610 --> 00:09:36,367
Somos nosotros vamos sobrescritura
ubicación matriz número 1.

201
00:09:36,367 --> 00:09:38,950
Así que el 33 que fue una especie de izquierda
detrás que acabamos fingimos

202
00:09:38,950 --> 00:09:44,390
¿no hay más, sólo estamos yendo
para darle una paliza y poner 40 en su lugar.

203
00:09:44,390 --> 00:09:46,290
Y luego, por supuesto,
desde que hicimos un empujón,

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

205
00:09:48,780 --> 00:09:50,950
de modo que si ahora añadimos
otro elemento que va a

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

207
00:09:54,700 --> 00:09:57,590
>> Ahora listas enlazadas son otra
manera de implementar las pilas.

208
00:09:57,590 --> 00:10:01,210
Y si esta definición en el
pantalla de aquí parece familiar a usted,

209
00:10:01,210 --> 00:10:04,260
es porque se ve casi
exactamente de la misma, de hecho,

210
00:10:04,260 --> 00:10:07,790
que prácticamente es exactamente el
mismo que una lista enlazada,

211
00:10:07,790 --> 00:10:11,990
si usted recuerda de nuestra discusión de
simplemente enlazada listas en otro vídeo.

212
00:10:11,990 --> 00:10:15,510
La única restricción aquí
es para nosotros como programadores,

213
00:10:15,510 --> 00:10:17,900
que no se nos permite
insertar o eliminar azar

214
00:10:17,900 --> 00:10:20,620
de la lista simplemente enlazada
que podríamos hacer con anterioridad.

215
00:10:20,620 --> 00:10:25,820
Podemos sólo ahora insertar y eliminar de
el frente o la parte superior del vinculados

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

217
00:10:26,320 --> 00:10:28,028
Eso es realmente la única
diferencia sin embargo.

218
00:10:28,028 --> 00:10:29,700
Esto es lo contrario de una lista enlazada.

219
00:10:29,700 --> 00:10:32,060
No es más que la restricción
reemplazando en nosotros mismos

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

221
00:10:35,770 --> 00:10:39,280
>> La regla aquí es mantener siempre una
puntero a la cabeza de una lista enlazada.

222
00:10:39,280 --> 00:10:41,520
Esto es por supuesto un general
regla importante primero.

223
00:10:41,520 --> 00:10:44,260
Por separado lista enlazada de todos modos
Sólo es necesario un puntero a la cabeza

224
00:10:44,260 --> 00:10:46,160
con el fin de tener esa
cadena de poder referirse

225
00:10:46,160 --> 00:10:48,596
para todos los demás elementos
en la lista enlazada.

226
00:10:48,596 --> 00:10:50,470
Pero es sobre todo
importante con una pila.

227
00:10:50,470 --> 00:10:52,386
Y así, en general, usted es
va a realmente quiere

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

229
00:10:54,090 --> 00:10:56,574
Probablemente va a
será aún más fácil de esa manera.

230
00:10:56,574 --> 00:10:58,240
¿Cuáles son los análogos de empuje y el pop?

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

232
00:10:58,740 --> 00:11:01,812
Así empujando de nuevo es la adición de
un nuevo elemento a la pila.

233
00:11:01,812 --> 00:11:03,770
En una lista enlazada que
significa que vamos a tener

234
00:11:03,770 --> 00:11:07,770
para crear un nuevo nodo que estamos
va a añadir a la lista enlazada,

235
00:11:07,770 --> 00:11:10,500
y luego siga los pasos cuidadosos
que hemos esbozado anteriormente

236
00:11:10,500 --> 00:11:16,050
en las listas ligadas sencillas para añadirlo a
la cadena sin romper la cadena

237
00:11:16,050 --> 00:11:18,900
y perder o huérfanos cualquier
elementos de la lista enlazada.

238
00:11:18,900 --> 00:11:21,820
Y eso es básicamente lo que
pequeña burbuja de texto allí resume.

239
00:11:21,820 --> 00:11:23,740
Y vamos a echar un vistazo
en él como un diagrama.

240
00:11:23,740 --> 00:11:24,823
>> Así que aquí está nuestra lista enlazada.

241
00:11:24,823 --> 00:11:26,620
Es al mismo tiempo contiene cuatro elementos.

242
00:11:26,620 --> 00:11:30,420
Y más perfectamente aquí está nuestra
apilar contiene cuatro elementos.

243
00:11:30,420 --> 00:11:36,030
Y digamos que ahora queremos
impulsar un nuevo elemento en esta pila.

244
00:11:36,030 --> 00:11:39,792
Y queremos impulsar una nueva
elemento cuyo valor es 12.

245
00:11:39,792 --> 00:11:41,000
Bueno, ¿qué vamos a hacer?

246
00:11:41,000 --> 00:11:43,420
Bueno primero que vamos a
espacio malloc, dinámicamente

247
00:11:43,420 --> 00:11:45,411
asignar espacio para un nuevo nodo.

248
00:11:45,411 --> 00:11:48,160
Y, por supuesto, inmediatamente después
hacemos una llamada a malloc siempre

249
00:11:48,160 --> 00:11:52,989
asegúrese de comprobar nula,
porque si llegamos nula vuelta

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

251
00:11:54,280 --> 00:11:57,570
No queremos eliminar la referencia que nula
puntero o que van a sufrir un fallo seg.

252
00:11:57,570 --> 00:11:58,510
Eso no es bueno.

253
00:11:58,510 --> 00:11:59,760
Para ello hemos malloced del nodo.

254
00:11:59,760 --> 00:12:01,260
Vamos a suponer que hemos tenido éxito aquí.

255
00:12:01,260 --> 00:12:06,090
Vamos a poner 12 en
el campo de datos de dicho nodo.

256
00:12:06,090 --> 00:12:11,570
Ahora Qué recuerdas cuál de nuestros punteros
Mueve siguiente, así que no rompemos la cadena?

257
00:12:11,570 --> 00:12:15,100
Tenemos un par de opciones aquí, pero
el único que va a estar a salvo

258
00:12:15,100 --> 00:12:19,330
es establecer noticias próximo puntero a
punto a la vieja cabeza de lista

259
00:12:19,330 --> 00:12:21,360
o lo que pronto será el
antiguo jefe de la lista.

260
00:12:21,360 --> 00:12:23,610
Y ahora que todo nuestro
elementos están encadenados juntos,

261
00:12:23,610 --> 00:12:27,370
sólo podemos mover la lista de señalar
al mismo lugar que el nuevo hace.

262
00:12:27,370 --> 00:12:33,550
Y ahora hemos llevado efectivamente una
nuevo elemento en la parte frontal de la pila.

263
00:12:33,550 --> 00:12:36,420
>> Para aparecer sólo queremos
borrar ese primer elemento.

264
00:12:36,420 --> 00:12:38,150
Y así que básicamente lo que
tenemos que hacer aquí,

265
00:12:38,150 --> 00:12:40,050
así que tenemos que encontrar el segundo elemento.

266
00:12:40,050 --> 00:12:43,540
Con el tiempo que se convertirá en el nuevo
cabeza después borramos la primera.

267
00:12:43,540 --> 00:12:47,300
Así que sólo tenemos que empezar desde
Al principio, mover un avance.

268
00:12:47,300 --> 00:12:50,340
Una vez que tenemos una bodega en un
adelante de donde estamos actualmente

269
00:12:50,340 --> 00:12:53,850
somos podemos eliminar la primera de ellas con seguridad
y luego nos podemos mover la cabeza

270
00:12:53,850 --> 00:12:57,150
para apuntar a lo que fue el
segundo mandato y entonces ahora

271
00:12:57,150 --> 00:12:59,170
es el primero después de eso
nodo ha sido eliminado.

272
00:12:59,170 --> 00:13:01,160
>> Así que de nuevo, echando un vistazo
en él como un diagrama que

273
00:13:01,160 --> 00:13:05,022
quieren ahora un pop
elemento fuera de esta pila.

274
00:13:05,022 --> 00:13:05,730
¿Asi que que hacemos?

275
00:13:05,730 --> 00:13:08,188
Bueno estamos primero va a crear
un nuevo puntero que está pasando

276
00:13:08,188 --> 00:13:10,940
para señalar el mismo lugar que la cabeza.

277
00:13:10,940 --> 00:13:13,790
Vamos a moverlo una posición
hacia delante diciendo iguales trav

278
00:13:13,790 --> 00:13:17,510
trav próximo por ejemplo, que
avanzaría el puntero trav un solo

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

280
00:13:19,324 --> 00:13:21,240
Ahora que tenemos un
mantenerse en el primer elemento

281
00:13:21,240 --> 00:13:24,573
a través de la lista de punteros llamado, y la
segundo elemento a través de un puntero llamado

282
00:13:24,573 --> 00:13:28,692
trav, podemos eliminar con seguridad que
primer elemento de la pila

283
00:13:28,692 --> 00:13:30,650
sin perder el resto
de la cadena porque

284
00:13:30,650 --> 00:13:32,358
tener una manera de referirse
al segundo elemento

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

286
00:13:34,780 --> 00:13:37,100
>> Así que ahora podemos liberar a ese nodo.

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

288
00:13:38,404 --> 00:13:41,320
Y entonces todo lo que necesitamos hacer ahora es
mover la lista a punto al mismo lugar

289
00:13:41,320 --> 00:13:44,482
que trav hace, y estamos especie de vuelta
donde empezamos antes empujamos 12

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

291
00:13:45,690 --> 00:13:46,940
Esto es exactamente donde estábamos.

292
00:13:46,940 --> 00:13:48,840
Hemos tenido este cuatro elementos de la pila.

293
00:13:48,840 --> 00:13:49,690
Hemos añadido un quinto.

294
00:13:49,690 --> 00:13:51,910
Empujamos un quinto
elemento, y luego nos

295
00:13:51,910 --> 00:13:55,980
aparecido recientemente que la mayoría
elemento añadido de marcha atrás.

296
00:13:55,980 --> 00:13:58,816
>> Eso es realmente más o menos
todo lo que hay a pilas.

297
00:13:58,816 --> 00:14:00,190
Se puede implementar como matrices.

298
00:14:00,190 --> 00:14:01,815
Se puede implementar como listas enlazadas.

299
00:14:01,815 --> 00:14:04,810
Hay, por supuesto, otra
formas de ponerlas en práctica también.

300
00:14:04,810 --> 00:14:09,060
Básicamente, la razón por la que usaríamos
pilas es mantener los datos de tal manera

301
00:14:09,060 --> 00:14:12,090
que el más recientemente añadido
elemento es el primero que estamos

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

303
00:14:14,980 --> 00:14:17,900
Soy Doug Lloyd, esto es CS50.

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