Listas, pilas

y colas
en Java
Captulo
Contenido
Tipo abstracto de datos (TAD) lista
Clase Lista
Lista ordenada
Lista doblemente enlazada
Lista circular
Tipo abstracto de datos pila
Pila dinmica implementada con vector
Pila implementada con una lista enlazada
Tipo abstracto de datos cola
Cola implementada con una lista enlazada
Resumen
Ejercicios
Problemas
Introduccin
La estructura de datos que se estudia en este captulo es la lista enlazada (ligada o encadenada, linked
list), que es una coleccin de elementos (denominados nodos) dispuestos uno a continuacin de otro,
cada uno de ellos conectado al siguiente elemento por un enlace o referencia. En el captulo se
desarrollan mtodos para insertar, buscar y borrar elementos en las listas enlazadas. De igual modo
se muestra el tipo abstracto de datos (TAD) que representa a las listas enlazadas.
Las pilas, como tipo abstracto de datos, son objeto de estudio en este captulo; son estructuras de
datos LIFO (last-in/first-out, ltimo en entrar/primero en salir). Las pilas se utilizan en compiladores,
sistemas operativos y programas de aplicaciones.
Tambin en este captulo se estudia el tipo abstracto cola. Las colas se conocen como estructuras
FIFO (first-in/first-out, primero en entrar/primero en salir), debido al orden de insercin y de extrac-
36
1109 Tipo abstracto de datos (TAD) lista
cin de elementos de la cola. Las colas tienen numerosas aplicaciones en el mundo de la computa-
cin: colas de mensajes, colas de tareas a realizar por una impresora, colas de prioridades.
Conceptos clave
Arreglo circular Lista doble
Estructura de datos LIFO Lista enlazada
Estructura FIFO Nodos
Lista circular
Tipo abstracto de datos (TAD) lista
Una lista enlazada es una coleccin o secuencia de elementos dispuestos uno detrs de otro, en la que
cada elemento se conecta al siguiente por un enlace o referencia. La idea bsica consiste en cons-
truir una lista cuyos elementos llamados nodos se componen de dos partes (campos): la primera par-
te contiene la informacin y es, por consiguiente, un valor de un tipo genrico (denominado Dato,
TipoElemento, Info, etc.) y la segunda parte es una referencia (denominada enlace) que apunta,
enlaza, al siguiente elemento de la lista.
Figura 36.1 Lista enlazada (representacin grfica tpica).
...
e
1
e
2
e
3
e
n
Los enlaces se representan por flechas para facilitar la comprensin
de la conexin entre dos nodos; ello indica que el enlace tiene la direc-
cin en memoria del siguiente nodo. Los enlaces tambin sitan los
nodos en una secuencia. El primer nodo se enlaza al segundo nodo, el
segundo se enlaza al tercero y as sucesivamente hasta llegar al ltimo.
El nodo ltimo ha de ser representado de forma diferente para significar
que ste no se enlaza a ningn otro. Las listas se pueden dividir en cua-
tro categoras.
Clasificacin de las listas enlazadas
Los diferentes tipos de listas dependen de la forma de enlazar los nodos, son:
Listas simplemente enlazadas . Cada nodo (elemento) contiene un nico enlace que conecta ese
nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos (adelante).
Listas doblemente enlazadas . Cada nodo contiene dos enlaces, uno a su nodo predecesor y el
otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo (adelante) como en re-
corrido inverso (atrs).
Lista circular simplemente enlazada . Una lista enlazada simplemente en la que el ltimo ele-
mento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida
de modo circular (en anillo).
Lista circular doblemente enlazada . Una lista doblemente enlazada en la que el ltimo elemento
se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en ani-
llo) tanto en direccin directa (adelante) como inversa (atrs).
La implementacin de cada uno de los cuatro tipos de estructuras de listas se puede desarrollar
utilizando referencias.
El primer nodo, frente, de una lista es el nodo apuntado por cabeza. La lista encadena nodos jun-
tos desde el frente hasta el final (cola) de la lista. El final se identifica como el nodo cuyo campo re-
ferencia tiene el valor null.

A recordar
Una lista enlazada consta de un nmero de
elementos y cada elemento tiene dos compo-
nentes (campos), una referencia al siguiente
elemento de la lista y un valor, que puede ser
de cualquier tipo.
1110 Captulo 36 Listas, pilas y colas en Java
TAD Lista
Una lista almacena informacin del mismo tipo, con la caracterstica de que puede contener un nme-
ro indeterminado de elementos, y que estos elementos mantienen un orden explcito. Este ordena-
miento explcito se manifiesta en que, en s mismo, cada elemento contiene la direccin del siguiente
elemento. Una lista es una estructura de datos dinmica, el nmero de nodos puede variar rpidamen-
te en un proceso, aumentando los nodos por inserciones, o bien, disminuyendo por eliminacin de
nodos.
Matemticamente, una lista es una secuencia de cero o ms elementos de un determinado tipo.
(a1, a2, a3, ... , an) siendo n >= 0,
si n = 0 la lista es vaca.
Los elementos de la lista tienen la propiedad de estar ordenados de forma lineal, segn las posiciones
que ocupan en la misma. Se dice que a
i
precede a a
i+1
para i = 1 ... , n1; y que a
i
sucede a a
i1
para
i = 2 ... n.
Para formalizar el tipo de dato abstracto Lista a partir de la nocin matemtica, se define un
conjunto de operaciones bsicas con objetos de tipo Lista. Las operaciones:
L Lista , x Dato, p puntero
Listavacia(L) Inicializa la lista L como lista vaca.
Esvacia(L) Determina si la lista L est vaca.
Insertar(L, x, p) Inserta en la lista L un nodo con el campo dato x, delante del nodo de di-
reccin p.
Localizar(L, x) Devuelve la posicin/direccin donde est el campo de informacin x.
Suprimir(L, x) Elimina de la lista el nodo que contiene el dato x.
Anterior(L, p) Devuelve la posicin/direccin del nodo anterior a p.
Primero(L) Devuelve la posicin/direccin del primer nodo de la lista L.
Anula(L) Vaca la lista L.
Estas operaciones son las que pueden considerarse bsicas para manejar listas. En realidad, la deci-
sin de qu operaciones son las bsicas depende de las caractersticas de la aplicacin que se va a realizar
con los datos de la lista.
Clase lista
Una lista enlazada se compone de una serie de nodos enlazados mediante referencias. En Java, se de-
clara una clase para contener las dos partes del nodo: dato y enlace. Por ejemplo, para una lista enla-
zada de nmeros enteros la clase Nodo:
class Nodo
{
protected int dato;
protected Nodo enlace;
public Nodo(int t)
{
dato = t;
enlace = null;
}
}
Figura 36.2 Representacin grfica de una lista enlazada.
dato siguiente
...
dato siguiente dato siguiente dato
cabeza actual cola
1111 Clase lista
Dado que los tipos de datos que se puede incluir en una lista pueden ser de cualquier tipo (enteros,
dobles, caracteres o cualquier objeto), con el fin de que el tipo de dato de cada nodo se pueda cambiar
con facilidad, a veces se define la clase Elemento como una generalizacin del tipo de dato de cada
campo. En ese caso se utiliza una referencia a Elemento dentro del nodo, como se muestra a conti-
nuacin:
class Elemento
{
// ...
}
class Nodo
{
protected Elemento dato;
protected Nodo enlace;
}
Ejemplo 36.1
Se declara la clase Punto, representa un punto en el plano con su coordenada x y y. Tambin,
la clase Nodo con el campo dato referencia a objetos de la clase Punto. Estas clases formarn
parte del paquete ListaPuntos.
package ListaPuntos;
public class Punto
{
double x, y;
public Punto(double x, double y)
{
this.x = x;
this.y = y;
}
public Punto( ) // constructor por defecto
{
x = y = 0.0;
}
}
La clase Nodo que se escribe a continuacin, tiene como campo dato una referencia a Pun-
to, y el campo enlace una referencia a otro nodo. Se definen dos constructores, el primero
inicializa dato a un objeto Punto y enlace a null. El segundo, inicializa enlace de tal for-
ma que referencia a un nodo.
package ListaPuntos;
public class Nodo
{
protected Punto dato;
protected Nodo enlace;
public Nodo(Punto p)
{
dato = p;
enlace = null;
}
public Nodo(Punto p, Nodo n)
{
dato = p;
enlace = n;
}
}
1112 Captulo 36 Listas, pilas y colas en Java
Definicin de la clase lista
El acceso a una lista se hace mediante una, o ms, referencias a los nodos. Normalmente, se accede a
partir del primer nodo de la lista, llamado cabeza o cabecera de la lista. En ocasiones, se mantiene
tambin una referencia al ltimo nodo de la lista enlazada, llamado cola de la lista.
4.15 5.25 71.5
10.5 NULL
Cabeza
Definicin nodo Definicin de referencias

