算法之桶排序，数组结构实现大小固定的队列和栈

队列和栈"/>

算法之桶排序，数组结构实现大小固定的队列和栈

桶排序：把数据放入一个个定义范围的桶中，定义的范围必须完全一样。每个桶再排序。
经典例题：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序。思想如上图所示。
用数组结构实现大小固定的队列和栈
变栈：先定义一个数组的大小即栈的长度，再定义一个变量来表示当前栈顶元素的位置
代码如下：

public static class ArrayStack {//数组变固定长度的栈结构 栈先进后出private Integer[] arr;private Integer size;public ArrayStack(int initSize) {if (initSize < 0) {throw new IllegalArgumentException("The init size is less than 0");}arr = new Integer[initSize];size = 0;}public Integer peek() {//peek是指取出栈顶元素，但是不改变栈的原来元素数据，即取出的那个元素还在栈顶if (size == 0) {return null;}return arr[size - 1];}public void push(int obj) {if (size == arr.length) {throw new ArrayIndexOutOfBoundsException("The stack is full");}arr[size++] = obj;//先把obj压入了arr[size]的位置，然后size加1.}public Integer pop() {if (size == 0) {throw new ArrayIndexOutOfBoundsException("The stack is empty");}return arr[--size];//要弹出的元素的位置}

变队列：用3个变量，一个size定义队列的长度，一个first定义返回值的位置，一个last定义后面加入的元素的位置，具体看代码。

public static class ArrayQueue { //数组变固定长度的队列结构 队列先进先出private Integer[] arr;private Integer size;private Integer first;private Integer last;public ArrayQueue(int initSize) {if (initSize < 0) {throw new IllegalArgumentException("The init size is less than 0");}arr = new Integer[initSize];size = 0;first = 0;//要弹出的元素的位置last = 0;//要加入的元素的位置}public Integer peek() {if (size == 0) {return null;}return arr[first];}public void push(int obj) {if (size == arr.length) {throw new ArrayIndexOutOfBoundsException("The queue is full");}size++;arr[last] = obj;last = last == arr.length - 1 ? 0 : last + 1;//相当于数组的元素位置一直循环使用}public Integer poll() {if (size == 0) {throw new ArrayIndexOutOfBoundsException("The queue is empty");}size--;int tmp = first;first = first == arr.length - 1 ? 0 : first + 1;//弹出元素的位置return arr[tmp];}

附：实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作
思想：增加一个新的栈来存放那个最小值，依次把原始的那个栈的元素放入到新的那个栈中，第一次放的是原始栈的栈顶元素，如果第二次原始栈的栈顶元素小于先前放入新栈的那个元素，就压入到新的那个栈里，反之不压入，所有新栈的栈顶元素就是原始栈的元素最小值。
代码实现：

public class Code_02_GetMinStack {public static class MyStack1 {private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack1() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();//建立一个stackmin用来存放小的那个元素}public void push(int newNum) {if (this.stackMin.isEmpty()) {this.stackMin.push(newNum);} else if (newNum <= this.getmin()) {this.stackMin.push(newNum);//比较大小，小的话就压入栈中}this.stackData.push(newNum);//把数据压入到data栈中}public int pop() {if (this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}int value = this.stackData.pop();//弹出data栈的栈顶元素if (value == this.getmin()) {this.stackMin.pop();}return value;}public int getmin() {if (this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();//peek是指弹出栈顶元素 但是不改变原来的栈顶元素}}public static class MyStack2 {private Stack<Integer> stackData;private Stack<Integer> stackMin;public MyStack2() {this.stackData = new Stack<Integer>();this.stackMin = new Stack<Integer>();}public void push(int newNum) {if (this.stackMin.isEmpty()) {this.stackMin.push(newNum);} else if (newNum < this.getmin()) {this.stackMin.push(newNum);} else {int newMin = this.stackMin.peek();this.stackMin.push(newMin);}this.stackData.push(newNum);}public int pop() {if (this.stackData.isEmpty()) {throw new RuntimeException("Your stack is empty.");}this.stackMin.pop();return this.stackData.pop();}public int getmin() {if (this.stackMin.isEmpty()) {throw new RuntimeException("Your stack is empty.");}return this.stackMin.peek();}}public static void main(String[] args) {MyStack1 stack1 = new MyStack1();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("=============");MyStack1 stack2 = new MyStack1();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());}}