一、习题练习

（1）数组排序之后相邻的最大差值

• 题：给定一个整型数组arr,返回排序之后相邻的两个数最大差值

• 解题思路：这道题充分利用了桶的思想，这次的桶不是以数据的范围划分桶，而是以数据量划分，假如有N个数，那么就分N+1个桶，然后找出数据的的范围即最大值和最小值。把范围等分N+1份，比如范围1到9有五个桶那么一号桶为1-2范围，二号桶3-4范围。。。，一共N个数却有N+1个桶所以至少有一个桶为空的，空桶左边桶的最大值和右边桶最小值的差必然大于组内相减的差，那么证明了一件事，最大的差值必然不来自组内的差（注意并也不一定只来自空桶周围），所以最大的差值一定来自不相邻桶的差之一。

• 代码示例

public class MaxGap {
        public static int maxGap(int[] arr){
            
        if(arr==null||arr.length<2){
        return 0;
        }
        int length=arr.length;
        int max=arr[0];
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
        max=Math.max(max,arr[i]);
        min=Math.min(min,arr[i]);
        }
        if(max==min){
        return 0;
        }
        int index=0;
        boolean[] isHave=new boolean[length+1];
        int[] maxbuk=new int[length+1];
        int[] minbuk=new int[length+1];
        for(int i=0;i<length;i++){
        index=getIndex(length,arr[i],max,min);
        maxbuk[index]=isHave[index]?Math.max(maxbuk[index],arr[i]):arr[i];
        minbuk[index]=isHave[index]?Math.min(minbuk[index],arr[i]):arr[i];
        isHave[index]=true;
        }
        int lastMax=maxbuk[0];
        int res=0;
        for(int j=1;j<length+1;j++){
        if(isHave[j]){
        res=Math.max(res,minbuk[j]-lastMax);
        lastMax=maxbuk[j];
        }
        }
        return res;
        }
        public static int getIndex(int length,int number,int max,int min){
        return (int)((number-min)*length/(max-min));
        }
        }

(2)用数组实现栈结构

• 题：用数组实现一个大小固定的栈

• 解题思路：设立一个index指针指向要加入数组的位置，数组为空时指向0位置，当入栈时先判断index是否等于了数组的长度如果等于告知栈已满，如不等将数据存入index指向的位置，index+1；出栈判断index是否为零，若为零告知栈为空，若不为零范围index-1的位置的数，且index-1。peek操作（只查看栈顶不出栈）依旧检查栈是否为空，不空返回index-1位置的数，index不变。

• 代码示例

public class MyStack{
    int[] stack;
int index=0;
public MyStack(int initSize){
    stack=new int[initSize];
}


public void push(int number){
if(index==stack.length){
    System.out.print("满了");
throw new RuntimeException("已经满了");
}
stack[index++]=number;
}
public int pop(){
if(index==0){
throw new RuntimeException("已经空了");
}
return stack[--index];
}
public int peek(){
if(index==0){
throw new RuntimeException("已经空了");
}
return stack[index-1];
}
}

(3)用数组实现队列结构

• 题：用数组实现一个固定长度的队列

• 解题思路：首先设置一个end指针告诉加入的数据放在哪，在设置一个start指针告诉数据应该从哪取，再设置一个size负责记录当时队列里有几个数，当数据放进来时，首先查看size是否等于数组大小的，若等于说明队列是满的，告知用户已满，若不等于把数据放入到end指着的位置，然后判断end+1是否等于数组的length，若等于让end=0；若不等让end+1。当取数据时先判断size是否等于零，为零告知用户队列为空，不为零返回start指的位置的数，判断start+1是否等于数组的length，若等于让start=0；若不等让end+1。peek时检查是否为空，不为空返回start指的位置的数，不再做任何操作。

• 代码示例

public class MyQueue {
    