class Nodo Nodo cabeza;
{
double dato; Nodo cola;
Nodo enlace;
public Nodo( ){;}
}
Figura 36.3 Declaraciones de tipos en lista enlazada.
Cola
Nota de programacin
La referencia cabeza (y cola) de una lista enlazada, normal-
mente se inicializa a null, indica lista vaca (no tiene nodos),
cuando se inicia la construccin de una lista. Cualquier mtodo
que se escriba para implementar listas enlazadas debe poder
manejar una referencia de cabeza (y de cola) null.
Error
Uno de los errores tpicos en el tratamiento de referencias con-
siste en escribir la expresin p.miembro cuando el valor de la
referencia p es null.
La clase Lista define el atributo cabeza o primero para acceder a los elementos de la lista. Nor-
malmente, no es necesario definir el atributo referencia cola. El constructor de lista inicializa
primero a null (lista vaca).
Los mtodos de la clase lista implementan las operaciones de una lista enlazada: insercin,
bsqueda... Adems, el mtodo crearLista( ) construye iterativamente el primer elemento (pri-
mero) y los elementos sucesivos de una lista enlazada.
A continuacin se declara la clase lista para representar una lista enlazada de nmeros enteros.
La declaracin se realiza paso a paso con el fin de describir detalladamente las operaciones. En primer
lugar, la declaracin del nodo de la lista con el dato de la lista, dos constructores bsicos y mtodos
de acceso:
package ListaEnteros;
public class Nodo
{
protected int dato;
protected Nodo enlace;
public Nodo(int x)
{
dato = x;
enlace = null;

A recordar
La construccin y manipulacin de una lista
enlazada requiere el acceso a los nodos de la
lista a travs de una o ms referencias a nodos.
Normalmente, se incluye una referencia al pri-
mer nodo (cabeza) y adems, en algunas aplica-
ciones, una referencia al ltimo nodo (cola).
1113 Clase lista
}
public Nodo(int x, Nodo n)
{
dato = x;
enlace = n;
}
public int getDato( )
{
return dato;
}
public Nodo getEnlace( )
{
return enlace;
}
public void setEnlace(Nodo enlace)
{
this.enlace = enlace;
}
}
A continuacin la clase lista:
package ListaEnteros;
public class Lista
{
private Nodo primero;
public Lista( )
{
primero = null;
}
//...
La referencia primero (a veces se denomina cabeza) se ha inicializado en el constructor a un
valor nulo, es decir, a lista vaca.
El mtodo crearLista( ), en primer lugar crea un nodo con un valor y su referencia se asigna
a primero:
primero = new Nodo(19);
19 null
primero
La operacin de crear un nodo se puede realizar en un mtodo al que se pasa el valor del campo
dato y del campo enlace. Si ahora se desea aadir un nuevo elemento con el 61, y situarlo en el pri-
mer lugar de la lista:
primero = new Nodo(61,primero);
primero
19 null 61
Por ltimo, para obtener una lista compuesta de 4, 61, 19 se habr de ejecutar
primero = new Nodo(4,primero);
primero
19 4 61
El mtodo crearLista( )construye una lista y devuelve una referencia al objeto lista creado
(this).
private int leerEntero( ) {;}
public Lista crearLista( )
{
int x;
1114 Captulo 36 Listas, pilas y colas en Java
primero = null;
do {
x = leerEntero( );
if (x != 1)
{
primero = new Nodo(x,primero);
}
} while (x != 1);
return this;
}
Insercin de un elemento en una lista
El nuevo elemento que se desea incorporar a una lista se puede insertar de distintas formas, segn la
posicin de insercin. sta puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento ltimo).
Antes de un elemento especificado, o bien,
Despus de un elemento especificado.
Insertar un nuevo elemento en la cabeza de la lista
La posicin ms eficiente para insertar un nuevo elemento es la cabeza, es decir, por el primer nodo
de la lista. El proceso de insercin se resume en este algoritmo:
1. Crear un nodo e inicializar el campo dato al nuevo elemento. La referencia del nodo creado
se asigna a nuevo, variable local del mtodo.
2. Hacer que el campo enlace del nuevo nodo apunte a la cabeza (primero) de la lista ori-
ginal.
3. Hacer que primero apunte al nodo que se ha creado.
El cdigo fuente del mtodo insertarCabezaLista:
public Lista insertarCabezaLista(Elemento entrada)
{
Nodo nuevo ;
nuevo = new Nodo(entrada);
nuevo.enlace = primero; // enlaza nuevo nodo al frente de la lista
primero = nuevo; // mueve primero y apunta al nuevo nodo
return this; // devuelve referencia del objeto Lista
}
Insertar entre dos nodos de la lista
Por ejemplo, en la lista de la figura 36.4 insertar el elemento 75 entre los nodos con los datos 25 y 40.
El algoritmo para la operacin de insertar entre dos nodos (n1, n2) requiere las siguientes etapas:
1. Crear un nodo con el nuevo elemento y el campo enlace a null. La referencia al nodo se
asigna a nuevo.
2. Hacer que el campo enlace del nuevo nodo apunte al nodo n2, ya que el nodo creado se ubi-
car justo antes de n2 (en el ejemplo de la figura 36.4, el nodo 40).
3. La variable referencia anterior tiene la direccin del nodo n1 (en el ejemplo de la figura
36.4, el nodo 25), entonces hacer que anterior.enlace apunte al nodo creado.
Figura 36.4 Insercin entre dos nodos.
10 25
75
40 NULL
1115 Clase lista
Grficamente las etapas del algoritmo y el cdigo que implementa la operacin.
Etapa 1
Se crea un nodo con el dato 75. La variable anterior apunta al nodo n1, en la figura 25.
40 NULL 10 25
primero
anterior
no se utiliza

