程序的两大支柱：数据结构与算法，来了解一下吧！

作者丨雨林沐风rzm

https://www.jianshu.com/p/622750145208

猫狗队列

注意：

查找了一些网上的写法，发现很多样本再处理pollAll pollDog pollCat方法的时候，并不是如下边的要求弹出所有，原因不详，以我对文字的

敏感性来说，这种只弹出一个的方式是错误的，奈何很多公司的算法题

答案也是如此，所以暂且先这样处理，你完全可以添加一个循环将所有

元素弹出

实现一种猫狗队列的结构，要求如下：

用户可以调用add方法将cat类或者dog类的实例放入队列中；

用户可以调用pollAll方法，将队列中所有的实例按照队列的先后顺序依次弹出；

用户可以调用pollDog方法，将队列中dog类的实例按照队列的先后顺序依次弹出；

用户可以调用pollCat方法，将队列中cat类的实例按照队列的先后顺序依次弹出；

用户可以调用isEmpty方法，检查队列中是否还有dog和cat的实例；

用户可以调用isDogEmpty方法，检查队列中是否还有do的实例；

用户可以调用isCatEmpty方法，检查队列中是否还有cat的实例。

public class CatDogQueue {

private LinkedList<PetHolder> dogs;

private LinkedList<PetHolder> cats;

private int order;

public CatDogQueue() {

dogs = new LinkedList<>();

cats = new LinkedList<>();

order = 0;

}

public void add(Pet pet) {

if ("cat".equals(pet.getPetType())) {

cats.add(new PetHolder(pet, order++));

} else if ("dog".equals(pet.getPetType())) {

dogs.add(new PetHolder(pet, order++));

}

}

public void pollAll() {

if (!dogs.isEmpty() && !cats.isEmpty()) {

if (dogs.peek().getOrder() < cats.peek().getOrder()) {

dogs.poll();

} else {

cats.poll();

}

} else if (!dogs.isEmpty()) {

dogs.poll();

} else if (!cats.isEmpty()) {

cats.poll();

}

}

public Dog pollDog() {

if (!dogs.isEmpty()) {

return (Dog) dogs.poll().getPet();

}

return null;

}

public Cat pollCat() {

if (!cats.isEmpty()) {

return (Cat) cats.poll().getPet();

}

return null;

}

public boolean isEmpty() {

return dogs.isEmpty() && cats.isEmpty();

}

public boolean isCatsEmpty() {

return cats.isEmpty();

}

public boolean isDogsEmpty() {

return dogs.isEmpty();

}

}

class Pet {

private String type;

public Pet(String type) {

this.type = type;

}

public String getPetType() {

return this.type;

}

}

class PetHolder {

private Pet pet;

private long order;

public PetHolder(Pet pet, long order) {

this.pet = pet;

this.order = order;

}

public Pet getPet() {

return this.pet;

}

public long getOrder() {

return this.order;

}

public String getEnterPetType() {

return this.pet.getPetType();

}

}

class Cat extends Pet {

public Cat() {

super("cat");

}

}

class Dog extends Pet {

public Dog() {

super("dog");

}

}

用两个栈实现队列，支持队列的基本操作(add,poll, peek)

简单分析：

1.先进先出，那么两个栈结合刚好满足这一点

2.两个栈顺序操作，全部添加到第一个栈之后，当要开始出的时候再往第二个栈中添加，从而保证先进先出的特性

​

简单分析：需要满足的要求大概如下：

1.先进后出

2.未进数据之前，为空，出完数据之后为空，所以如下实现中，pop使要保证两个stack都要pop干净

​

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序 的平均时间复杂度为O(NlogN),是冒泡排序的一种改进版。

注意，最外层的判断必不可少

​

冒泡排序

冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3.针对所有的元素重复以上的步骤，除了最后一个；

4.重复步骤1~3，直到排序完成。

​在工作中，见识了太多开口设计模式，闭口面向对象的人，在某个具体的问题上，问他为什么要用面向对象，为什么要用这样的设计模式，得到的回答相当空泛，有时候甚至是为了对象而对象，为了设计而设计。这样的人，做出来的设计，往往过度设计，似是而非，导致做出来的东西混乱不堪。

遇到的真正设计高手，还没有一个是对数据结构与算法是不精通的。让他讲为什么这样设计，为什么这样架构，他往往能深入浅出，将面向对象的思想、设计模式的考虑，与基础的数据结构和对应的算法结合起来，贴合问题的实际情况，给出良好的结论。

文章最后

怎么快速学C/C++，有什么方法，打算深入了解这个行业的朋友，可以加C/C++学习群：263515231，不管你是小白还是大牛，小编我都欢迎，不定期分享干货，包括小编自己整理的一份2019最新的C/C++资料和0基础入门教程，欢迎初学和进阶中的小伙伴。

每天晚上20:00我都会开直播给大家分享C/C++编程学习知识和路线方法，群里会不定期更新最新的教程和学习方法，大家都是学习C/C++的，或是转行，或是大学生，还有工作中想提升自己能力的前端党，如果你是正在学习C/C++的小伙伴可以加入学习。最后祝所有程序员都能够走上人生巅峰，让代码将梦想照进现实，非常适合新手学习，有不懂的问题可以随时问我，工作不忙的时候希望可以给大家解惑。

学习思路：

学习资料：