        int start=0;
        int end=0;
        int size=0;
        int[] queue;
        public MyQueue(int initSize){
        queue=new int[initSize];
        }
        public void push(int num){
        if(size==queue.length){
        throw new RuntimeException("队列已满");
        }
        queue[end]=num;
        end=end+1==queue.length?0:end+1;
        size++;
        }
        public int pop(){
        if(size==0){
        throw new RuntimeException("队列是空的");
        }
        int res=queue[start];
        size--;
        start=start+1==queue.length?0:start+1;
        return res;
        }
        public int peek(){
        if(size==0){
        throw new RuntimeException("队列是空的");
        }
        return queue[start];
        }
        }

(4)实现一个特殊的栈，在实现栈的最基本功能的基础上，在实现返回栈中最小元素的功能

• 题：要求pop,push,getMin操作的时间复杂度都是O(1),设计的栈结构可以使用现成的栈

• 解题思路：创建两个栈，其中一个栈用来保存数据叫dataStack，另一个用来保存最小值叫minStack。dataStack正常入栈出栈。minStack有两种方式操作：

1. 当入栈时如果minStack为空直接把数压进minStack里，如果不为空比较进来的数和minStack栈顶的数大小，如果进来的数小或等于压进栈minStack，如果大则不做任何操作。当出栈时，出栈的数和minStack栈顶的数比较大小，如果大minStack不做任何操作，如果等于minStack出栈。getmin方法就返回minStack栈顶的元素。这种方式比较省空间，但是出栈麻烦一些。

2. 当入栈时，若minStack为空，则直接压进minStack中，若不为空，和栈顶的数比较大小，如果大于栈顶把minStack栈顶的数重复压一遍，若小于等于直接压入栈中。当出栈时，和dataStack同步出栈就可以了。getmin方法就返回minStack栈顶的元素。这种方法稍微浪费空间，但出栈简单。

• 代码示例
  方案一

public class SpecialStack {
Stack<Integer> dataStack=new Stack<>();
Stack <Integer>minStack=new Stack<>();
public void push(int number) {
    dataStack.push(number);
    if(minStack.isEmpty()) {
        minStack.push(number);
    }else {
        int top=minStack.peek();
        if(number<=top) {
            minStack.push(number);
        }
    }
}
public int pop(){
    int popData=dataStack.pop();
    if(popData==minStack.peek()) {
        minStack.pop();
    }
    return popData;
}
public int getMin() {
    
    return minStack.peek();
}
}

方案二

public class SpecialStack2 {
Stack<Integer> dataStack=new Stack<>();
Stack <Integer>minStack=new Stack<>();
public void push(int number) {
    dataStack.push(number);
    if(minStack.isEmpty()) {
        minStack.push(number);
    }else {
        int top=minStack.peek();
        if(number<=top) {
            minStack.push(number);
        }else {
            minStack.push(top);
        }
    }
}
public int pop(){
    minStack.pop();
    return dataStack.pop();
}
public int getMin() {
    
    return minStack.peek();
}
}

(5)使用队列实现栈结构

• 题：使用队列实现栈结构

• 解题思路：准备两个队列queue1和queue2， 进栈时把数据放入queue1中，当出栈时把queue1中的数放入queue2中，但是不是全放进去queue留一个数，而出栈就是出剩下的这个数，然后把两个队列的引用换一下。

• 代码示例

public class QueueToStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public QueueToStack() {
    queue1=new LinkedList<>();
    queue2=new LinkedList<>();
}
public void push(int number) {
    queue1.add(number);
}
public int pop() {
    if(queue1.isEmpty()) {
        throw new RuntimeException("栈已空");
    }
    while(queue1.size()!=1) {
        queue2.add(queue1.poll());
    }
    int res=queue1.poll();
    swap();
    return res;
}
public int peek() {
    if(queue1.isEmpty()) {
        throw new RuntimeException("栈已空");
    }
    while(queue1.size()!=1) {
        queue2.add(queue1.poll());
    }
    int res=queue1.poll();
    queue2.add(res);
    swap();
    return res;
}
public void swap() {
    Queue<Integer> temp;
    temp=queue1;
    queue1=queue2;
    queue2=temp;
}
}

（6）用栈实现队列

• 题：用栈结构实现队列结构

