OpcionesLa pila es una secuencia de elementos del mismo tipo en la que el acceso a la misma se realiza por un único lugar denominado cima:
Vemos como el acceso a los elementos de la pila se realiza siempre sobre un único extremo. Las operaciones que caracterizan la pila son las de introducir un nuevo elemento sobre la cima (push) y la de extraer el
elemento situado en la cima (pop). Una forma de ver esta estructura de datos es como una pila de libros en la que sólo se puede coger el libro que está en la cima o apilar más libros sobre la misma, pero los
libros que sostienen la pila no son accesibles pues de otro modo todo se desmoronaría.
El interfaz en Java que define esta clase de objetos y sus métodos son los siguientes:
Pila.java
Veremos ahora dos implementaciones de pila, mediante arrays y listas enlazadas.
Implementación de pilas mediante arrays
Implementemos una Pila mediante un vector
PilaArray.java
La dimensión de la pila se establece al crear la pila, mediante el constructor. En el siguiente ejemplo creamos una pila con capacidad para 125 elementos
PilaArray pila_de_ejemplo = new PilaArray(125);
Si hubieramos usado el constructor por defecto se hubiera establecido el tamaño de la pila en 1000 elementos.
Definimos un campo privado top para conocer en todo momento cuál es la cima de la pila. De esta forma, si queremos añadir un nuevo elemento a la pila (push) lo haremos en la posición siguiente a la que nos indica
este campo. Observe como sólo se inserta un nuevo elemento sobre la cima cuando hay espacio suficiente, es decir la longitud de la pila es menor que su capacidad. Primero se incrementa el valor del campo top y después se inserta
el elemento en la pila .
Para implementar las operaciones pop y primero se comprueba que la lista no es vacía, en cuyo caso se devuelve un valor nulo (null). Para el caso de pop se decrementa la variable
top para eliminar el objeto de la cima, mientras que para primero no, puesto que en este último sólo se está consultando la cima.
Implementación de pilas mediante listas enlazadas
Utilizaremos ahora la clase Nodo definida anteriormente para ver esta otra implementación a la que llamaremos PilaEnlazada. Los campos que definiremos para esta clase son top, que almacena el nodo que está en la
cima de la pila y la longitud de la misma.
PilaEnlazada.java
A continuación vemos como se insertan los nodos por la cima de la pila. Para ello se crea un nuevo nodo y se le asigna como siguiente nodo la antigua cima de la pila. El siguiente paso es actualizar la cima de la pila con el
nuevo nodo creado.
El funcionamiento del pop es el siguiente. Si la lista es vacía devuelve un valor nulo. En caso contrario actualiza la cima al siguiente elemento por debajo del nodo situado en la cima y devuelve el valor del nodo cima:
