/*
今天的主要內(nèi)容：
1、桶排序厉碟、計數(shù)排序的介紹
2、求排序后的數(shù)組相鄰兩個數(shù)的最大差值
3屠缭、用數(shù)組實現(xiàn)大小固定的隊列和棧
4箍鼓、實現(xiàn)一個特殊的棧，在實現(xiàn)棧的基本功能的基礎上呵曹，再實現(xiàn)返回棧中最小元素的操作何暮。
*/

1海洼、桶排序坏逢、計數(shù)排序的介紹

①非基于比較的排序是整，與被排序的樣本的實際數(shù)據(jù)狀況很有關系，所以舵盈，實際中并不經(jīng)常使用
* 非基于比較的排序總有瓶頸秽晚，這種瓶頸來自于他數(shù)據(jù)狀況本身赴蝇，因此句伶，也就沒法作為一個通解被運
用到所有方面
②時間復雜度為O(N),空間復雜度為O(N)
③穩(wěn)定的排序

幾個小點：

• 什么是桶陆淀？
  答：a. 一種數(shù)據(jù)狀況出現(xiàn)的詞頻
  b. 桶具體的實現(xiàn)可以是數(shù)組中的某一個位置轧苫，可以是一個隊列，也可以
  是一個堆身冬；
  c. 對數(shù)據(jù)進行分桶岔乔，并不是基于比較的
• 計數(shù)排序只是實現(xiàn)了桶排序

補充問題：
2嘿歌、給定一個數(shù)組宙帝，求如果排序之后息裸，相鄰兩數(shù)的最大差值呼盆，要求時間復雜度O(N)，
且要求不能用非基于比較的排序相嵌。

答：此題借用了桶的概念饭宾，但是沒有進行桶排序
a. 準備桶：
* 如果一個數(shù)組中有N個數(shù)批糟，則準備N+1個桶
* 先遍歷數(shù)組看铆，找到最小值和最大值。
** 若最小值和最大值相同弹惦，最大差值為0否淤，直接返回
** 若最小值和最大值不同
** 則最小值放到0號桶中棠隐，最大值放到N號桶中
** 將最大值和最小值之間的范圍等分為N+1份石抡，一個數(shù)屬于哪個范圍，就放到哪
號桶里
** 此時N個數(shù)放在N+1個桶里啰扛，一定有一個是空桶侠讯。
** 相鄰兩數(shù)可能在同一個桶，也可能跨桶
*** 則差值最大的相鄰數(shù)一定是跨桶溜嗜，不可能在一個桶里。
** 空桶的左邊和右邊一定分別存在一個非空的桶
** 空桶左邊的非空桶中收集的最大值和空桶右邊的非空桶中收集的最小值一定
是兩個相鄰的數(shù)。這兩個數(shù)的差值一定大于桶所表示的范圍土全。
** 此時我們就不需要處理同一個桶中的兩個數(shù)之間的差值。因為一定不是最大的
** 此時我們分析空桶只是為了證明：相鄰兩個數(shù)的最大值一定不會來自同一個桶
而是來自于跨桶会涎。
b. 桶中只收集要放在該桶中的數(shù)據(jù)的最小值和最大值裹匙，以及一個Boolean類型的數(shù)，用來標識
當前桶中是否進來過數(shù)末秃。
c. 從1號桶開始概页，如果為空，則往下走练慕，每一個非空桶都找前面那個最近的非空桶惰匙，找到前一
個非空桶的最大值和當前桶的最小值求一個差值。
代碼：

// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (maxGap(arr1) != comparator(arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}

public static int maxGap(int[] arr){
//判斷數(shù)組合法性
if (arr == null || arr.length < 2) {
return 0 ;
}

//遍歷數(shù)組求數(shù)組中的最小值和最大值的下標
int len = arr.length;
int minIndex = 0;
int maxIndex = 0;
for (int i = 0; i < len; i++) {
    if (less(arr, i, minIndex)) {
        minIndex = i;
    }

    if (less(arr, maxIndex, i)) {
        maxIndex = i;
    }
}

//求出最小值和最大值
int min = arr[minIndex];
int max = arr[maxIndex];

//判斷最小值和最大值
if (min == max) {
    return  0;
}

//設計桶
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid = 0;

//重新遍歷整個數(shù)組铃将，將數(shù)進行分桶
for (int i = 0; i < len; i++) {
    bid = bucket(arr[i], len, min, max);
    mins[bid] = hasNum[bid] ? Math.min(mins[bid],arr[i]) : arr[i];    //更新桶中的最小值
    maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],arr[i]) : arr[i];  //更新桶中的最大值
    hasNum[bid] = true;
}

//求相鄰數(shù)的最大差值
/*
* 從1號桶開始项鬼，如果為空，則往下走劲阎，每一個非空桶都找前面那個最近的非空桶秃臣，
* 找到前一個非空桶的最大值和當前桶的最小值求一個差值。
* */
int result = 0;
int lastMax = maxs[0];                  //將第一個桶中的最大值作為初始的待比較的非空桶的最大值
for (int i = 1; i <= len; i++) {
    if (hasNum[i]) {          //當前桶不空
        result = Math.max(result, mins[i] - lastMax);                 //當前非空桶的最小值 - 前一個非空桶的最大值
        lastMax = maxs[i];
    }
}
return result;

}

/*

• 比較數(shù)組中兩個數(shù)的大小
• */
  private static boolean less(int[] arr, int i, int j) {
  return arr[i] - arr[j] < 0;
  }

/**

• 將數(shù)據(jù)進行分桶
  */
  private static int bucket(long num, long len,long min, long max) {
  return (int) ((num - min) * len / (max - min));
  }

// for test
public static int comparator(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
gap = Math.max(nums[i] - nums[i - 1], gap);
}
return gap;
}

// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}

// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}

3哪工、用數(shù)組結構實現(xiàn)大小固定的隊列和棧

public static class ArrayStack<T extends Comparable<T>>{
private static int maxSize = 10; //當前棧的大小
private static Comparable[] arr;
private static int N = 0; //當前棧中的元素個數(shù)

public ArrayStack() {
    init(maxSize);
}

public ArrayStack(int maxSize){
    this.maxSize = maxSize;
    init(maxSize);
}

private void init(int maxSize) {
    arr = new Comparable[maxSize];
}


public static boolean isEmpty(){
    return N == 0;
}

public static int size(){
    return N;
}

public static Comparable peek(){
    if (N == 0) {
        return null;
    }
    return arr[N - 1];
}

public static void push(Comparable item) {
    if (N == maxSize) {
        throw new ArrayIndexOutOfBoundsException("The stack is full");
    }
    arr[N++] = item;
}

public static Comparable pop(){
    if (!isEmpty()) {
        return arr[--N];
    }else
        throw new ArrayIndexOutOfBoundsException("The stack is empty");
}

}

/*

• 隊列的一些操作:

• • 隊列為空：rear == front
  • 隊列為滿：(rear + 1) % maxSize == front //（基于給隊列留一個空閑位置而實現(xiàn)奥此，不然和隊列為空時條件重合）
  • 隊列長度：(rear - front) % maxSize

• */
  public static class ArrayQueue<T extends Comparable<T>>{
  private static int maxSize = 10;
  private static Comparable[] arr;
  private static int front;
  private static int rear;

  ArrayQueue(){
  init(maxSize);
  }

  ArrayQueue(int maxSize) {
  init(maxSize);
  }

  private void init(int maxSize) {
  arr = new Comparable[maxSize];
  front = rear = 0;
  }

  public static boolean isEmpty(){
  return rear == front;
  }

  public static int size(){
  return (rear - front) % maxSize;
  }

  public static void enqueue(Comparable item) {
  if (isFull()) {
  throw new ArrayIndexOutOfBoundsException("The queue is full");
  }
  arr[rear] = item;
  rear = (rear + 1) % maxSize;
  }

  public static Comparable dequeue(){
  if (isEmpty()) {
  throw new ArrayIndexOutOfBoundsException("The queue is empty");
  }

    Comparable tmp = arr[front];
    front = (front + 1)%maxSize;
    return tmp;
  

  }

  private static boolean isFull() {
  return ((rear + 1) % maxSize) == front;
  }

  public Comparable peek() {
  return arr[front];
  }
  }

public static void main(String[] args) {
Integer[] a = {1,2,3,4,5,6};

ArrayStack<Integer> stack = new ArrayStack<>(a.length);
for (int i = 0; i < a.length; i++) {
    stack.push(a[i]);
}

System.out.print("棧的大小為：" + stack.size()+ "  輸出為：");

while (!stack.isEmpty()) {
    System.out.print(stack.pop() + " ");
}

System.out.println();

ArrayQueue<Integer> queue = new ArrayQueue<>(6);
for (int i = 0; i < a.length; i++) {
    queue.enqueue(a[i]);
}

System.out.print("隊列的大小為" + queue.size() + "  輸出為：");
while (!queue.isEmpty()) {
    System.out.print(queue.dequeue() + " ");
}
System.out.println();

}

4、實現(xiàn)一個特殊的棧雁比，在實現(xiàn)棧的基本功能的基礎上稚虎，再實現(xiàn)返回棧中最小元素的操作。
【要求】
* pop偎捎、push蠢终、getMin操作的時間復雜度都是O(1)。
* 設計的棧類型可以使用現(xiàn)成的棧結構茴她。

思路：
* 此時利用兩個棧：stackData和stackMin
** stackData中壓入每一次進來的數(shù)據(jù)
** stackMin中存放當前棧中最小值
* 進來一個數(shù)據(jù)item
** 壓入stackData棧寻拂，stackData.push(item)
** 如果stackMin棧為空，則壓入stackMin棧
如果stackMin不為空且item比stackMin的棧頂元素大丈牢，則將stackMin中棧頂元素再一次壓棧
如果stackMin不為空且item比stackMin的棧頂元素小祭钉，則將item進行壓棧

代碼：
public static class MinStack<T extends Comparable<T>>{
private static Stack<Comparable> stackData;
private static Stack<Comparable> stackMin;

private static int N = 0;

public MinStack(){
    init();
}

private void init() {
    this.stackData = new Stack<Comparable>();
    this.stackMin = new Stack<Comparable>();
}

public static int size() {
    return N;
}

public static void push(Comparable item) {
    stackData.push(item);                   //將數(shù)據(jù)直接壓入stackData棧中
    N++;

    if(!stackMin .isEmpty() && less(stackMin.peek(),item)){         //若新加入的數(shù)據(jù)比stackMin中棧頂數(shù)據(jù)大
        stackMin.push(stackMin.peek());         //將stackMin中的棧頂元素再進行一次壓棧
    }else{                                  //若新加入的數(shù)據(jù)比stackMin中棧頂數(shù)據(jù)大
        stackMin.push(item);                    //將新元素壓棧到stackMin棧中
    }
}

public static Comparable pop(){
    if (stackData.isEmpty()) {
        throw new RuntimeException("Your stack is empty.");
    }
    Comparable item = stackData.pop();
    N--;

    stackMin.pop();
    return item;
}

public static Comparable getMin(){
    return stackMin.peek();
}

private static boolean less(Comparable i, Comparable j) {
    return i.compareTo(j) < 0;
}

}

public static void main(String[] args) {
MinStack stack1 = new MinStack();
stack1.push(3);
System.out.println(stack1.getMin());
stack1.push(4);
System.out.println(stack1.getMin());
stack1.push(1);
System.out.println(stack1.getMin());
System.out.println(stack1.pop());
System.out.println(stack1.getMin());

System.out.println("=============");

MinStack stack2 = new MinStack();
stack2.push(3);
System.out.println(stack2.getMin());
stack2.push(4);
System.out.println(stack2.getMin());
stack2.push(1);
System.out.println(stack2.getMin());
System.out.println(stack2.pop());
System.out.println(stack2.getMin());

}

