APUNTES SOBRE LA ESTRUCTURA DE DATOS EN JAVA

Tipo abstracto de datos Pila

Una pila (stack) es una colección ordenada de elementos a los que sólo se puede acceder por un único lugar o extremo de la pila. Los elementos de la pila se añaden o quitan (borran) de la misma sólo por su parte superior (cima) de la pila. Las entradas de la pila deben ser eliminadas en el orden inverso al que se situaron en la misma. Por ejemplo, se puede crear una pila de libros, situando primero un diccionario, encima de él una enciclopedia y encima de ambos una novela de modo que la pila tendrá la novela en la parte superior.

Operaciones básicas de una pila.

Debido a su propiedad específica “último en entrar, primero en salir” se conoce a las pilas como estructura de datos LIFO (last-in/first-out). La pila se puede implementar guardando los elementos en un arreglo en cuyo caso su dimensión o longitud es fija. También se puede utilizar un Vector para almacenar los elementos. Otra forma de implementación consiste en construir una lista enlazada, cada elemento de la pila forma un nodo de la lista; la lista crece o decrece según se añaden o se extraen, respectivamente, elementos de la pila; ésta es una representación dinámica y no existe limitación en su tamaño excepto la memoria de la computadora.

Una pila puede estar vacía (no tiene elementos) o llena (en la representación con un arreglo, si se ha llegado al último elemento). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error, una excepción, debido a que esa operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila llena se produce un error, o excepción, de desbordamiento (overflow) o rebosamiento.

Especificaciones de la pila.

Las operaciones que sirven para definir una pila y poder manipular su contenido son las siguientes. Tipo de dato Elemento que se almacena en la pila

Operaciones

CrearPila Inicia

Insertar (push) Pone un dato en la pila

Quitar (pop) Retira (saca) un dato de la pila

Pila vacía Comprueba si la pila no tiene elementos

Pila llena Comprueba si la pila está llena de elementos

Limpiar pila Quita todos sus elementos y deja la pila vacía

CimaPila Obtiene el elemento cima de la pila

Tamaño de la pila Número de elementos máximo que puede contener la pila.

Ejemplo 36.2 muestra cómo declarar una pila con un arreglo lineal. El tipo de los elementos de la pila es Object, lo que permite que pueda contener cualquier tipo de objeto.

Pila dinámica implementada con el vector.

La clase Vector es un contenedor de objetos que puede ser manejado para que crezca y decrezca dinámicamente. Los elementos de Vector son de tipo Object. Dispone de métodos para asignar un elemento en una posición (insertElementAt), para añadir un elemento a continuación del último (addElement), para obtener el elemento que se encuentra en una posición determinada (elementAt), para eliminar un elemento (removeElementAt) ...

La posición del último elemento añadido a la pila se mantiene con la variable cima. Inicialmente cima == −1, que es la condición de pila vacía.

Insertar un nuevo elemento supone aumentar cima y asignar el elemento a la posición cima del Vector. La operación se realiza llamando al método addElement. No resulta necesario implementar el método pilaLlena ya que la capacidad del Vector crece dinámicamente.

El método quitar( ) devuelve el elemento cima de la pila y lo elimina. Al utilizar un Vector, llamando a removeElementAt(cima) se elimina el elemento cima; a continuación se decrementa cima.

La implementación es:

Pila implementada con una lista enlazada.

Guardar los elementos de la pila en una lista enlazada permite que la pila crezca o decrezca de manera indefinida. El tamaño se ajusta exactamente a su número de elementos.

Clase Pila y NodoPila.

Los elementos de la pila son los nodos de la lista, con un campo para guardar el elemento y otro de enlace. La clase NodoPila representa un nodo de la lista enlazada. Tiene dos atributos: elemento guarda el elemento de la pila y siguiente contiene la dirección del siguiente nodo de la lista. El constructor pone el dato en elemento e inicializa siguiente a null. El tipo de dato de elemento se corresponde con el tipo de los elementos de la pila, para que no dependa de un tipo concreto; para que sea más gené rico se utiliza el tipo Object y de esa forma puede almacenar cualquier tipo de referencia.

La clase PilaLista implementa las operaciones del TAD pila. Además, dispone del atributo cima que es la dirección del primer nodo de la lista. El constructor inicializa la pila vacía (cima == null), realmente, a la condición de lista vacía.

Implementación de las operaciones.

Las operaciones insertar, quitar, cima acceden a la lista directamente con la referencia cima (apunta al último nodo apilado). Entonces, como no necesitan recorrer los nodos de la lista, no dependen del número de nodos, la eficiencia de cada operación es constante, O(1). La clase PilaLista forma parte del mismo paquete que NodoLista, por ello tiene acceso a todos sus miembros.

Verificación del estado de la pila:

Poner un elemento en la pila. Crea un nuevo nodo con el elemento que se pone en la pila y se enlaza por la cima.

Eliminación del elemento cima. Retorna el elemento cima y lo quita de la pila.

Obtención del elemento cabeza o cima de la pila, sin modificar la pila:

Vaciado de la pila. Libera todos los nodos de que consta la pila. Recorre los n nodos de la lista enlazada, entonces es una operación lineal, O(n).

Tutorial de Pilas.

Tipo abstracto de datos Cola.

Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista (figura 36.18). Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por el frente (parte inicial, frente) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.

Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacena, por ello una cola es una estructura de tipo FIFO (first-in/first-out, primero en entra.

Especificaciones del tipo abstracto de datos Cola .

Las operaciones que sirven para definir una cola y poder manipular su contenido son las siguientes: Tipo de dato Elemento que se almacena en la cola

Operaciones

CrearCola Inicia la cola como vacía

Insertar Añade un elemento por el final de la cola

Quitar Retira (extrae) el elemento frente de la cola

Cola vacía Comprobar si la cola no tiene elementos

Cola llena Comprobar si la cola está llena de elementos

Frente Obtiene el elemento frente o primero de la cola

Tamaño de la cola Número de elementos máximo que puede contener la cola

Las colas se implementan utilizando una estructura estática (arreglos), o una estructura dinámica (listas enlazadas, Vector...). Utilizar un arreglo tiene el problema del avance lineal de frente y fin; este avance deja huecos por la izquierda del arreglo. Llega a ocurrir que fin alcanza el índice más alto del arreglo, sin poder añadir nuevos elementos y sin embargo haber posiciones libres a la izquierda de frente.

Cola con un arreglo circular .

La forma más eficiente de almacenar una cola en un array es modelar a éste de tal forma que se una el extremo final con el extremo cabeza. Tal arreglo se denomina arreglo circular y permite que la totalidad de sus posiciones se utilicen para almacenar elementos de la cola sin necesidad de desplazar elementos. La figura 36.20 muestra un arreglo circular de n elementos.

El arreglo se almacena de modo natural en la memoria, como un bloque lineal de n elementos. Se necesitan dos marcadores (apuntadores) frente y fin para indicar, respectivamente, la posición del elemento cabeza y del último elemento puesto en la cola.

El frente siempre contiene la posición del primer elemento de la cola y avanza en el sentido de las agujas del reloj; fin contiene la posición donde se puso el último elemento, también avanza en el sentido del reloj (circularmente a la derecha). La implementación del movimiento circular se realiza según la teoría de los restos, de tal forma que se generen índices de 0 a MAXTAMQ−1:

Mover fin adelante = (fin + 1) % MAXTAMQ

Mover frente adelante = (frente + 1) % MAXTAMQ

Los algoritmos que formalizan la gestión de colas en un arreglo circular han de incluir las operaciones básicas del TAD cola; en concreto, las siguientes tareas básicas:

• Creación de una cola vacía, de tal forma que fin apunte a una posición inmediatamente anterior a frente: frente = 0; fin = MAXTAMQ−1.

• Comprobar si una cola está vacía: frente == siguiente(fin)

• Comprobar si una cola está llena. Para diferenciar la condición entre cola llena y cola vacía se sacrifica una posición del arreglo, de tal forma que la capacidad de la cola va a ser MAXTAMQ−1. La condición de cola llena:

frente == siguiente(siguiente(fin))

• Poner un elemento a la cola, si la cola no está llena, avanzar fin a la siguiente posición: fin = (fin + 1) % MAXTAMQ y asignar el elemento.

• Retirar un elemento de la cola, si la cola no está vacía, quitarlo de la posición frente y avanzar frente a la siguiente posición:(frente + 1) % MAXTAMQ.

• Obtener el elemento primero de la cola, si la cola no está vacía, sin suprimirlo de la cola.

Clase cola con array circular .

La clase declara los apuntadores frente, fin y el arreglo listaCola[ ]. El método siguiente( ) obtiene la posición siguiente de una dada, aplicando la teoría de los restos. A continuación se codifica los métodos que implementan las operaciones del TAD cola. Ahora el tipo de los elementos es Object, de tal forma que se pueda guardar cualquier tipo de elementos.

Cola implementada con una lista enlazada .

La implementación del TAD Cola con una lista enlazada permite ajustar el tamaño exactamente al nú mero de elementos de la cola; la lista enlazada crece y decrece según las necesidades, según se incorporen elementos o se retiren. Utiliza dos apuntadores (referencias) para acceder a la lista, frente y fin, que son los extremos por donde salen y por donde se ponen, respectivamente, los elementos de la cola.

La referencia frente apunta al primer elemento de la lista y por tanto de la cola (el primero en ser retirado). La referencia fin apunta al último elemento de la lista y también de la cola.

Declaración de nodo y cola Se utilizan las clases Nodo y ColaLista. El Nodo representa al elemento y al enlace con el siguiente nodo; al crear un Nodo se asigna el elemento y el enlace se pone null. Con el objetivo de generalizar, el elemento se declara de tipo Object. La clase ColaLista define las variables (atributos) de acceso: frente y fin, y las operaciones básicas del TAD cola. El constructor de ColaLista inicializa frente y fin a null, es decir, a la condición cola vacía.