Universidad Carlos III de Madrid

We are modelling the reception and process of purchase orders in a company. Let's suppose that the company makes only one product. The company receives orders from different customers. Every order has two characteristics: customer and units of product. The orders are processed by order (FIFO). Below, you can download the definition of (class Order). 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;
		}
}

	  

Implement the Queue class that implements the following interface:

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();
} 

	

To do it, implement also the Node class that represents each node in the linked queue. Every node will have 2 references: one to the next node in the list, and one to the element attached to that node.

Implement a TestQueue class with a main to test the code.

To better test the code, add a new method printInfo() to the Queue class. This method should print the size of the queue and should go from first element to last one and present the data contained inside each order, by using the print() method from Order class. That is, it should present something similar to:

********* 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                              
     ------------                              
******************************                 

The program has to walk the linked list in order to show its elements. It begins with the first node, then the second node is reached through the next reference in the first one, then the third node, and so on until the end of the list is reached. The code for that should be something like:

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

In the main method, create a new queue and, at least, 3 new orders. Add them to the queue and test the methods front and dequeue. To better check the effect, after every insertion or deletion, use the printInfo method.

Once we feel comfortable with a very simple queue, we will make it a little bit complex: Implement a method to obtain the n-th element, without deleting it. It must return null if the position is not valid. public Object getNth(int pos) To test it, try to add 4 elements and obtain the third one.

Move the reference position forwards: the reference is moving forwards as many positions as indicated. If the list is empty or the number of positions to move forwards is not greater than zero, nothing is done. If it is required to move it forwards more positions than number of nodes from the current position up until the end of the list, advance currentPosition only until the last node. If currentPosition points to null before proceeding, it is first placed pointing to the first node of the list, and then moved forwards the specified number of positions minus one (for example, if it is required to move 5 positions forwards and currentPosition points initially to null, then currentPosition is first placed pointing to the first node, and then moved 4 positions from this first one).

Move the currentPosition reference backwards: the reference currentPosition must go backwards as many positions as indicated. If the list is empty or the number of positions to move backwards is not greater than zero, nothing is done. If it is required to move backwards more positions than number of nodes from the current position up until the first node of the list, the reference will remain in this first node.

Insert new data in the list: a new node is inserted to save this data, immediately following currentPosition, i.e. the new node will follow the node currently referenced by currentPosition. When currentPosition is null, the new node is inserted into the top of the list. After the insertion, currentPosition must point to the new node inserted.

Extracting data from the list: return the data pointed by currentPosition, delete the node, and moves currentPosition to the next node (currentPosition will point to null if there is no next node). If currentPosition is pointing to null, nothing is extracted and null is returned.

public void moveForwards(int numPositions) {...}

public void moveBackwards(int numPositions) {...}

public void insert(Object data) {...}

public Object extract() {...}

Program the DNode class which represents the node of a Double Linked List (DLL). Such node will contain both prev and next references to the previous and next node of the current one, as well as an Object reference to the data to be stored.

Declare the DLDqueue class that will implement a Deque based on a DLL. In order to do this, it must implement the Dqueue interface that has been previously mentioned.

Add the head and tail attributes that represents the nodes at both ends of the DLL and the integer attribute size that permits to store the size of it.

Program the constructor of the DLDqueue class that initializes the head and tail references to an emtpy DLL node and set the size to 0.

Program the following methods of the Dqueue's interface:

Finally, implement the public String toString() method that permits to print the content of the Deque on console according the next format (the shown values are examples):

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