Listas Enlazadas, Pilas y Colas

Tabla de contenidos

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

1.1. Implementación de una cola con listas enlazadas
1.2. Robot de exploración de Saturno

2.1. Implementación de una pila con listas enlazadas
2.2. Robot avanzado exploración de Saturno

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

1.1. Implementación de una cola con listas enlazadas

El objetivo general de esta práctica es aprender a implementar y utilizar pilas y colas en Java. Para ello, seguiremos una implementación basada en listas enlazadas.

Programa la clase LinkedQueue que implementa la interfaz Queue, cuyo código se muestra a continuación:

public interface Queue<E> {
    boolean isEmpty();
    int size();
    void enqueue (E info);
    E dequeue();
    E front();
}

Utiliza internamente en tu implementación la clase Node.java con la que ya has trabajado en la práctica anterior. Si no dispones de ella, puedes utilizar el siguiente código:

public class Node<E> {
    private E info;
    private Node<E> next;

    public Node() {
        info = null;
        next = null;
    }

    public Node(E info) {
        setInfo(info);
    }

    public Node(E info, Node<E> next) {
        setInfo(info);
        setNext(next);
    }

    public E getInfo() {
        return info;
    }

    public void setInfo(E info) {
        this.info = info;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

1.2. Robot de exploración de Saturno

La ESA está desarrollando un proyecto para colocar un robot de exploración sobre la superficie de Saturno. Dado el retardo de comunicaciones existente entre La Tierra y Saturno, el robot debe ser capaz de realizar exploraciones de forma autónoma. Por ello, además del control remoto desde la Tierra, cuenta con el apoyo de un complejo sistema de inteligencia artificial (IA) que se ejecuta en el propio robot.

Desde la Tierra se programan los siguientes movimientos que debe hacer el robot y se le envían. El robot los guarda en una cola de movimientos pendientes. Cada vez que el módulo de IA considere que es pertienente continuar con la exploración, desencola la siguiente orden de movimiento y la lleva a cabo.

El robot será capaz de realizar dos tipos de movimientos básicos: desplazamientos (avanzar o retroceder) y rotaciones sobre su vertical (derecha o izquierda). Para realizar un desplazamiento es necesario especificar la distancia (entero que representa centímetros, negativo para retroceder). Para realizar una rotación es necesario especificar el ángulo (entero que representa grados, negativo hacia la izquierda). Los movimientos se representan con la siguiente clase:

public class Movement {

    public final static short DISPLACEMENT = 1;
    public final static short ROTATION = 2;

    private short type;
    private int magnitude;

    public Movement(short type, int magnitude) {
        this.type = type;
        this.magnitude = magnitude;
    }

    public String toString() {
        if (type == DISPLACEMENT) {
            return "DSP " + magnitude;
        } else if (type == ROTATION) {
            return "ROT " + magnitude;
        } else {
            return "ERR";
        }
    }

    public short getType() {
        return type;
    }

    public int getMagnitude() {
        return magnitude;
    }

    public Movement reverse() {
        return new Movement(type, -magnitude);
    }
}

Apartado 1

Formas parte del equipo de ingenieros de la ESA. Se te ha encargado programar la clase MovementProgrammer, que debe registrar en una cola los movimientos solicitados desde la Tierra, y se los proporcionará al módulo de IA del robot según este los vaya pidiendo. Programa la clase MovementProgrammer, incluyendo sus atributos y un constructor sin parámetros. Además, esta clase debe proporcionar los siguientes métodos:

void program(Movement m): invocada por el control de la Tierra para añadir a la cola de movimientos un nuevo movimiento.
Movement next(): devuelve el siguiente movimiento básico a realizar por el robot, que se extrae de la cola de movimientos. Devuelve null si la cola está vacía. El módulo de IA invoca a este método cada vez que está preparado para realizar un nuevo movimiento.
int numMovements(): devuelve el número de movimientos almacenados en la cola de movimientos.
void reset(): elimina todos los movimientos pendientes, dejando la cola de movimientos en su estado inicial.

Apartado 2

Para probar el programador de movimientos debes escribir un pequeño programa interactivo en línea de comandos. El programa estará en un bucle continuo en que lee un comando de la entrada estándar y lo lleva a cabo. Los comandos que puede introducir el usuario son:

displace magnitude: programa un nuevo movimiento de desplazamiento con la magnitud dada. Por ejemplo: displace -30.
rotate magnitude: programa un nuevo movimiento de rotación con la magnitud dada. Por ejemplo: rotate 90.
execute: ejecuta el siguiente movimiento.
state: indica el número de movimientos que se encuentran programados actualmente.
reset: elimina los movimientos pendientes que permanezcan en la cola de movimientos.
exit: finaliza el programa.

A continuación se muestra una sesión de uso del programa a modo de ejemplo:

C:\Users\Alumno>java TestMovementProgrammer
> displace 10
Programmed: DSP 10
> rotate 45
Programmed: ROT 45
> displace -5
Programmed: DSP -5
> rotate -45
Programmed: ROT -45
> displace 40
Programmed: DSP 40
> execute
Executed: DSP 10
> state
Movements remaining: 4
> rotate 20
Programmed: ROT 20
> displace -10
Programmed: DSP -10
> execute
Executed: ROT 45
> execute
Executed: DSP -5
> execute
Executed: ROT -45
> state
Movements remaining: 3
> execute
Executed: DSP 40
> execute
Executed: ROT 20
> execute
Executed: DSP -10
> state
Movements remaining: 0
> execute
ERROR: empty movements queue
> salir
ERROR: syntax error
> exit

Puedes partir del siguiente código que se te proporciona a modo de ayuda. Asegúrate de entenderlo antes de empezar a modificarlo:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class TestMovementProgrammer {

    public static void main(String[] args) throws IOException {
        MovementProgrammer programmer = (...)
        boolean exit = false;
        BufferedReader input = new BufferedReader(
                                   new InputStreamReader(System.in));
        while (!exit) {
            System.out.print("> ");
            String command = input.readLine();
            if (command != null) {
                String[] parts = command.trim().split("\\s");
                if (parts.length == 1 && parts[0].equals("exit")) {
                    (...)
                } else if (parts.length == 2 && parts[0].equals("displace")) {
                    (...)
                } else (...)
                (...)
            } else {
                exit = true;
            }
        }
    }
}

2. Actividades para casa

2.1. Implementación de una pila con listas enlazadas

Apartado 1

Programa la clase LinkedStack que implementa la interfaz Stack que se muestra a continuación:

public interface Stack<E> {
    boolean isEmpty();
    int size();
    void push (E info);
    E pop();
    E top();
}

2.2. Robot avanzado exploración de Saturno

Cuando el módulo de IA del robot de la ESA en Saturno detecta que ha acabado en una posición comprometida, puede decidir deshacer sus últimos movimientos para volver a una posición anterior que considere segura. Para ello necesita utilizar un programador de movimientos más avanzado que permita deshacer los movimientos ejecutados más recientemente en orden inverso, de una forma similar a como funciona la operación de deshacer en un editor de textos.

Apartado 1

Programa una clase llamada AdvancedMovementProgrammer que herede de la clase MovementProgrammer del ejercicio anterior. Esta clase incorpora las siguientes novedades con respecto al programador de MovementProgrammer:

Dispone, además de la cola de movimientos, de una pila donde almacena cada movimiento realizado (con el más reciente en la cima de la pila). Cada vez que el método next() devuelva un movimiento distinto de null este debe ser almacenado en la pila.
Proporciona un método adicional Movement undo() que devuelve el movimiento que permita deshacer el último movimiento realizado. Para ello retira el movimiento de la pila y devuelve su inverso. Por ejemplo, si el último movimiento realizado es "DSP 10", recupera este movimiento de la cima de la pila y devuelve su inverso: "DSP -10". Además, por seguridad, vacía la cola de movimientos pendientes, porque dichos movimientos podrían dejar de tener sentido una vez se ha deshecho un movimiento. En caso de que la pila de movimientos a deshacer esté vacía, debe devolver null y dejar la cola de movimientos sin modificar.
Proporciona un método adicional int numUndoableMovements() que devuelve el número de movimientos que se pueden deshacer en este momento, esto es, el tamaño de la pila.

Apartado 2

Partiendo del código de la clase TestMovementProgrammer, programa la clase TestAdvancedMovementProgrammer, que debe probar el funcionamiento de AdvancedMovementProgrammer. Este nuevo programa proporcionará los mismos comandos que el anterior y, además:

Añade el comando undo, que deshace el último movimiento realizado y muestra el movimiento inverso correspondiente.
Modifica el comando state para que indique tanto el número de movimientos programados en la cola como el número de movimientos que se pueden deshacer.

A continuación se muestra una sesión de uso del programa a modo de ejemplo:

C:\Users\Alumno>java TestAdvancedMovementProgrammer
> rotate 45
Programmed: ROT 45
> displace 10
Programmed: DSP 10
> state
Movements remaining: 2; undoable movements: 0
> execute
Executed: ROT 45
> execute
Executed: DSP 10
> state
Movements remaining: 0; undoable movements: 2
> undo
Executed: DSP -10
> displace 50
Programmed: DSP 50
> execute
Executed: DSP 50
> state
Movements remaining: 0; undoable movements: 2
> undo
Executed: DSP -50
> undo
Executed: ROT -45
> undo
ERROR: no movement to undo
> exit

Universidad Carlos III de Madrid

Grado en Ingeniería Telemática/Grado en Ingeniería de Sistemas de Comunicaciones

Enero-Mayo 2014