75
Cdigo Java
nuevo = new Nodo(entrada);
Etapa 2
El campo enlace del nodo creado que apunte a n2, en la figura 40. La direccin de n2 se consigue con
anterior.enlace:
40 null 10 25
nuevo
anterior
75
Cdigo Java
nuevo.enlace = anterior.enlace
Etapa 3
Por ltimo, el campo enlace del nodo n1 (anterior) que apunte al nodo creado:
40 null 10 25
nuevo
anterior
75
nuevo
1116 Captulo 36 Listas, pilas y colas en Java
La operacin es un mtodo de la clase lista:
public Lista insertarLista(Nodo anterior, Elemento entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.enlace = anterior.enlace;
anterior.enlace = nuevo;
return this;
}
Antes de llamar al mtodo insertarLista( ), es necesario buscar la direccin del nodo n1,
esto es, del nodo a partir del cual se enlazar el nodo que se va a crear.
Bsqueda en listas enlazadas
La operacin bsqueda de un elemento en una lista enlazada recorre la lista hasta encontrar el nodo
con el elemento. El algoritmo, una vez encontrado el nodo, devuelve la referencia a ese nodo (en caso
negativo, devuelve null). Otro planteamiento es que el mtodo devuelva true si encuentra el nodo
con el elemento, y false si no est en la lista.
primero
5.75 41.25 101.43 0.25 NULL
ndice
Figura 36.5 Bsqueda en una lista.
El mtodo buscarLista, de la clase Lista, utiliza la referencia indice para recorrer la lista,
nodo a nodo. El bucle de bsqueda inicializa indice al nodo primero, compara el nodo referencia-
do por indice con el elemento buscado. Si coincide, la bsqueda termina; en caso contrario, indice
avanza al siguiente nodo. La bsqueda termina cuando se encuentra el nodo, o bien cuando se ha re-
corrido la lista y entonces indice toma el valor null. La comparacin entre el dato buscado y el dato
del nodo, que realiza el mtodo buscarLista( ), utiliza el operador == por claridad; realmente slo
se utiliza dicho operador si los datos son de tipo simple (int, double, ...). Normalmente, los datos
de los nodos son objetos y entonces se utiliza el mtodo equals( ) que compara dos objetos.
Cdigo Java
public Nodo buscarLista(Elemento destino)
{
Nodo indice;
for (indice = primero; indice!= null; indice = indice.enlace)
if (destino == indice.dato) // (destino.equals(indice.dato))
return indice;
return null;
}
Borrado de un nodo de una lista
La operacin de eliminar un nodo de una lista enlazada supone enlazar el nodo anterior con el nodo
siguiente al que se desea eliminar y liberar la memoria que ocupa. El algoritmo sigue estos pasos:
1. Bsqueda del nodo que contiene el dato. Se ha de obtener la direccin del nodo a eliminar y la
direccin del anterior.
2. El enlace del nodo anterior que apunte al nodo siguiente del que se elimina.
3. Si el nodo a eliminar es el cabeza de la lista (primero), se modifica primero para que tenga
la direccin del siguiente nodo.
4. Por ltimo, la memoria ocupada por el nodo se libera. Es el propio sistema el que libera el
nodo, al dejar de estar referenciado.
1117 Lista ordenada
A continuacin se escribe el mtodo eliminar( ), miembro de la clase Lista, recibe el dato
del nodo que se quiere borrar. Construye su bucle de bsqueda con el fin de disponer de la direc-
cin del nodo anterior.
Cdigo Java
public void eliminar (Elemento entrada)
{
Nodo actual, anterior;
boolean encontrado;
actual = primero;
anterior = null;
encontrado = false;
// bsqueda del nodo y del anterior
while ((actual!=null) && (!encontrado))
{
encontrado = (actual.dato == entrada);
//con objetos: actual.dato.equals(entrada)
if (!encontrado)
{
anterior = actual;
actual = actual.enlace;
}
}
// Enlace del nodo anterior con el siguiente
if (actual != null)
{
// Distingue entre que el nodo sea el cabecera,
// o del resto de la lista
if (actual == primero)
{
primero = actual.enlace;
}
else
{
anterior.enlace = actual.enlace;
}
actual = null; // no es necesario al ser una variable local
}
}
Lista ordenada
Los elementos de una lista tienen la propiedad de estar ordenados de forma lineal, segn las posiciones
que ocupan en la misma. Ahora bien, tambin es posible mantener una lista enlazada ordenada segn
el dato asociado a cada nodo. La figura 36.6 muestra una lista enlazada de nmeros reales, ordenada
de forma creciente.
La forma de insertar un elemento en una lista ordenada siempre realiza la operacin de tal forma
que la lista resultante mantiene la propiedad de ordenacin. Para esto, en primer lugar determina la
posicin de insercin, y a continuacin ajusta los enlaces.
Por ejemplo, para insertar el dato 104 en la lista de la figura 36.7 es necesario recorrer la lista has-
ta el nodo con 110.0, que es el inmediatamente mayor. El pointer indice se queda con la direccin
del nodo anterior, a partir del cual se enlaza el nuevo nodo.
primero
5.5 51.0 101.5 110.0 NULL
Figura 36.6 Lista ordenada.
1118 Captulo 36 Listas, pilas y colas en Java
primero
5.5 51.0 101.5 110.0 NULL
104
nuevo
ndice
Figura 36.7 Insercin en una lista ordenada.
El mtodo insertaOrden( ) crea una lista ordenada; el punto de partida es una lista vaca, a la
que se aaden nuevos elementos, de tal forma que en todo momento el orden de los elementos es cre-
ciente. La insercin del primer nodo de la lista consiste, sencillamente, en crear el nodo y asignar su
referencia a la cabeza de la lista. El segundo elemento se ha de insertar antes o despus del primero,
dependiendo de que sea menor o mayor. En general, para insertar un nuevo elemento a la lista orde-
nada, primero se busca la posicin de insercin en la lista actual, es decir, el nodo a partir del cual se
ha de enlazar el nuevo nodo para que la lista mantenga la ordenacin.
Los datos de una lista ordenada han de ser de tipo ordinal (tipo al que se pueda aplicar los opera-
dores ==, <, >); o bien objetos de clases que tengan definidos mtodos de comparacin (equals( ),
compareTo( ), ...). A continuacin se escribe el cdigo Java que implementa el mtodo para una lis-
ta de enteros.
public ListaOrdenada insertaOrden(int entrada)
{
Nodo nuevo ;
nuevo = new Nodo(entrada);
if (primero == null) // lista vaca
primero = nuevo;
else if (entrada < primero.getDato( ))
{
nuevo. setEnlace(primero);
primero = nuevo;
}
else /* bsqueda del nodo anterior a partir del que
se debe insertar */
{
Nodo anterior, p;
anterior = p = primero;
while ((p.getEnlace( ) != null) && (entrada > p.getDato( )))
{
anterior = p;
p = p.getEnlace( );
}
if (entrada > p.getDato( )) //se inserta despus del ltimo nodo
anterior = p;
// Se procede al enlace del nuevo nodo
nuevo.setEnlace(anterior.getEnlace( ));
anterior.setEnlace(nuevo);
}
return this;
}
Clase ListaOrdenada
Se declara la clase ListaEnlazada como extensin (derivada) de la clase lista. Por consiguiente,
hereda las propiedades de lista. Los mtodos eliminar( ) y buscarLista( ) se deben redefi-
nir para que la bsqueda del elemento aproveche el hecho de que stos estn ordenados.
La declaracin de la clase:
public class ListaOrdenada extends Lista
{
public ListaOrdenada( )
1119 Lista doblemente enlazada
{
super( );
}
public ListaOrdenada insertaOrden(int entrada) // ya definido
// mtodos a codificar:
public void eliminar (int entrada){ ; }
public Nodo buscarLista(int destino){ ; }
}
Lista doblemente enlazada
Existen numerosas aplicaciones en las que es conveniente poder acceder a los elementos o nodos de
una lista en cualquier orden, tanto hacia adelante como hacia atrs. La estructura lista doblemente
enlazada hace posible el acceso bidireccional a los elementos. Cada elemento de la lista dispone de
dos pointers (referencias), adems del valor almacenado. Una referencia apunta al siguiente elemento
de la lista y la otra referencia apunta al elemento anterior.
cabeza
a)
izquierdo Dato derecho
b)
Figura 36.8 Lista doblemente enlazada. a) Lista con tres nodos; b) nodo.
Las operaciones de una Lista doble son similares a las de una Lista: insertar, eliminar, buscar,
recorrer... Las operaciones que modifican la lista, insertar y eliminar, deben realizar ajustes de los dos
pointers de cada nodo. La figura 36.9 muestra los ajustes de los enlaces que se deben realizar al inser-
tar un nodo a la derecha del nodo actual.
Figura 36.9 Insercin de un nodo en una lista doblemente enlazada.
D
Nodo actual
I
D I
Para eliminar un nodo de la lista doble se necesita enlazar el nodo anterior con el nodo siguiente
del que se borra, como se observa en la figura 36.10.
Figura 36.10 Eliminacin de un nodo en una lista doblemente enlazada.
D I D
I
D I D I
I D
1120 Captulo 36 Listas, pilas y colas en Java
Clase Lista Doble
Un nodo de una lista doblemente enlazada tiene dos pointer (referencias) para enlazar con nodo iz-
quierdo y derecho, adems la parte correspondiente al campo dato. La declaracin de la clase Nodo:
package listaDobleEnlace;
public class Nodo
{
protected TipoDato dato;
protected Nodo adelante;
protected Nodo atras;
public Nodo(int entrada)
{
dato = entrada;
adelante = atras = null;
}
// ...
}
La clase ListaDoble implementa la estructura lista doblemente enlazada. La clase dispone de
la variable cabeza que referencia al primer nodo de la lista, y la variable cola para referenciar al l-
timo nodo.
package listaDobleEnlace;
public class ListaDoble
{
protected Nodo cabeza;
protected Nodo cola;
// mtodos de la clase (implementacin)
public ListaDoble( ){ cabeza = cola = null;}
public ListaDoble insertarCabezaLista(TipoDato entrada){;}
public ListaDoble insertaDespues(Nodo anterior, TipoDato entrada)
public void eliminar (TipoDato entrada)
public void visualizar( )
public void buscarLista(TipoDato destino)
}
Insertar un elemento en una lista doblemente enlazada
Se puede aadir un nuevo nodo a la lista de distintas formas, segn la posicin donde se inserte el
nodo. La posicin de insercin puede ser:
En la cabeza (elemento primero) de la lista.
Al final de la lista (elemento ltimo).
Antes de un elemento especificado.
Despus de un elemento especificado.
El algoritmo de insercin depende de la posicin donde se inserte. Los pasos que se siguen para
insertar despus de un nodo n son:
1. Crear un nodo con el nuevo elemento y asignar su referencia a la variable nuevo.
2. Hacer que el enlace adelante del nuevo nodo apunte al nodo siguiente de n (o bien a null si
n es el ltimo nodo). El enlace atras del nodo siguiente a n (si n no es el ltimo nodo) tiene
que apuntar a nuevo.
3. Hacer que el enlace adelante del nodo n apunte al nuevo nodo. A su vez, el enlace atras
del nuevo nodo debe apuntar a n.
El mtodo de la clase ListaDoble, insertaDespues( ), implementa el algoritmo. El primer
argumento, anterior, representa el nodo n a partir del cual se enlaza el nuevo nodo. El segundo ar-
gumento, entrada, es el dato que se aade a la lista.
1121 Lista doblemente enlazada
Cdigo Java
public ListaDoble insertaDespues(Nodo anterior, TipoDato entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = anterior.adelante;
if (anterior.adelante !=null)
anterior.adelante.atras = nuevo;
anterior.adelante = nuevo;
nuevo.atras = anterior;
if (anterior == cola) cola = nuevo; // es el ltimo elemento
return this;
}
Eliminar un elemento de una lista doblemente enlazada
Quitar un nodo de una lista doble supone realizar el enlace de dos nodos, el nodo anterior con el nodo
siguiente al que se desea eliminar. La referencia adelante del nodo anterior debe apuntar al nodo
siguiente, y la referencia atras del nodo siguiente debe apuntar al nodo anterior.
El algoritmo es similar al del borrado para una lista simple. Ahora, la direccin del nodo anterior
se encuentra en la referencia atras del nodo a borrar. Los pasos a seguir son:
1. Bsqueda del nodo que contiene el dato.
2. La referencia adelante del nodo anterior tiene que apuntar a la referencia adelante del
nodo a eliminar (si no es el nodo cabecera).
3. La referencia atras del nodo siguiente a borrar tiene que apuntar a la referencia atras del
nodo a eliminar (si no es el ltimo nodo).
4. Si el nodo que se elimina es el primero, cabeza, se modifica cabeza para que tenga la direc-
cin del nodo siguiente.
5. La memoria ocupada por el nodo es liberada automticamente.
El mtodo eliminar, de la clase ListaDoble, implementa el algoritmo:
public void eliminar (TipoDato entrada)
{
Nodo actual;
boolean encontrado = false;
actual = cabeza;
// Bucle de bsqueda
while ((actual != null) && (!encontrado))
{
/* La comparacin se podr realizar con el mtodo equals( )...,
depende del tipo que tenga entrada */
encontrado = (actual.dato == entrada);
if (!encontrado)actual = actual.adelante;
}
// Enlace de nodo anterior con el siguiente
if (actual != null)
{
//distingue entre nodo cabecera o resto de la lista
if (actual == cabeza)
{
cabeza = actual.adelante;
if (actual.adelante != null)
actual.adelante.atras = null;
}
else if (actual.adelante != null) // No es el ltimo nodo
{
actual.atras.adelante = actual.adelante;
actual.adelante.atras = actual.atras;
}
else // ltimo nodo
actual.atras.adelante = null;
1122 Captulo 36 Listas, pilas y colas en Java
if (actual == cola) cola = actual.atras;
actual = null;
}
}
Lista circular
En las listas lineales simples o dobles siempre hay un primer nodo (cabeza) y un ltimo nodo (cola).
Una lista circular, por propia naturaleza, no tiene ni principio ni fin. Sin embargo, resulta til estable-
cer un nodo a partir del cual se acceda a la lista y as poder acceder a sus nodos.
La figura 36.11 muestra una lista circular con enlace simple; podra considerarse que es una lista
lineal cuyo ltimo nodo apunte al primero.
Figura 36.11 Lista circular.
Lc
4.0 5.0 7.5 1.5
Las operaciones que se realizan sobre una lista circular son similares a las operaciones sobre listas
lineales, teniendo en cuenta que no hay primero ni ltimo nodo, aunque s un nodo de acceso a la
lista. Estas operaciones permiten construir el TAD lista circular y su funcionalidad es la siguiente:
Inicializacin o creacin.
Insercin de elementos en una lista circular.
Eliminacin de elementos de una lista circular.
Bsqueda de elementos de una lista circular.
Recorrido de cada uno de los nodos de una lista circular.
Verificacin de lista vaca.
La construccin de una lista circular se puede hacer con enlace simple o enlace doble. La imple-
mentacin que se desarrolla, en este apartado, enlaza dos nodos con un enlace simple.
Se declara la clase Nodo, con el campo dato y enlace; y la clase ListaCircular con el pointer
de acceso a la lista, junto a los mtodos que implementan las operaciones. Los elementos de la lista
pueden ser de cualquier tipo, se puede abstraer el tipo de stos en otra clase, por ejemplo Elemento;
con el fin de simplificar se supone un tipo conocido.
El constructor de la clase Nodo vara respecto al de las listas no circulares; el campo referencia
enlace, en vez de quedar a null, se inicializa para que apunte al mismo nodo, de tal forma que que-
da como lista circular de un solo nodo.
package listaCircular;
public class Nodo
{
Elemento dato;
Nodo enlace;
public Nodo (Elemento entrada)
{
dato = entrada;
enlace = this; // se apunta a s mismo
}
}
A tener en cuenta
El pointer de acceso a una lista circular, lc, normalmente apunta al ltimo nodo aadido a la
estructura. Esta convencin puede cambiar ya que en una estructura circular no hay primero
ni ltimo.
Figura 36.12
Creacin de un
nodo de lista
circular.
nuevo 2.5
1123 Lista circular
Clase Lista Circular
La clase ListaCircular declara la variable lc a partir de la cual se puede acceder a cualquier nodo
de la lista. El constructor de la clase inicializa la lista vaca.
package listaCircular;
public class ListaCircular
{
private Nodo lc;
public ListaCircular( )
{
lc = null;
}
public ListaCircular insertar(Elemento entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
if (lc != null) // lista circular no vaca
{
nuevo.enlace = lc.enlace;
lc.enlace = nuevo;
}
lc = nuevo;
return this;
}
El algoritmo empleado por el mtodo insertar, realiza la insercin en el nodo anterior al de ac-
ceso a la lista lc y considera que lc tiene la direccin del ltimo nodo insertado.
Eliminar un elemento de una lista circular
Para eliminar un nodo hay que enlazar el nodo anterior con el nodo siguiente al que se desea eliminar
y que el sistema libere la memoria que ocupa. El algoritmo es:
1. Bsqueda del nodo que contiene el dato.
2. Enlace del nodo anterior con el siguiente.
3. En caso de que el nodo a eliminar sea por el que se accede a la lista, lc, se modifica lc para
que tenga la direccin del nodo anterior.
4. Por ltimo, el sistema libera la memoria ocupada por el nodo al anular la referencia.
La implementacin del mtodo debe tener en cuenta que la lista circular tendr un solo nodo, ya
que al eliminarlo la lista se queda vaca (lc = null). La condicin de lista con un nodo se corres-
ponde con la forma de inicializar un nodo: lc = lc.enlace.
El mtodo recorre la lista buscando el nodo con el dato a eliminar, utiliza un pointer al nodo an-
terior para que cuando se encuentre el nodo se enlace con el siguiente. Se accede al dato con la sen-
tencia actual.enlace.dato, con el fin de que si coincide con el dato a eliminar, se disponga en
actual el nodo anterior.
Cdigo Java
public void eliminar(Elemento entrada)
{
Nodo actual;
boolean encontrado = false;
actual = lc;
while ((actual.enlace != lc) && (!encontrado))
{
encontrado = (actual.enlace.dato == entrada);
if (!encontrado)
{
actual = actual.enlace;
}
}
1124 Captulo 36 Listas, pilas y colas en Java
encontrado = (actual.enlace.dato == entrada);
// Enlace de nodo anterior con el siguiente
if (encontrado)
{
Nodo p;
p = actual.enlace; // Nodo a eliminar
if (lc == lc.enlace) // Lista con un solo nodo
lc = null;
else
{
if (p == lc)
{
lc = actual; // Se borra el elemento referenciado por lc,
// el nuevo acceso a la lista es el anterior
}
actual.enlace = p.enlace;
}
p = null;
}
}
Recorrer una lista circular
Una operacin comn a todas las estructuras enlazadas es recorrer o visitar todos los nodos de la es-
tructura. En una lista circular el recorrido puede empezar en cualquier nodo e iterativamente ir proce-
sando cada nodo hasta alcanzar el nodo de partida. El mtodo recorrer, miembro de la clase
ListaCircular, inicia el recorrido en el nodo siguiente al de acceso a la lista, lc, y termina cuando
alcanza el nodo lc.
public void recorrer( )
{
Nodo p;
if (lc != null)
{
p = lc.enlace; // siguiente nodo al de acceso
do {
System.out.println("\t" + p.dato);
p = p.enlace;
} while(p != lc.enlace);
}
else
System.out.println("\t Lista Circular vaca.");
}
Tipo abstracto de datos pila
Una pila (stack) es una coleccin ordenada de elementos a los que slo se puede acceder por un nico
lugar o extremo de la pila. Los elementos de la pila se aaden o quitan (borran) de la misma slo 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 en-
ciclopedia y encima de ambos una novela de modo que la pila tendr la novela en la parte superior.
Figura 36.13 Pila de libros.
Novela
Enciclopedia
Diccionario
1125 Tipo abstracto de datos pila
Debido a su propiedad especfica 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 dimensin
o longitud es fija. Tambin se puede utilizar un Vector para almacenar los elementos. Otra forma de
implementacin consiste en construir una lista enlazada, cada elemento de la pila forma un nodo de la
lista; la lista crece o decrece segn se aaden o se extraen, respectivamente, elementos de la pila; sta
es una representacin dinmica y no existe limitacin en su tamao excepto la memoria de la compu-
tadora.
Una pila puede estar vaca (no tiene elementos) o llena (en la representacin con un arreglo, si se
ha llegado al ltimo elemento). Si un programa intenta sacar un elemento de una pila vaca, se produ-
cir un error, una excepcin, debido a que esa operacin es imposible; esta situacin se denomina des-
bordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en
una pila llena se produce un error, o excepcin, de desbordamiento (overflow) o rebosamiento.
Especificaciones de una 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 vaca 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 vaca
CimaPila Obtiene el elemento cima de la pila
Tamao de la pila Nmero de elementos mximo que puede contener la pila
El ejemplo 36.2 muestra cmo 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.
Figura 36.14 Operaciones bsicas de una pila.
Insertar
Cima
Quitar
Fondo
Ejemplo 36.2
Declarar la clase Pila con elementos de tipo Object. Insertar y extraer de la pila datos de
tipo entero.
La declaracin de la clase:
package TipoPila;
1126 Captulo 36 Listas, pilas y colas en Java
Pila dinmica implementada con Vector
La clase Vector es un contenedor de objetos que puede ser manejado para que crezca y decrezca di-
nmicamente. Los elementos de Vector son de tipo Object. Dispone de mtodos para asignar un
elemento en una posicin (insertElementAt), para aadir un elemento a continuacin del ltimo
(addElement), para obtener el elemento que se encuentra en una posicin determinada (elemen-
tAt), para eliminar un elemento (removeElementAt) ...
La posicin del ltimo elemento aadido a la pila se mantiene con la variable cima. Inicialmente
cima == 1, que es la condicin de pila vaca.
Insertar un nuevo elemento supone aumentar cima y asignar el elemento a la posicin cima del
Vector. La operacin se realiza llamando al mtodo addElement. No resulta necesario implementar
el mtodo pilaLlena ya que la capacidad del Vector crece dinmicamente.
El mtodo 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 continuacin se decrementa
cima.
La implementacin es:
package TipoPila;
import java.util.Vector;
public class PilaVector
{
private static final int INICIAL = 19;
private int cima;
private Vector listaPila;
public PilaVector( )
{
cima = 1;
listaPila = new Vector(INICIAL);
}
public void insertar(Object elemento)throws Exception
{
cima++;
listaPila.addElement(elemento);
}
public Object quitar( ) throws Exception
{
Object aux;
public class PilaLineal
{
private static final int TAMPILA = 49;
private int cima;
private Object [ ]listaPila;
// operaciones que aaden o extraen elementos
public void insertar(Object elemento)
public Object quitar( )throws Exception
public Object cimaPila( )throws Exception
// resto de operaciones
}
El siguiente segmento de cdigo inserta los datos 11, 50 y 22:
PilaLineal pila = new PilaLineal( );
pila.insertar(new Integer(11));
pila.insertar(new Integer(50));
pila.insertar(new Integer(22));
Para extraer de la pila y asignar el dato a una variable:
Integer dato;
dato = (Integer) pila.quitar( );
1127 Pila implementada con una lista enlazada
if (pilaVacia( ))
{
throw new Exception ("Pila vaca, no se puede extraer.");
}
aux = listaPila.elementAt(cima);
listaPila.removeElementAt(cima);
cima;
return aux;
}
public Object cimaPila( ) throws Exception
{
if (pilaVacia( ))
{
throw new Exception ("Pila vaca, no se puede extraer.");
}
return listaPila.elementAt(cima);
}
public boolean pilaVacia( )
{
return cima == 1;
}
public void limpiarPila( )throws Exception
{
while (! pilaVacia( ))
quitar( );
}
}
Nota de programacin
Para utilizar una pila de elementos de tipo primitivo (int, char, long, float, double ... )
es necesario, para insertar, crear un objeto de la correspondiente clase envolvente (Integer,
Character, Long, Float, Double...) y pasar dicho objeto como argumento del mtodo in-
sertar( ).
Pila implementada con una lista enlazada
Guardar los elementos de la pila en una lista enlazada permite que la pila crezca o decrezca de mane-
ra indefinida. El tamao se ajusta exactamente a su nmero de elementos.
Figura 36. 15 Representacin de una pila con una lista enlazada.
Pila
Cima
1128 Captulo 36 Listas, pilas y colas en Java
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 en-
lace. La clase NodoPila representa un nodo de la lista enlazada. Tiene dos atributos: elemento guarda
el elemento de la pila y siguiente contiene la direccin 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 ms gen-
rico se utiliza el tipo Object y de esa forma puede almacenar cualquier tipo de referencia.
package TipoPila;
public class NodoPila
{
Object elemento;
NodoPila siguiente;
NodoPila(Object x)
{
elemento = x;
siguiente = null;
}
}
La clase PilaLista implementa las operaciones del TAD pila. Adems, dispone del atributo cima
que es la direccin del primer nodo de la lista. El constructor inicializa la pila vaca (cima == null),
realmente, a la condicin de lista vaca.
package TipoPila;
public class PilaLista
{
private NodoPila cima;
public PilaLista( )
{
cima = null;
}
// operaciones
}
Implementacin 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 depen-
den del nmero de nodos, la eficiencia de cada operacin es constante, O(1).
La clase PilaLista forma parte del mismo paquete que NodoLista, por ello tiene acceso a to-
dos sus miembros.
Verificacin del estado de la pila:
public boolean pilaVacia( )
{
return cima == null;
}
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.
public void insertar(Object elemento)
{
NodoPila nuevo;
nuevo = new NodoPila(elemento);
nuevo.siguiente = cima;
cima = nuevo;
}
1129 Pila implementada con una lista enlazada
Eliminacin del elemento cima. Retorna el elemento cima y lo quita de la pila.
public Object quitar( ) throws Exception
{
if (pilaVacia( ))
throw new Exception ("Pila vaca, no se puede extraer.");
Object aux = cima.elemento;
cima = cima.siguiente;
return aux;
}
Figura 36.16 Apilar un elemento.
Figura 36.17 Quita la cima de la pila.
pila
Obtencin del elemento cabeza o cima de la pila, sin modificar la pila:
public Object cimaPila( ) throws Exception
{
if (pilaVacia( ))
throw new Exception ("Pila vaca, no se puede leer cima.");
return cima.elemento;
}
Vaciado de la pila. Libera todos los nodos de que consta la pila. Recorre los n nodos de la lista enlazada,
entonces es una operacin lineal, O(n).
public void limpiarPila( )
{
NodoPila t;
while(!pilaVacia( ))
{
t = cima;
cima = cima.siguiente;
t.siguiente = null;
}
}
pila
cima
cima
1130 Captulo 36 Listas, pilas y colas en Java
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 utili-
zan una cola para almacenar elementos en su orden de aparicin o concurrencia.
Figura 36.18 Una cola.
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 entrar-primero en salir o bien primero en
llegar-primero en ser servido).
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 vaca
Insertar Aade un elemento por el nal de la cola
Quitar Retira (extrae) el elemento frente de la cola
Cola vaca 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
Tamao de la cola Nmero de elementos mximo que puede contener la cola
Las colas se implementan utilizando una estructura esttica (arreglos), o una estructura dinmica
(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 ms alto
del arreglo, sin poder aadir nuevos elementos y sin embargo haber posiciones libres a la izquierda de
frente.

A recordar
Una cola es una estructura de datos cuyos ele-
mentos mantienen un cierto orden, tal que slo
se pueden aadir elementos por un extremo,
final de la cola, y eliminar o extraer por el otro
extremo, llamado frente.
Figura 36.19 Una cola representada en un arreglo.
1 2 3 4
A G H K
frente fin
1 2 3 4
G H K
(posicin de frente y fin despus de extraer)
frente fin
1 2 3 4 ltimo
Frente Fin
1131 Tipo abstracto de datos Cola
Cola con un arreglo circular
La forma ms 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 to-
talidad 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.
Figura 36.20 Un arreglo circular.
n 1 0
1
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 posicin del ele-
mento cabeza y del ltimo elemento puesto en la cola.
Figura 36.21 Una cola vaca.
0
1
frente
final
2
n 1
El frente siempre contiene la posicin del primer elemento de la cola y avanza en el sentido de
las agujas del reloj; fin contiene la posicin donde se puso el ltimo elemento, tambin avanza en el
sentido del reloj (circularmente a la derecha). La implementacin del movimiento circular se realiza
segn la teora de los restos, de tal forma que se generen ndices de 0 a MAXTAMQ1:
Mover fin adelante = (fin + 1) % MAXTAMQ
Mover frente adelante = (frente + 1) % MAXTAMQ
Los algoritmos que formalizan la gestin de colas en un arreglo circular han de incluir las opera-
ciones bsicas del TAD cola; en concreto, las siguientes tareas bsicas:
Creacin de una cola vaca, de tal forma que fin apunte a una posicin inmediatamente ante-
rior a frente:
frente = 0; fin = MAXTAMQ1.
Comprobar si una cola est vaca:
frente == siguiente(fin)
Comprobar si una cola est llena. Para diferenciar la condicin entre cola llena y cola vaca se
sacrifica una posicin del arreglo, de tal forma que la capacidad de la cola va a ser MAXTAMQ1.
La condicin de cola llena:
frente == siguiente(siguiente(fin))

1132 Captulo 36 Listas, pilas y colas en Java

Poner un elemento a la cola, si la cola no est llena, avanzar fin a la siguiente posicin: fin =
(fin + 1) % MAXTAMQ y asignar el elemento.
Retirar un elemento de la cola, si la cola no est vaca, quitarlo de la posicin frente y avanzar
frente a la siguiente posicin:(frente + 1) % MAXTAMQ.
Obtener el elemento primero de la cola, si la cola no est vaca, sin suprimirlo de la cola.
Clase cola con array circular
La clase declara los apuntadores frente, fin y el arreglo listaCola[ ]. El mtodo siguiente( )
obtiene la posicin siguiente de una dada, aplicando la teora de los restos.
A continuacin se codifica los mtodos 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.
package TipoCola;
public class ColaCircular
{
private static fin int MAXTAMQ = 99;
protected int frente;
protected int fin;
protected Object [ ]listaCola ;
private int siguiente(int r)
{
return (r+1) % MAXTAMQ;
}
public ColaCircular( )
{
frente = 0;
fin = MAXTAMQ1;
listaCola = new Object [MAXTAMQ];
}
// operaciones de modificacin de la cola
public void insertar(Object elemento) throws Exception
{
if (!colaLlena( ))
{
fin = siguiente(fin);
listaCola[fin] = elemento;
}
else
throw new Exception("Overflow en la cola");
}
public Object quitar( ) throws Exception
{
if (!colaVacia( ))
{
Object tm = listaCola[frente];
frente = siguiente(frente);
return tm;
}
else
throw new Exception("Cola vacia ");
}
public void borrarCola( )
{
frente = 0;
fin = MAXTAMQ1;
}
// acceso a la cola
public Object frenteCola( ) throws Exception
{
if (!colaVacia( ))
{
1133 Cola implementada con una lista enlazada
return listaCola[frente];
}
else
throw new Exception("Cola vacia ");
}
// mtodos de verificacin del estado de la cola
public boolean colaVacia( )
{
return frente == siguiente(fin);
}
public boolean colaLlena( )
{
return frente == siguiente(siguiente(fin));
}
}
Cola implementada con una lista enlazada
La implementacin del TAD Cola con una lista enlazada permite ajustar el tamao exactamente al n-
mero de elementos de la cola; la lista enlazada crece y decrece segn las necesidades, segn se incor-
poren 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.
Figura 36.22 Cola con lista enlazada.
e
n
e
2
e
3
e
1
frente fin
...
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 tambin de la cola.
Declaracin de nodo y cola
Se utilizan las clases Nodo y ColaLista. El Nodo representa al elemento y al enlace con el siguien-
te nodo; al crear un Nodo se asigna el elemento y el enlace se pone null. Con el objetivo de genera-
lizar, el elemento se declara de tipo Object.
La clase ColaLista define las variables (atributos) de acceso: frente y fin, y las operaciones
bsicas del TAD cola. El constructor de ColaLista inicializa frente y fin a null, es decir, a la
condicin cola vaca.
package TipoCola;
// declaracin de Nodo (slo visible en este paquete)
class Nodo
{
Object elemento;
Nodo siguiente;
public Nodo(Object x)
{
elemento = x;
siguiente = null;
}
}
1134 Captulo 36 Listas, pilas y colas en Java
// declaracin de la clase ColaLista
public class ColaLista
{
protected Nodo frente;
protected Nodo fin;
// constructor: crea cola vaca
public ColaLista( )
{
frente = fin = null;
}
// insertar: pone elemento por el final
public void insertar(Object elemento)
{
Nodo a;
a = new Nodo(elemento);
if (colaVacia( ))
{
frente = a;
}
else
{
fin.siguiente = a;
}
fin = a;
}
// quitar: sale el elemento frente
public Object quitar( )throws Exception
{
Object aux;
if (!colaVacia( ))
{
aux = frente.elemento;
frente = frente.siguiente;
}
else
throw new Exception("Eliminar de una cola vaca");
return aux;
}
// libera todos los nodos de la cola
public void borrarCola( )
{
Nodo T;
for (; frente != null;)
{
T = frente;
frente = frente.siguiente; t.siguiente = null;
}
System.gc( );
}
// acceso al primero de la cola
public Object frenteCola( ) throws Exception
{
if (colaVacia( ))
throw new Exception("Error: cola vaca");
return (frente.elemento);
}
// verificacin del estado de la cola
public boolean colaVacia( )
{
return (frente == null);
}
}
1135 Resumen
Resumen
Una lista enlazada es una estructura de datos dinmica cuyos componentes estn ordenados l-
gicamente por sus campos de enlace en vez de ordenados fsicamente como estn en un arreglo.
El final de la lista se seala mediante una constante o referencia especial llamada null.
Una lista simplemente enlazada contiene slo un enlace a un sucesor nico, a menos que sea el
ltimo, en cuyo caso no se enlaza con ningn otro nodo.
Cuando se inserta un elemento en una lista enlazada, se deben considerar cuatro casos: aadir a
una lista vaca, aadir al principio de la lista, aadir en el interior y aadir al final de la lista.
Para borrar un elemento, primero hay que buscar el nodo que lo contiene y considerar dos casos:
borrar el primer nodo y borrar cualquier otro nodo de la lista.
El recorrido de una lista enlazada significa pasar por cada nodo (visitar) y procesarlo. El proceso
de cada nodo puede consistir en escribir su contenido, modificar el campo dato, etctera.
Una lista doblemente enlazada es aquella en la que cada nodo tiene una referencia a su sucesor
y otra a su predecesor. Las listas doblemente enlazadas se pueden recorrer en ambos sentidos.
Las operaciones bsicas son insercin, borrado y recorrer la lista; similares a las listas simples.
Una lista enlazada circularmente por propia naturaleza no tiene primero ni ltimo nodo. Las
listas circulares pueden ser de enlace simple o doble.
Una pila es una estructura de datos tipo LIFO (last-in/first-out, ltimo en entrar/primero en sa-
lir) en la que los datos (todos del mismo tipo) se aaden y eliminan por el mismo extremo, deno-
minado cima de la pila.
Se definen las siguientes operaciones bsicas sobre pilas: crear, insertar, cima, quitar,
pilaVacia, pilaLlena y limpiarPila.
crear inicializa la pila como pila vaca. Esta operacin la implementa el constructor.
insertar aade un elemento en la cima de la pila. Debe haber espacio en la pila.
cima devuelve el elemento que est en la cima, sin extraerlo.
quitar extrae de la pila el elemento cima de la pila.
pilaVacia determina si el estado de la pila es vaca; en su caso devuelve el valor lgico true.
pilaLlena determina si existe espacio en la pila para aadir un nuevo elemento. De no haber es-
pacio devuelve true. Esta operacin se aplica en la representacin de la pila mediante arreglo.
limpiarPila , el espacio asignado a la pila se libera, queda disponible.
El TAD Pila se puede implementar con arreglos y con listas enlazadas.
La realizacin de una pila con listas enlazadas ajusta el tamao de la estructura al nmero de ele-
mentos de la pila, es una estructura dinmica.
Una cola es una lista lineal en la que los datos se insertan por un extremo ( final) y se extraen por
el otro ( frente). Es una estructura FIFO (first-in/first-out, primero en entrar/primero en salir).
Las operaciones bsicas que se aplican sobre colas son: crearCola, colaVacia, colaLlena,
insertar, frente, retirar.
crearCola inicializa a una cola sin elementos. Es la primera operacin a realizar con una cola.
colaVacia determina si una cola tiene o no elementos. Devuelve true si no tiene elementos.
colaLlena determina si no se pueden almacenar ms elementos en una cola. Se aplica esta ope-
racin cuando se utiliza un arreglo para guardar los elementos de la cola.
insertar aade un nuevo elemento a la cola, siempre por el extremo final.
frente devuelve el elemento que est en el extremo frente de la cola, sin extraerlo.
retirar extrae el elemento frente de la cola.
El TAD cola se puede implementar con arreglos y con listas enlazadas. La implementacin con
un arreglo lineal es muy ineficiente; se ha de considerar el arreglo como una estructura circular
y aplicar la teora de los restos para avanzar el frente y el final de la cola.
La realizacin de una cola con listas enlazadas permite que el tamao de la estructura se ajuste
al nmero de elementos. La cola puede crecer indefinidamente, con el nico tope de la memoria
libre.
1136 Captulo 36 Listas, pilas y colas en Java
Numerosos modelos de sistemas del mundo real son de tipo cola: cola de impresin en un servi-
dor de impresoras, programas de simulacin, colas de prioridades en organizacin de viajes. Una
cola es la estructura tpica que se suele utilizar como almacenamiento de datos, cuando se envan
datos desde un componente rpido de una computadora a un componente lento (por ejemplo, una
impresora).
Ejercicios
36.1. Escribir un mtodo, en la clase Lista, que devuelva cierto si la lista est vaca.
36.2. Aadir a la clase ListaDoble un mtodo que devuelva el nmero de nodos de una lista
doble.
36.3. A la clase que representa una cola implementada con un arreglo circular y dos variables fren-
te y fin, se le aade una variable ms que guarda el nmero de elementos de la cola. Escribir
de nuevo los mtodos de manejo de colas considerando este campo contador.
36.4. A la clase Lista aadir el mtodo eliminaraPosicion( ) que elimine el nodo que ocupa
la posicin i, siendo el nodo cabecera el que ocupa la posicin 0.
36.5. Cul es la salida de este segmento de cdigo, teniendo en cuenta que el tipo de dato de la pila
es int:
Pila p = new Pila( );
int x = 4, y;
p.insertar(x);
System.out.println("\n " + p.cimaPila( ));
y = p.quitar( );
p.insertar(32);
p.insertar(p.quitar( ));
do {
System.out.println("\n " + p.quitar( ));
}while (!p.pilaVacia( ));
36.6. Se tiene una lista simplemente enlazada de nmeros reales. Escribir un mtodo para obtener
una lista doble ordenada respecto al campo dato, con los valores reales de la lista simple.
36.7. Se tiene una lista enlazada a la que se accede por el primer nodo. Escribir un mtodo que im-
prima los nodos de la lista en orden inverso, desde el ltimo nodo al primero; como estructura
auxiliar utilizar una pila y sus operaciones.
36.8. Supngase que se tienen ya codificados los mtodos que implementan las operaciones del
TAD Cola. Escribir un mtodo para crear una copia de una cola determinada. Las operaciones
que se han de utilizar sern nicamente las del TAD cola.
36.9. Dada una lista circular de nmeros enteros, escribir un mtodo que devuelva el mayor entero
de la lista.
36.10. Se tiene una lista de simple enlace, el campo dato es un objeto alumno con las variables: nom-
bre, edad, sexo. Escribir un mtodo para transformar la lista de tal forma que si el primer nodo
es de un alumno de sexo masculino, el siguiente sea de sexo femenino, as alternativamente,
siempre que sea posible, masculino y femenino.
36.11. Una lista circular de cadenas est ordenada alfabticamente. El pointer de acceso a la lista tie-
ne la direccin del nodo alfabticamente mayor. Escribir un mtodo para aadir una nueva pa-
labra, en el orden que le corresponda, a la lista.
1137 Problemas
36.12. Dada la lista del ejercicio 36.11 escribir un mtodo que elimine una palabra dada.
Problemas
36.1. Escribir un programa que realice las siguientes tareas:
Crear una lista enlazada de nmeros enteros positivos al azar, la insercin se realiza por el
ltimo nodo.
Recorrer la lista para mostrar los elementos por pantalla.
Eliminar todos los nodos que superen un valor dado.
36.2. Se tiene un archivo de texto de palabras separadas por un blanco o el carcter de fin de lnea.
Escribir un programa para formar una lista enlazada con las palabras del archivo. Una vez for-
mada la lista se pueden aadir nuevas palabras o borrar alguna de ellas. Al finalizar el
programa escribir las palabras de la lista en el archivo.
36.3. Un polinomio se puede representar como una lista enlazada. El primer nodo de la lista repre-
senta el primer trmino del polinomio; el segundo nodo al segundo trmino del polinomio y as
sucesivamente. Cada nodo tiene como campo dato el coeficiente del trmino y el exponente.
Por ejemplo, el polinomio 3x
4
4x
2
+ 11 se representa
3 4 11 4 2 0
Escribir un programa que permita dar entrada a polinomios en x, representndolos con una
lista enlazada simple. A continuacin, obtener una tabla de valores del polinomio para valores
de x = 0.0, 0.5, 1.0, 1.5, , 5.0.
36.4. Teniendo en cuenta la representacin de un polinomio propuesta en el problema 36.3, hacer
los cambios necesarios para que la lista enlazada sea circular. La referencia de acceso debe te-
ner la direccin del ltimo trmino del polinomio, el cual apuntar al primer trmino.
36.5. Segn la representacin de un polinomio propuesta en el problema 36.4, escribir un programa
para realizar las siguientes operaciones:
Obtener la lista circular suma de dos polinomios.
Obtener el polinomio derivada.
Obtener una lista circular que sea el producto de dos polinomios.
36.6. Se tiene un archivo de texto del cual se quieren determinar las frases que son palndromo, para
lo cual se ha de seguir la siguiente estrategia:
Considerar cada lnea del texto una frase.
Aadir cada carcter de la frase a una pila y a la vez a una cola.
Extraer carcter a carcter, y simultneamente de la pila y de la cola. Su comparacin de-
termina si es palndromo o no.
Escribir un programa que lea cada lnea del archivo y determine si es palndromo.
36.7. Un conjunto es una secuencia de elementos todos del mismo tipo sin duplicidades. Escribir un
programa para representar un conjunto de enteros mediante una lista enlazada. El programa
debe contemplar las operaciones:
Cardinal del conjunto.
Pertenencia de un elemento al conjunto.
Aadir un elemento al conjunto.
Escribir en pantalla los elementos del conjunto.
1138 Captulo 36 Listas, pilas y colas en Java
36.8. Con la representacin propuesta en el problema 36.7, aadir las operaciones bsicas de con-
juntos:
Unin de dos conjuntos.
Interseccin de dos conjuntos.
Diferencia de dos conjuntos.
Inclusin de un conjunto en otro.
36.9. Escribir un mtodo para determinar si una secuencia de caracteres de entrada es de la forma:
X & Y
siendo X una cadena de caracteres y Y la cadena inversa. El carcter & es el separador.
36.10. Utilizar una lista doblemente enlazada para controlar una lista de pasajeros de una lnea area.
El programa principal debe ser controlado por mens y debe permitir al usuario visualizar los
datos de un pasajero determinado, insertar un nodo (siempre por el final), eliminar un pasaje-
ro de la lista. A la lista se accede por dos variables, una referencia al primer nodo y la otra al
ltimo nodo.
36.11. Escribir un programa que haciendo uso de una pila, procese cada uno de los caracteres de una
expresin que viene dada en una lnea. La finalidad es verificar el equilibrio de parntesis, llaves
y corchetes. Por ejemplo, la siguiente expresin tiene un nmero de parntesis equilibrado:
((a+b)*5) 7
A esta otra expresin le falta un corchete: 2*[(a+b)/2.5 + x 7*y
36.12. Un vector disperso es aquel que tiene muchos elementos que son cero. Escribir un programa
que permita representar mediante listas enlazadas un vector disperso. Los nodos de la lista son
los elementos de la lista distintos de cero; en cada nodo se representa el valor del elemento y
el ndice (posicin del vector). El programa ha de realizar las operaciones: sumar dos vectores
de igual dimensin y hallar el producto escalar.