Programación Orientada a Objetos

Profesor: Ángel Roldán
Profesor: Ángel Roldán
Cursos Relacionados

Cursos de Java

Pilas en Java

La 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:


El mecanismo que sigue el método primero es similar al visto en el pop, aunque se elimina la cima, únicamente se devuelve su valor:

Compartir

Sección de Interés

ÁREA LINUX