cc156_3.7

gistfile1.java

package cc150;
/*
 * 3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in,
first out" basis. People must adopt either the "oldest" (based on arrival time) of
all animals at the shelter, or they can select whether they would prefer a dog or
a cat (and will receive the oldest animal of that type). They cannot select which
specificanimal they would like. Create the data structures to maintain this system
and implement operations such as enqueue, dequeueAny, dequeueDog and
dequeueCat.You may use the built-in LinkedList data structure.
Algorithm:
use two queues  for dog   and cat  
 and  a property flag   as   the item enter queue sequence

 */
public class CatAndDogQueue_3_7 {

	public static void main(String[] args) {
		DogAndCatQueue testQ = new DogAndCatQueue();
		testQ.EnQueue("Cat", "cat1");
		testQ.EnQueue("Cat", "cat2");
		testQ.EnQueue("Dog", "dog3");
		testQ.EnQueue("Cat", "cat4");
		testQ.EnQueue("Dog", "dog5");
		testQ.EnQueue("Dog", "dog6");
		testQ.EnQueue("Dog", "dog7");
		testQ.EnQueue("Dog", "dog8");
		testQ.EnQueue("Cat", "cat9");
		System.out.println(testQ.DeQueueAny().name);
		System.out.println(testQ.DeQueueDog().name);
		System.out.println(testQ.DeQueueCat().name);
		System.out.println(testQ.DeQueueDog().name);
		System.out.println(testQ.DeQueueCat().name);
		System.out.println(testQ.DeQueueDog().name);
		System.out.println(testQ.DeQueueCat().name);
		AnimalNode result = testQ.DeQueueCat();
		if(result == null)
			System.out.println("there is no more  Cat");
	}

}

class DogAndCatQueue  {
	BaseQueue dogQueue;
	BaseQueue catQueue;
	int mainSequnece;
	public DogAndCatQueue(){
		
		dogQueue = new BaseQueue();
		catQueue = new BaseQueue();
		mainSequnece =0;
	}
	public void EnQueue(String type,String name){
		if(type.equals("Dog") || type.equals("Cat")){
			 
			if(type.equals("Cat")){
				catQueue.EnQueue(type,name,++mainSequnece);
			}
			else {
				dogQueue.EnQueue(type,name,++mainSequnece);
			}
			
		}
	}
	public AnimalNode  DeQueueAny(){
		int dogSeq = dogQueue.getEarliestSequence();
		int catSeq = catQueue.getEarliestSequence();
		 
			if(catSeq < dogSeq){
				return catQueue.DeQueue();
			}
			else if(catSeq > dogSeq){
				return dogQueue.DeQueue();
			}
		 
		return null;
	}
	public AnimalNode DeQueueCat(){
		return catQueue.DeQueue();
		
	}
	public AnimalNode DeQueueDog(){
		return dogQueue.DeQueue();
		
	}
}

class AnimalNode{
	String type; // dog or cat
	String name;
    int sequence;
	AnimalNode next;
	public AnimalNode(String type,String name,int seq){
		this.type = type;
		this.name = name;
		this.sequence = seq;
		 
	}
}

class BaseQueue {
	AnimalNode head;
	AnimalNode rear;
	public BaseQueue(){
		head  =  null;
		rear = null;
	}
	public void EnQueue(String type ,String name,int seq)
	{
		AnimalNode newNode = new AnimalNode(type,name,seq);
		if(head ==null){
			head = newNode;
			rear = newNode;
		}
		else{
			rear.next = newNode;
			rear = newNode;
		}
		
	}
	public  AnimalNode DeQueue(){
		if(head !=null){
			AnimalNode deNode =  head;
			head =head.next;
			return  deNode;
		}
		return null;
	}
	public int getEarliestSequence(){
		if(head != null)
			return head.sequence;
		else 
			return Integer.MAX_VALUE;
	}
}