Universidad Carlos III de Madrid

Vamos a modelar el proceso de recepción de pedidos en una empresa. Supongamos que la empresa sólo fabrica un producto; a la empresa llegan pedidos de distintos clientes; cada pedido contiene dos características: cliente y cantidad de producto; y los pedidos se procesan por orden de llegada. Se entrega la definición de la clase Order, que representa un pedido. Order.java

public class Order {
        private String customer;
	private int qtty;
		public Order(int qtty, String customer) {
			this.customer=customer;
			this.qtty = qtty;
		}
		public void print (){
			System.out.println("     Customer: " + this.getCustomer());
			System.out.println("     Quantity: " + this.getQtty());
			System.out.println("     ------------");
		}
		public int getQtty(){
			return this.qtty;
		}
		public String getCustomer(){
			return this.customer;
		}
}

	  

Programa la clase Queue, basada en una lista enlazada, que implemente la siguiente interfaz:

public interface QueueInterface {

    // returns the number of elements in Queue
    public int size();                   

    // verifies if the Queue is empty. true if empty | false if not empty.
    public boolean isEmpty();

    // returns the first element in Queue. The element IS NOT REMOVED from Queue. Returns null if empty.
    public Object front();

    // adds a new element to the Queue.
    public void enqueue(Object info);
 
    // returns the first element in Queue. The element IS REMOVED from Queue. Returns null if empty.
    public Object dequeue();
} 

	

Para ello, define la clase Node, que representa cada uno de los nodos de la lista enlazada. Cada nodo tendrá 2 referencias: una referencia al siguiente nodo de la lista (o null si es el último) y una referencia al objeto que realmente contiene.

Construye una clase TestQueue con un main para probar la cola definida.

Para poder probar mejor los desarrollos, añade un método printInfo() en la clase Queue, que presente en consola el número de elementos que contiene y recorra la cola presentando la información de cada uno de los elementos, usando el método print() de la clase Order. Es decir, que presente una información parecida a:

********* QUEUE DUMP *********                 
   Size: 4                                     
   ** Element 1                                
     Customer: cust1                           
     Quantity: 20                              
     ------------                              
   ** Element 2                                
     Customer: cust2                           
     Quantity: 30                              
     ------------                              
   ** Element 3                                
     Customer: cust3                           
     Quantity: 40                              
     ------------                              
   ** Element 4                                
     Customer: cust3                           
     Quantity: 50                              
     ------------                              
******************************                 

Para imprimir los elementos de la lista, es necesario que el programa recorra la lista. Para ello debe comenzar por el primer nodo, pasar al segundo a través de su referencia next, después al tercero y así sucesivamente mientras no se llegue al final de la lista. El código se debería parecer a lo siguiente:

Node node = top;
while (node != null) {
  // print here the information of the node
  (...)
  node = node.getNext();
}

En el main, crea una nueva cola y crea al menos 3 pedidos. Añádelos a la cola y prueba los métodos front y dequeue. Para ver el efecto en cada caso, tras cada operación de inserción y extracción, invoca el método printInfo de la cola.

Una vez tenemos cierta soltura con el manejo normal de una cola simple, vamos a complicarla un poco: Define un método para obtener el n-ésimo elemento de la cola (sin borrarlo). Debe devolver null si se pide una posición no válida. public Object getNth(int pos) Prueba a introducir cuatro elementos y obtener el tercero.

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).

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.

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.

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.

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

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

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

public Object extraer() {...}

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.

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

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.

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.

Programa los siguientes métodos del interfaz Deque:

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