Pilas y colas java

Solo disponible en BuenasTareas
  • Páginas : 13 (3175 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de febrero de 2011
Leer documento completo
Vista previa del texto
http://www.compunauta.com/forums/linux/programacion/java/AprendiendoJava.pdf
http://www.mmc.igeofcu.unam.mx/cursos/mcst-2007-II/Ejemplitos/EstructurasDatos/a4.pdf
http://www.ctr.unican.es/asignaturas/eda/cap6-implementaciones2-2en1.pdf
http://books.google.com.mx/books?id=2Fwqu0XE77gC&pg=PA157&dq=funcionamiento+colas+en+java&cd=2#v=onepage&q=&f=false

Pilas y Colas
Pilas que "Recuerdan"
LaPila es una estrucutra de datos donde las inserciones y recuperaciones/borrados de datos se
hacen en uno de los finales, que es conocido como el top de la pila. Como el último elemento
insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como
pilas LIFO (last-in, first-out).
Los datos se push (insertan) dentro y se pop (recuperan/borran) de la partesuperior de la pila. La
siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila:
Como muestra la figura anterior, las pilas se construyen en memoria. Por cada dato insertado, el itém
superior anterior y todos los datos inferiores se mueven hacia abajo. Cuando llega el momento de
sacar un ítem de la pila, se recpupera y se borra de la pila el ítemsuperior (que en la figura anterior
se revela como "third").
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 elmé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 sa 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 primermé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.
Es muy común implementar una pila utilizando un array uni-dimensional o una lista de enlace simple.
En el escenario del array uni-dimensional, una variable entera, típicamente llamada top, contiene el
índice de la parte superior de la pila. De forma similar, una variable de referencia, también nombradanoramlmente como top, referencia el nodo superior del escenario de la lista de enlace simple.

He modelado mis implementaciones de pilas después de encontrar la arquitectura del API Collections
de Java. Mis implementaciones constan de un interface Stack para una máxima flexibilidad, las
clases de implementación ArrayStack y LinkedListStack, y una clase de soporte
FullStackException. Parafacilitar su distribución, he empaquetado estas clases en un paquete
llamado com.javajeff.cds, donde cds viene de estructura de datos complejas. El siguiente listado
presenta el interface Stack:
// Stack.java
package com.javajeff.cds;
public interface Stack {
boolean isEmpty ();
Object peek ();
void push (Object o);
Object pop ();
}
Sus cuatro métodos determinan si la pila está vacía,recuperan el elemento superior sin borrarlo de la
pia, situan un elemento en la parte superior de la pila y el último recuera/borra el elemento superior.
Aparte de un constructor específico de la implementación, su programa únicamente necesita llamar a
estos métodos.
El siguiente listado presenta una implementación de un Stack basado en un array uni-dimensional:
// ArrayStack.java
package...
tracking img