Quiero advertir que si alguien estuvo en la UDB habrán visto estos materiales pues si para aquellos que me odiaron profundamente o me apreciaron en Progra 3 y 4 “I say you Hi…. =)” son mis materiales de clases….whatever no mas palabras y la acción yo pienso estructurar la info. Así:
1- Comenzar escribiendo algunos conceptos básicos.
2- Mostrar una explicación en forma grafica.
3- Y posteriormente ejemplos de aplicación de los TAD PILA.
Obviamente esto no sera algo que este listo ya hoy...no!, sera poco a poco y obvio los comentarios son bienvenidos aunque no creo que estos cambien mi forma de pensar =) pero sientanse libres de liberar sus emociones..... ¬¬
***********************+++++++++++++++++++++++++++++++++++****************++
PILAS
Una pila es una lista ordenada de elementos en la que todas las inserciones y supresiones se realizan por un mismo extremo de la lista. A una pila se le pueden añadir y retirar nuevos nodos únicamente de su parte superior. Por esta razón, se conoce una pila como una estructura de datos LIFO por last-in, first-out, es decir último en entrar primero en salir.
Se referencia una pila mediante un apuntador al elemento superior de la misma. El miembro de enlace en el último nodo de la pila se define a NULL, para indicar que se trata de la parte inferior de la pila misma. Vea una representación gráfica de la PILA:
Note que las pilas y las listas enlazadas se representan en forma idéntica. La diferencia entre las pilas y las listas enlazadas es que en una lista enlazada las inserciones y borrados pueden ocurrir en cualquier parte, pero en una pila únicamente en su parte superior.
Las funciones primarias utilizadas para manipular una pila son push y pop. La función push crea un nuevo nodo y lo coloca en la parte superior de la pila (tope). La función pop sirve ya sea para leer o elimina un nodo de la parte superior de la pila, liberando la memoria que fue asignada al nodo retirado, y regresando el valor retirado.
Las pilas pueden implementarse con arrays pero este debe ser lo suficientemente amplio para poder contener el máximo previsto de elementos de la pila. Un extremo del array se considera el fondo de la pila, que permanecerá fijo. La implementación dinámica de una pila se hace almacenando los elementos como nodos de una lista enlazada, con la particularidad de que siempre que se quiera meter (empujar) un elemento se hará por el mismo extremo que se extraerá. Esta realización tiene la ventaja de que el tamaño se ajusta exactamente a los elementos de la pila. Sin embargo, para cada elemento es necesaria más memoria, ya que hay que guardar el campo de enlace.
Antes de analizar el código quiero advertir que en algunos casos las imagenes tienen un literal en color rojo entre parentesis o un literal encerrado en cuadrito en rojo, seguido de la imagen que contenga estos literales esta la explicación o el significado de la línea de código junto a la cual esta el literal. Es decir vean la imagen y luego la explicación para que sepan que hace cada línea de código , obviamente el programa tiene comentarios pero para entrar mas en detalle he querido colocar una explicación extra. A continuación analizaremos el código en c++ que permite implementar una pila:
Representación gráfica
La clase nodo contiene el código que permitirá crear cada nodo para implementar la pila. Cada nodo tendrá un valor (dato que se almacena dentro del nodo en la pila) y un puntero apuntando al siguiente nodo o elemento de la pila. Graficamente podriamos decir que esta clase genera una serie de cajitas que se iran uniendo unas a otras para formar la pila, estas cajitas podrian ser algo como lo siguiente:
.png)
La clase Pila encierra el código de la Pila este código permitirá crear la pila dentro de la cual se colocara cada nodo. Esta clase es la base de la pila gracias a ella sabemos donde comienza la pila y donde acaba y solamente genera un puntero que apuntará a la primera cajita de la pila si no crearamos esta clase no sabriamos donde comienza la pila. Recuerden que estamos trabajando con memoria dinamica lo que implica el necesario uso de los lindos PUNTEROS que son los responsables de decirme cual es la ubicacion de mis elementos dentro de la memoria, una memoria que no puedo controlar igual que controlo un vector, arreglo o array. Es igual pero en el vector yo digo posición 0,1,2,...n y en la memoria dinamica se asigna dinamicamente y no exactamente si mis elementos estan en la ubicación de memoria FFX001, etc. Por esto necesito saber donde comienza mi pila y luego me voy desplazando por cada nodo de la pila gracias al puntero que cada nodo tiene.
**Bueno algo enrredadito ¿no? =( al principio suena bien macabro pero despues se entiende bien esta
vaina es cuestion de practica =). Pero animo que estamos al principio conforma avancemos se facilita la
cosa. Y a medida que lo entiendan se van a sentir bien poderosos....**
...En fin graficamente la clase pila genera algo como lo siguiente:
.png)
ANALISIS DE FUNCION CONSTRUCTOR
.png)
.png)
1- El constructor inicializa el fondo de la pila, poniendo a ultimo (puntero de la pila) apuntado a NULL. Ahora ya esta creada la pila.
ANALISIS DE FUNCION PUSH (INSERTAR NUEVO NODO A LA PILA EN EL TOPE)
.png)
( A continuación se muestra la representación grafica de este segmento de código ubique el (1) y el (2) en la imagen para que sepan la presentación de estas lineas de codigo y en la respectiva explicación el significado de las mismas. )
Representación gráfica .png)
(1) Para las pilas solo se pueden insertar elementos al tope, por lo tanto lo único que hacemos es crear el nuevo nodo pasando como parámetro el valor que guardar y pasándole el valor al que apunta en ese momento ultimo, como ultimo antes de agregar el nodo apunta a NULL entonces siguiente apuntara a NULL.
(2) Le indicamos a ultimo (puntero de la pila) que apunte al nodo que se acaba de agregar.
Bueno por hoy es todo .......continuara....