• 解题思路：创建两个栈stack1和stack2，进栈时往stack1进，出栈时把stack1里面的数倒进stack2里面，然后数从stack2里面出。倒数据需要满足两个条件，只要满足这两个条件什么时候倒数据都可以，条件是stack2不为空的时候不能倒，条件二是要是倒就要把stack1里面的数全部倒进stack2中。

-代码示例

public class StackToQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public StackToQueue() {
    stack1=new Stack<>();
    stack2=new Stack<>();
}
public void add(int number) {
    stack1.push(number);
}
public int poll() {
    if(stack2.isEmpty()) {
        while(stack1.size()!=0) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}
public int peek() {
    if(stack2.isEmpty()) {
        while(stack1.size()!=0) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.peek();
}
}

(7)猫狗队列问题

• 题：有dog，cat，pet类如下
  class Pet{
  private String type;
  public Pet(String type) {
  this.type=type;
  }
  public String getType() {
  return type;
  }
  }
  class Dog extends Pet{
  public Dog() {
  super("dog");
  }
  }
  class Cat extends Pet{
  public Cat() {
  super("cat");
  }
  }

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

• 解题思路：将传进来的猫狗类重新封装成一个类，这个里面有一个属性用来记录猫狗实例的传进来的顺序，然后创建两个队列分别放猫的实例和狗的实例。当pollAll的时候，先比较猫和狗队列的第一个实例的顺序值大小谁小谁弹出。当pollDog的时候从dog队列中弹出，当pollCat的时候从cat队列中弹出。isEmpty检查两个队列是否都为空，都为空才为空，isDogEmpty和isCatEmapty分别检查狗的队列和猫的队列。

• 代码示例

猫狗封装类
class QueueEnter{
    private Pet pet;
    private int count;
    public QueueEnter(Pet pet,int count) {
        this.pet=pet;
        this.count=count;
    }
    public Pet getPet() {
        return pet;
    }
    public int getCount() {
        return count;
    }
}

猫狗队列

public class DogAndCatQueue {
int count=0;
Queue<QueueEnter> dogQueue;
Queue<QueueEnter> catQueue;
public DogAndCatQueue() {
    dogQueue=new LinkedList<>();
    catQueue=new LinkedList<>();
}
public void add(Pet pet) {
    if(pet.getType().equals("dog")){
        dogQueue.add(new QueueEnter(pet,count++));
    }else {
        catQueue.add(new QueueEnter(pet,count++));
    }
}
public Pet pollAll() {
    if(dogQueue.isEmpty()&&catQueue.isEmpty()) {
        throw new RuntimeException("队列已空");
    }
    if(dogQueue.isEmpty()) {
        return (Cat)catQueue.poll().getPet();
    }
    if(catQueue.isEmpty()) {
        return (Dog)dogQueue.poll().getPet();
    }
    int dogCount=dogQueue.peek().getCount();
    int catCount=catQueue.peek().getCount();
    if(dogCount<catCount) {
        return (Dog)dogQueue.poll().getPet();
    }else {
        return (Cat)catQueue.poll().getPet();
    }
}
public Pet pollDog() {
    if(dogQueue.isEmpty()) {
        throw new RuntimeException("队列中已没有dog实例");
    }
    return (Dog)dogQueue.poll().getPet();
}
public Pet pollCat() {
    if(catQueue.isEmpty()) {
        throw new RuntimeException("队列中已没有cat实例");
    }
    return (Cat)catQueue.poll().getPet();
}
public boolean isEmpty() {
    if(dogQueue.isEmpty()&&catQueue.isEmpty()) {
        return false;
    }else {
        return true;
    }
}
public boolean isDogEmpty() {
    return dogQueue.isEmpty();
}
public boolean isCatEmpty() {
    return catQueue.isEmpty();
}
public int size() {
    return dogQueue.size()+catQueue.size();
}
}

二、拓展

综合排序，当数据量大时，首先用归并或者快速排序，当递归到数量小于一定数量以后直接用插入排序排，选择归并还是快速排序看数据是否是基本类型，当是基本类型时用快速排序，因为快排不具备稳定但速度更快，而且基本类型也不需要稳定性，当是非基本类型时，用归并排序，归并排序稳定性高