本題來自程序員代碼面試指南

實現(xiàn)一種狗貓隊列的結(jié)構(gòu)，要求如下：

●　用戶可以調(diào)用add方法將cat類或dog類的實例放入隊列中；

●　用戶可以調(diào)用pollAll方法，將隊列中所有的實例按照進隊列的先后順序依次彈出；

●　用戶可以調(diào)用pollDog方法，將隊列中dog類的實例按照進隊列的先后順序依次彈出；

●　用戶可以調(diào)用pollCat方法，將隊列中cat類的實例按照進隊列的先后順序依次彈出；

●　用戶可以調(diào)用isEmpty方法，檢查隊列中是否還有dog或cat的實例；

●　用戶可以調(diào)用isDogEmpty方法，檢查隊列中是否有dog類的實例；

●　用戶可以調(diào)用isCatEmpty方法，檢查隊列中是否有cat類的實例

這個題的用雙隊列實現(xiàn)，要解決的關(guān)鍵點是如何判斷倆個隊列的隊頭元素入隊的先后。解決的方法是擴展寵物類，加上計數(shù)器（時間戳）來判斷入隊的先后（不能改變原來的類，我覺得這個題更加側(cè)重的是面向?qū)ο髷U展的思想）

public class DogCatQueue {
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue() {
        this.dogQ = new LinkedList<PetEnterQueue>();
        this.catQ = new LinkedList<PetEnterQueue>();
        this.count = 0;//計數(shù)器
    }

    /**
     * 添加操作
     * @param pet
     */
    public void add(Pet pet) {
        if (pet.getPetType().equals("dog")) {
            this.dogQ.add(new PetEnterQueue(pet, this.count++));
        } else if (pet.getPetType().equals("cat")) {
            this.catQ.add(new PetEnterQueue(pet, this.count++));
        } else {
            throw new RuntimeException("添加的既不是貓也不是狗");
        }
    }

    /**
     * 返回隊頭對象
     * @return
     */
    public Pet pollAll() {
        if (! this.dogQ.isEmpty() && ! this.catQ.isEmpty()) {
            if(this.dogQ.peek().getCount()  <  this.catQ.peek().getCount()) {
                return this.dogQ.poll().getPet();
            } else {
                return this.catQ.poll().getPet();


            }
        } else if (! this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else if (! this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("隊列是空的");
        }
    }

    /**
     * 返回隊頭的狗
     * @return
     */
    public Dog pollDog() {
        if (! this.isDogQueueEmpty()) {
            return (Dog) this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("狗隊列為空");
        }
    }

    public Cat pollCat() {
        if (! this.isCatQueueEmpty()) {
            return (Cat) this.catQ.poll().getPet();
        } else
            throw new RuntimeException("貓隊列為空");
    }

    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 class Pet {
    private String type;

    public Pet(String type) {
        this.type = type;
    }

    public String getPetType() {
        return this.type;
    }
}

public class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}

public class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}

public class PetEnterQueue {
    private Pet pet;
    private long count;

    public PetEnterQueue(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return this.pet;
    }

    public long getCount() {
        return this.count;
    }

    public String getEnterPetType() {
        return this.pet.getPetType();
    }
}

最后附上github地址