Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Listas Enlazadas, Pilas y Colas

Tabla de contenidos

1. Sesión 4 (laboratorio): Pilas y Colas
1.1. Implementación de una pila con listas enlazadas
1.2. Implementación de una cola con listas enlazadas
2. Actividades para casa
2.1. Trabajo con Listas doblemente enlazadas
2.2. Implementación de una Deque (Bicola) mediante lista doblemente enlazada
2.3. Implementación de pilas y colas con Deques (Bicolas)

Lab Section1. Sesión 4 (laboratorio): Pilas y Colas

Exercise Section1.1. Implementación de una pila con listas enlazadas

Objetivo

Mediante la resolución de este ejercicio se pretende que el alumno aprenda a implementar una pila utilizando listas enlazadas como estructura de datos.

Apartado 1

Implementa una pila utilizando una lista enlazada como estructura de datos. La pila debe permitir almacenar cualquier tipo de objeto, e implementar al menos métodos para:

- Insertar un objeto en la pila (push).

- Recuperar un objeto de la pila (pop).

- Obtener el objeto de la cima (top) de la pila, sin extraerlo.

- Averiguar si hay algún objeto almacenado en la pila.

- Devolver el número de objetos almacenados en la pila.

Diseña la clase, decidiendo el nombre de cada método, sus parámetros y su valor de retorno. (Pista: Crea una clase Node, que sea la encargada de almacenar los valores de la pila)

Apartado 2

Haz una clase de prueba que lea líneas de un fichero y las imprima en orden inverso en pantalla. Por ejemplo, si el fichero tiene cuatro lineas "A", "B", "C" y "D", debe imprimir "D", "C", "B" y "A". La solución debe utilizar internamente una pila.

Exercise Section1.2. Implementación de una cola con listas enlazadas

Objetivo

Mediante la resolución de este ejercicio se pretende que el alumno aprenda a implementar una cola utilizando listas enlazadas como estructura de datos.

Apartado 1

Implementa una cola utilizando una lista enlazada como estructura de datos. La cola debe permitir almacenar cualquier tipo de objeto, e implementar al menos métodos para:

- Insertar un objeto en la cola (enqueue).

- Recuperar un objeto de la cola (dequeue).

- Obtener el primer objeto (first) de la cola, sin extraerlo.

- Averiguar si hay algún objeto almacenado en la cola (isEmpty).

- Devolver el número de objetos almacenados en la cola (size).

Diseña la clase, decidiendo el nombre de cada método, sus parámetros y su valor de retorno.

Apartado 2

De igual modo, haz una clase de prueba que lea líneas de dos ficheros y las imprima en orden en pantalla. Por ejemplo, si el primer fichero tiene dos lineas "A" y "B" y el segundo fichero contiene dos líneas "C" y "D", debe imprimir "A", "B", "C" y "D". La solución debe utilizar internamente una cola.

Homework Section2. Actividades para casa

Objetivo

Profundizar en el manejo de estructuras de datos listas.

Ejercicio

La clase Lista representa una colección lineal de datos organizados en forma de lista enlazada. Esta lista presenta la peculiaridad de que almacena una referencia a un nodo concreto de la lista, al que apunta la referencia posicion, sobre el cual se realizan las operaciones de inserción y extracción de datos.

La referencia posicion debe poder avanzar y retroceder por la lista posición a posición. Por ello, resulta adecuado que la lista está doblemente enlazada, esto es, que cada nodo guarde una referencia no sólo al nodo que lo sigue en la lista, sino también al nodo que lo precede. La siguiente figura ilustra la estructura de la lista con un ejemplo:

Las operaciones básicas que debe permitir realizar esta lista son las siguientes:

  1. Avanzar la referencia posicion: la referencia se mueve hacia delante tantas posiciones como se indique. Si la lista está vacía o el número de posiciones a avanzar no es mayor que cero, no se hace nada. Si se pide avanzar más posiciones de las que quedan en la lista, posicion avanzará sólo hasta el último nodo. Si posicion apunta a null antes de avanzar, se coloca en el primer nodo de la lista, y a continuación se avanza el número de posiciones indicado, descontando una (por ejemplo, si se pide avanzar 5 posiciones y posicion apunta a null inicialmente, primero se coloca apuntando al primer nodo, y después se avanzan 4 posiciones desde este).

  2. Retroceder la referencia posicion: la referencia posicion debe retroceder tantas posiciones como se indique. Si la lista está vacía o el número de posiciones a retroceder no es mayor que cero, no se hace nada. Si se pide retroceder más posiciones que el primer elemento de la lista, la referencia se quedará en este primer elemento.

  3. Insertar un nuevo dato en la lista: se inserta un nuevo nodo para guardar este dato, inmediatamente a continuación de posicion, esto es, el nodo nuevo seguirá al actualmente referenciado por posicion. Cuando posicion es null, el nuevo nodo se inserta en la primera posición de la lista. Al finalizar la inserción, la referencia posicion debe apuntar al nuevo nodo introducido.

  4. Extraer un dato de la lista: devuelve el dato del nodo apuntado por posicion, borra dicho nodo, y avanza posicion al siguiente nodo (queda apuntando a null si no hay siguiente nodo). Si posicion apunta a null, no se extrae nada y se devuelve null.

Programa la clase Nodo, la clase Lista y los siguientes métodos de ésta:

  1. public void avanzar(int posiciones) {...}

  2. public void retroceder(int posiciones) {...}

  3. public void insertar(Object dato) {...}

  4. public Object extraer() {...}

Objetivo

