Universidad Carlos III de Madrid

La pila de ejecución de Java almacena las invocaciones de todos los métodos que se están ejecutando y permite, sobre todo en caso de producirse una excepción, hacer un seguimiento de las invocaciones hasta el método que la ha provocado, incluido el número de línea en el que se ha provocado. Para obtener dicha pila hay que invocar al método e.printStackTrace() del objeto Exception que se genera. A continuación, se muestra una posible pila de ejecución al no encontrar un fichero en un programa.

java.io.FileNotFoundException: fred.txt
   at java.io.FileInputStream.
              <init>(FileInputStream.java)
   at java.io.FileInputStream.
              <init>(FileInputStream.java)
   at ExTest.readMyFile(ExTest.java:19)
   at ExTest.main(ExTest.java:7)						

Dentro de las opciones del intérprete de Java, la opción -Xss permite establecer el tamaño de la pila para cada hilo de ejecución. Java tiene dos pilas: una para el código Java y otra para el código C. Esta opción establece el tamaño máximo de la pila que puede ser usada por el código Java en un hilo de ejecución. El tamaño por defecto de dicha pila es de 512 kilobytes (-Xss512k).

El API de Java tiene la implementación de una pila en la clase java.util.Stack. Los métodos son push, pop, peek, empty y search. Sin embargo, esta clase extiende de Vector y es extremadamente lenta. Al igual que la clase Vector (que además está en desuso), la clase Stack se recomienda no usarla ya, sino que se reemplace con arrays o con clases que implementen la interfaz java.util.List.

int [] arr = new int[10];
					

Supón que necesitamos 12 elementos en vez de 10, podemos expandirlo de esta manera:

int[] temporal = arr;   //Guarda la referencia a arr
arr = new int[12];      //Da más memoria a arr
for(int i=0;i<10;i++)   //Copia los datos antiguos
  arr[i] = temporal[i]; 
temporal = null;        //Desreferencia el temporal
					

Tal cual está, ésto sería una operación costosa. Imagina que esta expansión se hace cada vez que leemos de un fichero; sería muy ineficiente reexpandirlo cada vez que leemos unos pocos elementos. Por eso, cuando se implementa esta técnica, lo que se hace es expandir el array por una constante multiplicativa más grande. Por ejemplo, expandirlo dos veces más de su tamaño; de ser un array de N elementos pasaría a ser un array de 2N elementos.

Esta clase es la clase ArrayList, que deberás utilizar en lugar de la clase Vector cuando quieras implementar un array dinámico. La idea básica es que un ArrayList mantiene no sólo un tamaño, sino una capacidad; la capacidad es la cantidad de memoria que tiene reservada (es un detalle interno transparente al programador). El método add añade el elemento en la posición adecuada, tarea trivial si no se ha alcanzado la capacidad. Si sí la alcanza, la capacidad es automáticamente expandida, usando la técnica de expansión. Aparte, debes saber que indexar vía [] es para arrays básicos; en ArrayList se accede a los elementos mediante el método get.

La clase ArrayList es apropiada cuando las inserciones se realizan sólo en un lado del array, el más alto (usando add). Esto es así porque esta clase dobla (con la técnica de expansión dinámica) la capacidad interna del array si una inserción excediera dicha capacidad. Aunque esto da un buen orden de complejidad, especialmente si en el constructor podemos indicar una capacidad inicial, esta estructura es mala elección si las inserciones no se hacen al final, porque entonces hay que ir moviendo items.

En una lista enlazada, los elementos se almacenan de manera no contigua. Para hacer esto, cada objecto se almacena en un nodo que contiene además del objeto una referencia al siguiente nodo. Se mantienen dos referencias, una al primer elemento de la lista y otra a la última. Estas listas son más eficientes para evitar mover grandes cantidades de datos como habría que hacer en un array.

Las operaciones de acceso (get y set) de una cola siempre se ejecutan en los extremos de la misma; se extraen elementos de la cabeza (head) y se añaden por la cola (tail). El siguiente elemento que se extrae es el que se encuentra en la cabeza (head) de la misma. Para acceder a un elemento de la cola tienen que haberse extraído todos los elementos previos en orden. El paquete java.util de Java proporciona la siguiente interface para trabajar con colas:public interface Queue extends Collection con los siguientes métodos para operar con ellas:

