猫狗队列.md

猫狗队列

题目

宠物、狗和猫的类如下：
public class Pet { private String type;
public Pet(String type) { this.type = type; }
public String getPetType() { return this.type; }}
public class Dog extends Pet { public Dog() { super("dog"); } }
public class Cat extends Pet { public Cat() { super("cat"); } }

实现一种狗猫队列的结构，要求如下：
用户可以调用add方法将cat类或dog类的实例放入队列中；
用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；
用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；
用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

代码

PHP

// 宠物类
class Pet
{
    public $type;

    public function __construct($type)
    {
        $this->type = $type;
    }
}

// 猫类
class Cat extends Pet
{
    public function __construct()
    {
        parent::__construct('cat');
    }
}

// 狗类
class Dog extends Pet
{
    public function __construct()
    {
        parent::__construct('dog');
    }
}

// 为了不改变原来的猫狗类, 下面定义一个新类, 给猫狗类增加一个成员属性count
class PetEnter
{
    public $pet;
    public $count;

    public function __construct(Pet $pet, $count)
    {
        $this->pet = $pet;
        $this->count = $count;
    }
}

// 新的队列, 存放猫和狗两个队列, 还有一个递增的计数器
class CatDogQueue
{
    public $catQ;
    public $dogQ;
    public $count;

    public function __construct()
    {
        $this->catQ = new SplQueue();
        $this->dogQ = new SplQueue();
        $this->count = 0;
    }

    // 入队
    public function enqueue(Pet $pet)
    {
        if ($pet->type == 'cat') {
            $this->catQ->enqueue(new PetEnter($pet, $this->count++));
        } else if ($pet->type == 'dog') {
            $this->dogQ->enqueue(new PetEnter($pet, $this->count++));
        } else {
            throw new Exception('err, not dog or cat');
        }
    }

    // 出队
    public function dequeue()
    {
        if (!$this->catQ->isEmpty() && !$this->dogQ->isEmpty()) {
            if ($this->catQ->top()->count < $this->dogQ->top()->count) {
                return $this->catQ->dequeue()->pet;
            } else {
                return $this->dogQ->dequeue()->pet;
            }
        } elseif (!$this->catQ->isEmpty()) {
            return $this->catQ->dequeue()->pet;
        } elseif (!$this->dogQ->isEmpty()) {
            return $this->dogQ->dequeue()->pet;
        } else {
            throw new Exception('err, queue is empty!');
        }
    }

    public function pollCat()
    {
        if ($this->catQ->isEmpty()) {
            throw new Exception('err, queue is empty!');
        }

        return $this->catQ->dequeue()->pet;
    }

    public function pollDog()
    {
        if ($this->dogQ->isEmpty()) {
            throw new Exception('err, queue is empty!');
        }

        return $this->dogQ->dequeue()->pet;
    }

    public function isEmpty()
    {
        return $this->catQ->isEmpty() && $this->dogQ->isEmpty();
    }

    public function isCatQueueEmpty()
    {
        return $this->catQ->isEmpty();
    }

    public function isDogQueueEmpty()
    {
        return $this->dogQ->isEmpty();
    }
}

// Test
$queue = new CatDogQueue;
$cat1 = new Cat;
$dog1 = new Dog;
$cat2 = new Cat;
$dog2 = new Dog;

$queue->enqueue($cat1);
$queue->enqueue($dog1);
$queue->enqueue($cat2);
$queue->enqueue($dog2);

// cat
echo $queue->dequeue()->type;
// dog
echo $queue->pollDog()->type;
// dog
echo $queue->pollDog()->type;
// cat
echo $queue->dequeue()->type;

JAVA

import java.util.LinkedList;
import java.util.Queue;

public class CatDogQueue {
	
	// 宠物类
	public static class Pet {
		private String type;
		
		public Pet(String type) {
			this.type = type;
		}
		
		public String getPetType() {
			return this.type;
		}
	}
	
	// 猫类
	public static class Cat extends Pet {
		public Cat() {
			super("cat");
		}
	}
	
	// 狗类
	public static class Dog extends Pet {
		public Dog() {
			super("dog");
		}
	}
	
	// 为了不改变原来的猫狗类, 下面定义一个新类, 给猫狗类增加一个成员属性count
	public static class PetEnter {
		// 猫 or 狗
		private Pet pet;
		// 计数器
		private long count;
		
		public PetEnter(Pet pet, long count) {
			this.pet = pet;
			this.count = count;
		}
		
		public Pet getPet() {
			return this.pet;
		}
		
		public long getCount() {
			return this.count;
		}
		
		public String getPetType() {
			return this.pet.getPetType();
		}
	}
	
	// 新的队列, 存放猫和狗两个队列, 还有一个递增的计数器
	public static class NewQueue {
		private Queue<PetEnter> catQ;
		private Queue<PetEnter> dogQ;
		private long count;
		
		public NewQueue() {
			this.dogQ = new LinkedList<PetEnter>();
			this.catQ = new LinkedList<PetEnter>();
			this.count = 0;
		}
		
		// 入队
		public void enqueue(Pet pet) {
			if (pet.getPetType().equals("dog")) {
				this.dogQ.add(new PetEnter(pet, this.count++));
			} else if (pet.getPetType().equals("cat")) {
				this.catQ.add(new PetEnter(pet, this.count++));
			} else {
				throw new RuntimeException("err, not dog or cat");
			}
		}
		
		// 出队
		public Pet dequeue() {
			if (!catQ.isEmpty() && !dogQ.isEmpty()) {
				// 比较猫狗的计数器
				if (catQ.peek().getCount() < dogQ.peek().getCount()) {
					return catQ.poll().getPet();
				} else {
					return dogQ.poll().getPet();
				}
			} else if (!catQ.isEmpty()) {
				return catQ.poll().getPet();
			} else if (!dogQ.isEmpty()) {
				return dogQ.poll().getPet();
			} else {
				throw new RuntimeException("err, queue is empty!");
			}
		}
		
		public Dog pollDog() {
			if (!this.isDogQueueEmpty()) {
				return (Dog) this.dogQ.poll().getPet();
			} else {
				throw new RuntimeException("Dog queue is empty!");
			}
		}

		public Cat pollCat() {
			if (!this.isCatQueueEmpty()) {
				return (Cat) this.catQ.poll().getPet();
			} else
				throw new RuntimeException("Cat queue is empty!");
		}

		public boolean isEmpty() {
			return this.dogQ.isEmpty() && this.catQ.isEmpty();
		}

		public boolean isDogQueueEmpty() {
			return this.dogQ.isEmpty();
		}

		public boolean isCatQueueEmpty() {
			return this.catQ.isEmpty();
		}	
	}
	
	public static void main(String[] args) {
		NewQueue queue = new NewQueue();;
		
		Pet cat1 = new Cat();
		Pet dog1 = new Dog();
		Pet cat2 = new Cat();
		Pet dog2 = new Dog();
		
		queue.enqueue(cat1);
		queue.enqueue(dog1);
		queue.enqueue(cat2);
		queue.enqueue(dog2);
		
		// cat
		System.out.println(queue.dequeue().getPetType());
		System.out.println(queue.pollDog().getPetType());
		System.out.println(queue.pollDog().getPetType());
		System.out.println(queue.dequeue().getPetType());
	}
}