Aprender a trabajar con Deques (Bicolas).

Ejercicio

Una Deque, también conocida como Bicola, es una estructura lineal de datos que permite insertar y eliminar elementos por ambos extremos. Para su construcción, nos basaremos en el uso de una Lista Doblemente Enlazada (LDE) en la que implementaremos los métodos correspondientes para lograr dicho comportamiento.

El comportamiento de una Deque se puede lograr mediante la implementación de la siguiente interfaz que muestra sus métodos principales:

/**
 * Interface for a Deque.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Dqueue {

  void insertFirst(Object obj);

  void insertLast(Object obj);

  Object removeFirst();

  Object removeLast();

  int size();
}

Para implemetar una Deque mediante una LDE realiza las siguientes tareas:

  1. Programa la clase DNode que constituye el nodo de una Lista Doblemente Enlazada (LDE). Dicho nodo contendrá las referencias prev y next a los nodos anterior y posterior de la misma, así como una referencia de tipo Object al dato que se almacena.

  2. Declara la clase DLDqueue que implementará una Deque basada en una LDE. Para ello, deberá implementar el interfaz Dqueue mencionado anteriormente.

  3. Añade los atributos head y tail que representan los nodos extremos de la LDE y el atributo entero size que permite almacenar el tamaño de la misma.

  4. Programa el constructor de la clase DLDqueue que inicializa las referencias head y tail a un nodo de la LDE que esté vacío y establece el tamaño a 0.

  5. Programa los siguientes métodos del interfaz Deque:

    • public void insertFirst(Object obj)

      Este método inserta un objeto al comienzo de la LDE.

    • public void insertLast(Object obj)

      Este método inserta un objeto al final de la LDE.

    • public Object removeFirst()

      Este método extrae un objeto del comienzo de la LDE y lo elimina de la lista. Si no existe dicho objeto, devuelve null.

    • public Object removeLast()

      Este método extrae un objeto del final de la LDE y lo elimina de la lista.Si no existe dicho objeto, devuelve null.

    • public int size()

      Este método devuelve el tamaño de la lista LDE.

  6. Por úlitmo, implementa el método public String toString() que permite imprimir el contenido de la Deque por pantalla con el siguiente formato (los valores que aparecen son de ejemplo):

    head [ 1-2-3-4-5 ] tail

¡¡ NOTA IMPORTANTE !!

En este ejercicio, hemos practicado el diseño y la implementación de una Deque. Sin embargo, en el API de Java existen clases que también implementan este tipo de estructuras de datos. Una Deque está definida por la siguiente interfaz: Interface Deque. Existen dos posibles implementaciones de la misma, una basada en arrays (ArrayDeque) y otra basada en Listas Enlazadas (LinkedList).

Objetivo

Aprender cómo hacer que una Deque se comporte como una Pila o una Cola.

Ejercicio

En este ejercicio, vamos a aprovechar la flexibilidad de una Deque para hacer que se comporte como si fueran una Pila o una Cola. Para hacerlo, obligaremos a que la clase que la use implemente el interfaz correspondiente que se muestra a continuación:

  • Interfaz de una Pila:

    /**
 * Interface for a Stack.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Stack {

  void push(Object obj);

  Object pop();

  int size();
}

  • Interfaz de una Cola:

    /**
 * Interface for a Queue.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Queue {

  public void enqueue(Object obj);

  public Object dequeue();

  int size();
}

A continuación, vamos a usar una Deque para implementar tanto una Pila como una Cola de datos. Para ello, realiza las siguientes tareas:

  • Para implemetar una Pila mediante una Dqueue:

    1. Declara la clase DQStack que se comportará como una Pila. Para ello deberá implementar el interfaz Stack mencionado anteriormente.

    2. Añade un atributo data que sea de tipo DLDqueue y que constituye la lista donde se almacenarán los datos de la pila.

    3. Programa el constructor de la clase DQStack que inicializa el atributo data creando un objeto de la clase DLDqueue.

    4. Programa los siguientes métodos del interfaz Stack:

      • public void push(Object obj)

        Este método inserta un objeto al comienzo de la DLDqueue.

      • public Object pop()

        Este método extrae un objeto del comienzo de la DLDqueue y lo elimina de la lista. Si no existe dicho objeto, devuelve null.

      • public int size()

        Este método devuelve el tamaño de la DLDqueue.

    5. Implementa el método main para probar la Pila. Deberá crear una instancia de una DQStack, apilar y desapilar una serie de datos imprimiendo por pantalla el contenido y el tamaño de la pila.

  • Para implemetar una Cola mediante una DLDqueue se pide:

    1. Declara la clase DQQueue que debe comportarse como una Cola. Para ello deberá implementar el interfaz Queue proporcionado.

    2. Añade un atributo data que sea de tipo DLDqueue y que constituye la lista donde se almacenarán los datos de la cola.

    3. Programa el constructor de la clase DQQueue que inicializa el atributo data creando un objeto de la clase DLDqueue.

    4. Programa los siguientes métodos del interfaz Queue:

      • public void enqueue(Object obj)

        Este método inserta un objeto al comienzo de la DLDqueue.

      • public Object dequeue()

        Este método extrae un objeto del final de la DLDqueue y lo elimina de la lista.Si no existe dicho objeto, devuelve null.

      • public int size()

        Este método devuelve el tamaño de la DLDqueue.

    5. Por último, implementa el método main para probar la Cola. Dicho método deberá crear una instancia de una DQQueue, encolar y desencolar una serie de datos imprimiendo por pantalla el contenido y el tamaño de la lista.