Pilas y Colas en Java Estructura de Datos PDF

Preview

Summary

Este documento ayuda para entender un concepto básico de la programación y la estructura de datos, cuando se necesita recurrir a listas y colas...

Description

16th November 2015

Pilas y Colas en 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. De aqui que decimos que una lista se comporta como una pila, ya que las inserciones y las extracciones solo pueden hacerse desde la parte superior de la pila. Esto se conoce también como LIFO (Last In First Out).

Las pilas son muy útiles en varios escenarios de programación. Dos de los más comunes son:

Pilas que contienen direcciones de retorno: Cuando el código llama a un método, la dirección de la primera instrucción que sigue a la llamada se inserta en la parte superior de la pila de llamadas de métodos del thread actual. Cuando el método llamado ejecuta la instrucción return, se saca la dirección de la parte superior de la pila y la ejecución continúa en esa dirección. Si un método llama a otro método, el comportamiento LIFO de la pila asegura que la instrucción return del segundo método transfiere la ejecución al primer método, y la del primer método transfiere la ejecución al código que sigue al código que llamó al primer método. Como resultado una pila "recuerda" las direcciones de retorno de los métodos llamados. Pilas que contienen todos los parámetros del método llamado y las variables locales: Cuando se llama a un método, la JVM reserva memoria cerca de la dirección de retorno y almacena todos los parámetros del método llamado y las variables locales de ese método. Si el método es un método de ejemplar, uno de los parámetros que almacena en la pila es la referencia this del objeto actual.

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

[https://www.blogger.com/blogger.g?

blogID=6535684173821324097]

[https://www.blogger.com/blogger.g?

blogID=6535684173821324097]

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:

Como programar una PILA en Java Netbeans o Eclipse (FILO - LIFO)

Como programar una Pila en Java NetBeans o Eclipse FILO

http://aprenderaprogramar.com/index.php?option=com_content&view=article&id=608:la-estructura-de-datos-pila-en-java-clase-stack-del-api-java-ejemplo-simple-y-ejercicios-resueltoscu00920c&catid=58:curso-lenguaje-programacion-java-nivel-avanzado-i&Itemid=180 http://www.ciberaula.com/articulo/pilas_en_java/

Colas en Java

En una Cola los elementos se añaden desde la parte de atrás o la parte final de la cola, sin embargo la información se extrae desde el frente, es decir, los elementos que se añadieron primero serán los primeros en salir, esto se conoce como estructura FIFO (First In First Out). Los elementos de la cola se añaden y se eliminan de tal manera que el primero en entrar es el primero en salir. La adición de elementos se realiza a través de una operación llamada encolar (enqueue), mientras que la eliminación se denomina desencolar (dequeue). La operación de encolar inserta elementos por un extremo de la cola, mientras que la de desencolar los elimina por el otro. El siguiente interfaz muestras las operaciones típicas para colas: Cola.java

La siguiente es una posible implementación de colas mediante la clase Nodo: ColaEnlazada.java

Vemos como la clase Cola contiene dos campos, cola y cabecera que apuntan al principio y al final de la cola. La cabecera la utilizaremos para extraer elementos. Para insertar utilizaremos la cola. La operación encolar crea un nodo cuyo sucesor es nulo. Esto es porque añadimos al final de la cola, es decir, donde apunta el campo cola. Si la cola es vacía la cabecera y la cola apuntan al mismo objeto Nodo.

Para eliminar (desencolar) y para consultar (cabecera) se utiliza el campo cabecera. Se extraen/consultan elementos de la cabeza de la cola.

Hacer una Cola en Java

Hacer una cola (Queue) en java

http://www.ciberaula.com/articulo/colas_en_java/ http://es.slideshare.net/RoverOportunity2012/java-pilas-ycolas

Publicado hace 16th November 2015 por JuanPablo Salazar 2

Ver comentarios

Rey Salcedo 5 de agosto de 2018, 21:34 Excelente trabajo, muy bien explicado y documentado, hago http://usandojava.blogspot.com/2012/01/implementacion-de-pila-y-cola.html Responder

mi

aporte

espero

les

guste

Atalaya de la Mota 26 de mayo de 2020, 14:05 Gracias por la guia, muy completa. Te pregunto como hacer el sgte ejercicio gracias. Crear una clase en JAVA que permita definir una pila construida a partir de un arreglo. Adicionar un método que permita mostrar cuántos datos se pueden agregar a la pila o si ya está llena. Crear un objeto de esta clase con un tamaño de 9. Apilar 5 valores numéricos aleatorios. Mostrar el tamaño actual de la pila. Borrar un dato. Indicar nuevamente el tamaño actual. Enseñar la cantidad de datos que se pueden agregar a la pila. En JAVA, utilizar la clase Stack para crear dos nuevas pilas. Agregar 7 datos a la primera pila. La segunda pila deberá contener los mismos datos de la primera, pero en orden inverso. Responder

Escribe un comentario...

Comentar como:

Publicar

Vista previa

jhan24b@gmai

Cerrar sesión

Notificarme...