DOUG LLOYD: Muy bien, así que en este punto estás
probablemente bastante familiarizado con matrices y listas enlazadas
que es el de dos primaria estructuras de datos que hemos
hablado de mantener conjuntos de datos de tipos de datos similares organizada.
>> Ahora vamos a hablar alrededor de un par de variaciones
en matrices y listas enlazadas.
En este video vamos para hablar de las pilas.
En concreto vamos a hablar sobre una estructura de datos llamada una pila.
Recuerde que en los debates anteriores acerca de los punteros y memoria,
que la pila es también el nombrar para un segmento de la memoria
donde declara estáticamente memoria memory-- que
nombre, variables que usted nombre, et marcos cetera y función que también
existen marcos de pila de llamadas.
Así que esta es una estructura de datos de la pila no es un segmento de pila de la memoria.
OK.
>> Pero, ¿qué es una pila?
Así que es prácticamente sólo una tipo especial de estructura
que mantiene los datos de una manera organizada.
Y hay dos muy formas comunes de implementar
pilas utilizando dos estructuras de datos que ya estamos familiarizados,
matrices y listas enlazadas.
¿Qué hace un especial de pila es el manera en que ponemos la información
en la pila, y la forma en que eliminar la información de la pila.
En particular con las pilas la regla es sólo el más
recientemente elemento añadido se puede quitar.
>> Así que pensar en ello como si fuera una pila.
Estamos acumulando información en la parte superior de la misma,
y sólo la cosa en la parte superior de la pila se puede quitar.
No podemos quitar la cosa debajo porque todo lo demás lo haría
colapsar y caer.
Así que realmente estamos construyendo una pila que entonces tenemos que eliminar pieza por pieza.
Debido a esto nos referimos comúnmente a una pila como una estructura LIFO,
último en entrar primero en salir.
LIFO, último en entrar, primero en salir.
>> Así que debido a esta restricción en cómo la información puede ser añadido a
y retirado de una pila, no hay realmente sólo dos cosas que pueden hacer con una pila.
Podemos empujar, que es el término que usamos para añadir
un nuevo elemento a la parte superior de la pila, o si la pila no existe
y estamos creando desde cero, la creación de la pila en el primer lugar
sería empujar.
Y a continuación, el pop, que es el tipo de CS término que usamos para quitar el más reciente
elemento añadido desde la parte superior de la pila.
>> Así que vamos a mirar a ambos implementaciones, basado tanto array
y lista enlazada con base.
Y vamos a comenzar con matriz basada.
Así que aquí está la idea básica de lo que la estructura de datos basada en pila de conjuntos
se vería así.
Tenemos una definición mecanografiada aquí.
En el interior de la que tenemos dos miembros o campos de la estructura.
Tenemos una matriz.
Y otra vez estoy usando el valor de tipo de datos arbitrarios.
>> Así que este podría ser cualquier tipo de datos, int carbón o algún otro dato
escribe que ha creado anteriormente.
Así que tenemos una gran variedad de capacidad de tamaño.
Capacidad de ser una libra define constante, tal vez en otro lugar en nuestro archivo.
Así que ya cuenta con este particular aplicación estamos delimitador
nosotros mismos como era normalmente en el caso de arrays,
que no podemos cambiar el tamaño de forma dinámica, donde hay un cierto número
de elementos máxima que podemos poner en nuestra pila.
En este caso se trata de elementos de capacidad.
>> También mantenemos un registro de la parte superior de la pila.
¿Qué elemento es el más en fecha reciente a la pila?
Y así hacemos un seguimiento de que en una variable llamada superior.
Y todo esto se envuelve juntos en un nuevo tipo de datos llamado una pila.
Y una vez que fuimos creados este nuevo tipo de datos
podemos tratarlo como cualquier otro tipo de datos.
Podemos declarar pila s, al igual que podríamos hacer int x, o de carbón y.
Y cuando decimos apilamos s, así lo que sucede
está obtenemos un conjunto de de memoria reservado para nosotros.
>> En este caso, la capacidad Al parecer, he decidido
es 10 porque tengo un única variable de tipo pila
que contiene dos campos recuerdan.
Una matriz, en este caso va ser una matriz de enteros
como es el caso en la mayoría de mis ejemplos.
Y otra variable entera capaz de almacenar la parte superior,
más recientemente añadido elemento a la pila.
Así que una sola pila de lo que sólo se parece a esta definido.
Es una caja que contiene una serie de 10 lo
serán números enteros en este caso, y otra variable entera allí en verde
para indicar la parte superior de la pila.
>> Para establecer la parte superior de la pila sólo decimos s.top.
Esa es la forma en que accedemos a una campo de una estructura de retiro.
s.top es igual a 0 eficazmente Hace esto a nuestra pila.
Así que de nuevo tenemos dos operaciones que podemos llevar a cabo ahora.
Podemos empujar y podemos pop.
Vamos a empezar con empuje.
Una vez más, empujando es la adición de un nuevo elemento a la parte superior de la pila.
>> Entonces, ¿qué hacemos lo que necesitamos hacer en esta matriz de implementación basada?
Bueno en general la función de empuje se va
a tener que aceptar una puntero a la pila.
Ahora tómate un segundo y pensar en ello.
¿Por qué querríamos aceptar un puntero a la pila?
Recuerde que en los videos anteriores sobre alcance y punteros variables,
¿qué pasaría si nos enviamos pila, s en lugar de como un parámetro?
Lo que en realidad se pasó ahí?
Recuerde que estamos creando una copia cuando se pasa a una función
a menos que utilicemos punteros.
Y así esta función empujar necesidades para aceptar un puntero a la pila
por lo que en realidad estamos cambiando la pila tenemos la intención de cambiar.
>> La otra cosa empuje probablemente quiere aceptar es un elemento de datos de valor de tipo.
En este caso, de nuevo, un número entero que vamos a añadir a la parte superior de la pila.
Así que tenemos nuestros dos parámetros.
¿Qué vamos a ahora hacer dentro de empuje?
Bueno, simplemente, sólo vamos a añadir ese elemento a la parte superior de la pila
y luego cambiar en la parte superior de la pila es, que s dot valor superior.
Así que esto es lo que una función declaración de empuje
podría parecer en un basada en arreglos de implementación.
>> De nuevo, esto no es una regla dura y rápida que podría cambiar esto y tener
que varían en diferentes maneras.
Tal vez s se declara globalmente.
Y por lo que ni siquiera es necesario pasar es como un parámetro.
Esto es de nuevo sólo una caso general para empujar.
Y hay diferentes maneras de ponerlo en práctica.
Pero en este caso nuestra empuje va a tomar
dos argumentos, un puntero a una pila y un elemento de datos de valor de tipo, número entero
en este caso.
>> Así que declaramos s, nos dijo s.top es igual a 0.
Ahora vamos a empujar el el número 28 en la pila.
Bueno, ¿qué quiere decir eso?
Bueno actualmente la parte superior de la pila es 0.
Y así, lo que es, básicamente, va a pasar es
vamos a pegar el número 28 en la ubicación array 0.
Bastante sencillo, correcto, que era la parte superior y ahora somos buenos para ir.
Y entonces tenemos que cambiar lo que la parte superior de la pila será.
Así que la próxima vez empujamos un elemento,
vamos a guardarlo en ubicación array, probablemente no 0.
No queremos sobrescribir lo que acabamos de poner allí.
Y así sólo tendremos que mover la parte superior a 1.
Eso probablemente tiene sentido.
>> Ahora bien, si queremos poner otro elemento en la pila, decimos que queremos empujar 33,
Bueno, ahora sólo vamos a tomar 33 y lo puso en el número de ubicación de matriz
1, y después cambiar la parte superior de nuestra apilar ser ubicación matriz número dos.
Así que si la próxima vez que queremos empujar un elemento en la pila,
que va a ser puesto en un lugar matriz 2.
Y vamos a hacer eso una vez más.
Nos empujamos 19 fuera de las pilas.
Vamos a poner 19 en la localización matriz 2 y cambiar la parte superior de nuestra pila
ser ubicación matriz 3 por lo que si la próxima vez que vayamos de
que tenga que hacer un esfuerzo que estamos bien para ir.
>> OK, así que eso es empujar en pocas palabras.
¿Qué hay de estallar?
Así que hace estallar es el tipo de contrapartida a empujar.
Es la forma en que nos quitamos los datos de la pila.
Y en pop necesidades generales a hacer lo siguiente.
Se necesita aceptar un puntero a la apilar, de nuevo en el caso general.
En otro caso, usted puede ser han declarado la pila a nivel mundial,
en cuyo caso no es necesario para pasarlo en porque ya tiene acceso a la misma
como una variable global.
Pero entonces ¿qué más tenemos que hacer?
Bueno nos incrementando la parte superior de la pila en empuje,
así que estamos probablemente va a querer para disminuir la parte superior de la pila
en el pop, ¿no?
Y luego, por supuesto, también vamos a querer
para devolver el valor que eliminemos.
Si estamos agregando elementos, queremos para obtener elementos a cabo más adelante,
es probable que en realidad querer guardarlos así que
no simplemente eliminarlos de la apilar y luego no hacer nada con ellos.
Generalmente si somos empujando y haciendo estallar aquí
queremos almacenar esta la información de una manera significativa
y por lo que no hace sentido simplemente descartarlo.
Así que esta función debe probablemente devolver un valor para nosotros.
>> Así que esto es lo que una declaración de pop podría parecer que hay en la parte superior izquierda.
Esta función devuelve los datos de valor de tipo.
Una vez que hemos estado usando enteros largo.
Y acepta un puntero a una pila como su único argumento o parámetro único.
Entonces, ¿qué es el pop va a hacer?
Digamos que queremos ahora pop un elemento fuera de s.
Entonces recuerdo que dije que las pilas están última In, First Out, estructuras de datos LIFO.
¿Qué elemento se va a ser retirado de la pila?
¿Sabía usted adivina 19?
Porque estaríamos en lo cierto.
19 fue el último elemento que agregamos a la apilar cuando estábamos empujando elementos en,
y por lo que va a la primera elemento que consigue quitado.
Es como si dijéramos 28, y a continuación, ponemos 33 en la parte superior de la misma,
y pusimos 19 por encima de eso.
El único elemento que podemos sacar es 19.
>> Ahora en el diagrama aquí lo que he hecho es una especie de borrado 19 de la matriz.
Eso no es realidad lo que vamos a hacer.
Sólo vamos a clase de pretender que no está ahí.
Es todavía allí en esa ubicación de memoria,
pero sólo vamos a ignorarlo cambiando la parte superior de nuestra pila
de ser 3 a 2.
Así que si tuviéramos que ahora empujar otro elemento en la pila,
sería más de escribir 19.
>> Pero no hay que pasar por la molestia 19 de eliminarlo de la pila.
Sólo podemos pretender que no está ahí.
A los efectos de la pila que se ha ido si cambiamos la parte superior para ser 2 en lugar de 3.
Muy bien, así que eso fue más o menos la misma.
Eso es todo lo que necesitamos hacer para que aparezca un elemento fuera.
Hagámoslo de nuevo.
Así que he destacado en rojo para indicamos que estamos haciendo otra llamada.
Vamos a hacer lo mismo.
>> Entonces, ¿qué va a pasar?
Bueno, vamos a almacenar 33 en x y vamos
para cambiar la parte superior de la pila a 1.
Así que si fuéramos ahora para empujar un elemento en la pila que estamos
vamos a hacer en este momento, Qué va a pasar
Somos nosotros vamos sobrescritura ubicación matriz número 1.
Así que el 33 que fue una especie de izquierda detrás que acabamos fingimos
¿no hay más, sólo estamos yendo para darle una paliza y poner 40 en su lugar.
Y luego, por supuesto, desde que hicimos un empujón,
vamos a incrementar el superior de la pila 1-2
de modo que si ahora añadimos otro elemento que va a
ir a la ubicación matriz número dos.
>> Ahora listas enlazadas son otra manera de implementar las pilas.
Y si esta definición en el pantalla de aquí parece familiar a usted,
es porque se ve casi exactamente de la misma, de hecho,
que prácticamente es exactamente el mismo que una lista enlazada,
si usted recuerda de nuestra discusión de simplemente enlazada listas en otro vídeo.
La única restricción aquí es para nosotros como programadores,
que no se nos permite insertar o eliminar azar
de la lista simplemente enlazada que podríamos hacer con anterioridad.
Podemos sólo ahora insertar y eliminar de el frente o la parte superior del vinculados
lista.
Eso es realmente la única diferencia sin embargo.
Esto es lo contrario de una lista enlazada.
No es más que la restricción reemplazando en nosotros mismos
como programadores que cambia en una pila.
>> La regla aquí es mantener siempre una puntero a la cabeza de una lista enlazada.
Esto es por supuesto un general regla importante primero.
Por separado lista enlazada de todos modos Sólo es necesario un puntero a la cabeza
con el fin de tener esa cadena de poder referirse
para todos los demás elementos en la lista enlazada.
Pero es sobre todo importante con una pila.
Y así, en general, usted es va a realmente quiere
este puntero a una variable global.
Probablemente va a será aún más fácil de esa manera.
¿Cuáles son los análogos de empuje y el pop?
Correcto.
Así empujando de nuevo es la adición de un nuevo elemento a la pila.
En una lista enlazada que significa que vamos a tener
para crear un nuevo nodo que estamos va a añadir a la lista enlazada,
y luego siga los pasos cuidadosos que hemos esbozado anteriormente
en las listas ligadas sencillas para añadirlo a la cadena sin romper la cadena
y perder o huérfanos cualquier elementos de la lista enlazada.
Y eso es básicamente lo que pequeña burbuja de texto allí resume.
Y vamos a echar un vistazo en él como un diagrama.
>> Así que aquí está nuestra lista enlazada.
Es al mismo tiempo contiene cuatro elementos.
Y más perfectamente aquí está nuestra apilar contiene cuatro elementos.
Y digamos que ahora queremos impulsar un nuevo elemento en esta pila.
Y queremos impulsar una nueva elemento cuyo valor es 12.
Bueno, ¿qué vamos a hacer?
Bueno primero que vamos a espacio malloc, dinámicamente
asignar espacio para un nuevo nodo.
Y, por supuesto, inmediatamente después hacemos una llamada a malloc siempre
asegúrese de comprobar nula, porque si llegamos nula vuelta
había algún tipo de problema.
No queremos eliminar la referencia que nula puntero o que van a sufrir un fallo seg.
Eso no es bueno.
Para ello hemos malloced del nodo.
Vamos a suponer que hemos tenido éxito aquí.
Vamos a poner 12 en el campo de datos de dicho nodo.
Ahora Qué recuerdas cuál de nuestros punteros Mueve siguiente, así que no rompemos la cadena?
Tenemos un par de opciones aquí, pero el único que va a estar a salvo
es establecer noticias próximo puntero a punto a la vieja cabeza de lista
o lo que pronto será el antiguo jefe de la lista.
Y ahora que todo nuestro elementos están encadenados juntos,
sólo podemos mover la lista de señalar al mismo lugar que el nuevo hace.
Y ahora hemos llevado efectivamente una nuevo elemento en la parte frontal de la pila.
>> Para aparecer sólo queremos borrar ese primer elemento.
Y así que básicamente lo que tenemos que hacer aquí,
así que tenemos que encontrar el segundo elemento.
Con el tiempo que se convertirá en el nuevo cabeza después borramos la primera.
Así que sólo tenemos que empezar desde Al principio, mover un avance.
Una vez que tenemos una bodega en un adelante de donde estamos actualmente
somos podemos eliminar la primera de ellas con seguridad y luego nos podemos mover la cabeza
para apuntar a lo que fue el segundo mandato y entonces ahora
es el primero después de eso nodo ha sido eliminado.
>> Así que de nuevo, echando un vistazo en él como un diagrama que
quieren ahora un pop elemento fuera de esta pila.
¿Asi que que hacemos?
Bueno estamos primero va a crear un nuevo puntero que está pasando
para señalar el mismo lugar que la cabeza.
Vamos a moverlo una posición hacia delante diciendo iguales trav
trav próximo por ejemplo, que avanzaría el puntero trav un solo
posición adelantada.
Ahora que tenemos un mantenerse en el primer elemento
a través de la lista de punteros llamado, y la segundo elemento a través de un puntero llamado
trav, podemos eliminar con seguridad que primer elemento de la pila
sin perder el resto de la cadena porque
tener una manera de referirse al segundo elemento
reenviar a través de la puntero llamado trav.
>> Así que ahora podemos liberar a ese nodo.
Podemos liberar lista.
Y entonces todo lo que necesitamos hacer ahora es mover la lista a punto al mismo lugar
que trav hace, y estamos especie de vuelta donde empezamos antes empujamos 12
en en el primer lugar, a la derecha.
Esto es exactamente donde estábamos.
Hemos tenido este cuatro elementos de la pila.
Hemos añadido un quinto.
Empujamos un quinto elemento, y luego nos
aparecido recientemente que la mayoría elemento añadido de marcha atrás.
>> Eso es realmente más o menos todo lo que hay a pilas.
Se puede implementar como matrices.
Se puede implementar como listas enlazadas.
Hay, por supuesto, otra formas de ponerlas en práctica también.
Básicamente, la razón por la que usaríamos pilas es mantener los datos de tal manera
que el más recientemente añadido elemento es el primero que estamos
va a querer volver.
Soy Doug Lloyd, esto es CS50.