Operación    Con Excepción    Sin Excepción
--------------------------------------------------------
añadir       add()            offer()
extraer      remove()         poll()
mirar        element()        peek()
					

El uso de una pila auxiliar permite realizar de forma eficiente la inversión de los elementos de una cola aprovechando que es una estructura de tipo LIFO (Last In - First Out). Para ello, apilamos en la pila los elementos que desencolamos de la cola y, posteriormente, añadimos a la cola los elementos que desapilamos de la pila. El código se muestra a continuación:

void invertir(Cola cola) {
 Pila pila = new Pila();
  while (!cola.vacia())
   pila.push(cola.dequeue());
  while (!pila.vacia())
   cola.enqueue(pila.pop())
} 
					

En efecto, la complejidad es constante, es decir, O(1), porque da igual el número de elementos que tengas en estas estructuras; el acceso siempre es a uno de los elementos de un extremo y no se necesita procesar el resto. Por ello, si se implementa alguno de estos métodos con una complejidad no constante, la implementación entonces no será tan eficiente y no es recomendable.

Cada aplicación gráfica de Java almacena las acciones del usuario (clicks, pulsaciones, etc.) en una cola de eventos (AWT Event Queue) a medida que se van produciendo. Por otro lado, existe una tarea que, mediante un bucle infinito, extrae los eventos de la cola y los procesa consecutivamente. Dicha tarea se conoce como "Event Dispatch Thread" (EVT) y procesa los eventos en función de su tipo. Por ejemplo, si el evento es un click sobre un componente, la tarea invocará al handler correspondiente del tipo de evento correspondiente del componente. Se puede invocar explícitamente el proceso de un evento del EVT usando los métodos SwingUtilities.invokeLater() o SwingUtilities.invokeAndWait().

Una cola doble (deque) puede almacenar o eliminar elementos tanto por la cabeza (top) como por la cola (tail). Una pila puede considerarse como una especialización de una cola doble y puede implementarse en base a ella. A continuación se muestra la equivalencia de los métodos de ambas:

Pila        Deque
--------------------------
size()      size()
isEmpty()   isEmpty()
top()       last()
push(e)     insertLast(e)
pop()       removeLast()
					

Una cola doble (deque) puede almacenar o eliminar elementos tanto por la cabeza (top) como por la cola (tail). Una cola puede considerarse como una especialización de una cola doble y puede implementarse en base a ella. A continuación se muestra la equivalencia de los métodos de ambas.

Cola        Deque
----------------------
size()      size()
isEmpty()   isEmpty()
front()     first()
enqueue(e)  insertLast(e)
dequeue()   removeFirst()

					

Una lista enlazada mantiene una única referencia al nodo inicial de la misma (head) para su implementación. En una cola implementada con lista enlazada , al hacer la inserción del dato (enqueue()) por el extremo final de la misma, el coste de la misma es proporcional al número de elementos de la lista enlazada (O(n)). Es por ello que se suele disponer de otra referencia que apunte al final (tail) para independizar el coste de la inserción del dato del tamaño de la lista (O(1)).

El uso de un array circular en la implementación de una cola (ArrayQueue) evita tener que hacer un desplazamiento adicional de los elementos del mismo en las operaciones de inserción y borrado del dato ya que los extremos del array coinciden y, por consiguiente, dichas operaciones son de orden de complejidad constante O(1). En el caso de la implementación de una pila basada en array (ArrayStack) no haría falta ni siquiera que fuera un array circular ya que dicho desplazamiento no se produce ni en la inserción ni en el borrado del dato al realizarse por el mismo extremo del array y siendo igualmente con complejidad constante O(1).

En Java, un iterador (Iterator) proporciona un mecanismo para recorrer los elementos de una colección y sustituye a las antiguas enumeraciones (Enumeration). Sin embargo, tanto las pilas como las colas son estructuras de datos que "esconden" los elementos intermedios y solo proporcionan métodos de acceso por los extremos de las mismas, por eso no tiene sentido usar un objeto iterador sobre las mismas.