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

桶排序：把数据放入一个个定义范围的桶中，定义的范围必须完全一样。每个桶再排序。
经典例题：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度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());
	}

}

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

相关推荐