5、如何僅用隊列結構實現(xiàn)棧結構己沛？ 如何僅用棧結構實現(xiàn)隊列結構慌核？

思路一：
* 如何僅用隊列結構實現(xiàn)棧結構距境？
** 準備兩個隊列，queueData和queueHelp隊列
*** queueData用來入隊每一個新進來的元素垮卓，數(shù)永遠只進data隊列
*** 當需要取出一個元素時垫桂，我們將除了queueData中最后一個元素外出隊到queueHelp中
然后從queueData中取出那個剩下的隊尾的元素
*** 每一次的pop操作之后，都要交換data和help的指針
思路二：
* 如何僅用棧結構實現(xiàn)隊列結構粟按？
** 準備兩個棧诬滩，stackPush和stackPop棧
*** stackPush用來入棧每一個新進來的元素，數(shù)永遠只被push到stackPush中
*** 當需要取出一個元素時灭将，我們就從stackPop中進行獲取
①要注意：把stackPush棧中的內(nèi)容全部出棧到stackPop中
②如果stackPop中有元素碱呼，則一定不要將stackPush中數(shù)據(jù)倒到stackPop中

代碼：
public static class TwoQueuesStack{
private static Queue<Comparable> queueData;
private static Queue<Comparable> queueHelp;

TwoQueuesStack(){
    queueData = new LinkedList<>();
    queueHelp = new LinkedList<>();
}

public static void push(Comparable item){
    queueData.add(item);
}

public static Comparable peek(){
    if (queueData.isEmpty()) {
        throw new RuntimeException("Stack is Empty");
    }

    while (queueData.size() > 1) {                  //將queueData隊列中除了隊尾的元素外都出隊到queueHelp中
        queueHelp.add(queueData.poll());
    }

    Comparable result = queueData.poll();
    queueHelp.add(result);            //因為只是查看，因此還要將隊尾元素再添加到queueHelp隊列中
    exch();                 //交換queueData和queueHelp
    return result;
}

public static Comparable pop(){
    if (queueData.isEmpty()) {
        throw new RuntimeException("Stack is Empty");
    }

    while (queueData.size() > 1) {                  //將queueData隊列中除了隊尾的元素外都出隊到queueHelp中
        queueHelp.add(queueData.poll());
    }

    Comparable result = queueData.poll();
    exch();                 //交換queueData和queueHelp
    return result;
}

public static int size(){
    return (queueHelp.size() + queueData.size());
}

/*
* 交換queueData和queueHelp
* */
private static void exch() {
    Queue<Comparable> t = queueData;
    queueData = queueHelp;
    queueHelp = t;
}

}

public static class TwoStacksQueue{
private static Stack<Comparable> stackPush;
private static Stack<Comparable> stackPop;

TwoStacksQueue(){
    stackPush = new Stack<>();
    stackPop = new Stack<>();
}

public static int size(){
    return stackPush.size() + stackPop.size();
}

public static void enqueue(Comparable item){
    stackPush.push(item);
}

public static Comparable dequeue(){
    if (stackPop.empty() && stackPush.empty()) {
        throw new RuntimeException("Queue is empty!");
    }

    pushToPop();
    return stackPop.pop();
}

/*
* 當需要取出一個元素時宗侦，我們就從stackPop中進行獲取
            ①要注意：把stackPush棧中的內(nèi)容全部出棧到stackPop中
            ②如果stackPop中有元素愚臀，則一定不要將stackPush中數(shù)據(jù)倒到stackPop中
* */
private static void pushToPop() {
    if (stackPop.isEmpty()) {          //如果stackPop中有元素，則一定不要將stackPush中數(shù)據(jù)倒到stackPop中
        return;
    }

    while(!stackPush.isEmpty())
        stackPop.push(stackPush.pop());
}

}