运行结果：

3.4.1 结果分析

元素，其中最大值为7，最小值为1。

5个元素，需要6个桶。

首先，将max-min=7-1=6进行5等分，6/5=1.2，得每段距离长1.2。

然后进行每个元素属于的桶号的计算：

• 3：(3-1)/1.2=2/1.2=1（取整）；
• 6：(6-1)/1.2=5/1.2=4；
• 2：(2-1)/1.2=1/1.2=0；

所以分桶结果如下图：

所以result=3;

3.4.2 对于计算桶号的公式的分析

即就是：

先算出每段距离的长度（），再求出当前元素据起点min的距离（），最后用后者除以前者就得到当前元素所属于的桶号（index）。

4.用数组结构实现大小固定的栈和队列

4.1 实现栈

4.1.1 分析

index：表示新进来的数应该放置的位置。

一个数入栈时，若index+1>size，则报错；否则这个数放在array[index]的位置，然后index++；

一个数出栈时，若index-1<0，则报错；否则弹出放在array[index-1]位置上的数，然后index--。

4.1.2 代码实现

package Solution;class ArrayStack{Integer[] array;Integer size;	public ArrayStack(int initsize) {if(initsize<0)throw new IllegalArgumentException("The init size is less than 0");elsearray=new Integer[initsize];size=0;}public void push(int num) {if(size==array.length)throw new ArrayIndexOutOfBoundsException("The queue is full");elsearray[size++]=num;}public Integer peek() {if(size==0)throw new ArrayIndexOutOfBoundsException("The queue is empty");elsereturn array[size-1];}public Integer pop() {if(size==0)throw new ArrayIndexOutOfBoundsException("The queue is empty");elsereturn array[--size];}
}	public class ArrayToStack {public static void main(String[] args) {ArrayStack as=new ArrayStack(3);as.push(3);System.out.println("peek:"+as.peek());as.push(24);System.out.println("pop:"+as.pop());System.out.println("pop:"+as.pop());//System.out.println("pop:"+as.pop());}	
}

运行结果：

若为注释掉最后一句pop，运行结果为：

4.2 实现队列

4.2.1 分析

如果一个数要入队列，若size

如果一个数要出队列，若size>0，则array[first]位置上的数出队列，同时first++；否则报错。

注：当last和first到达最后一个元素时，让它们下一个位置为0位置。

（last和first之间无关系）

4.2.2 代码实现

package Solution;class ArrayQueue{Integer[] array;Integer first;//出队列时的下标Integer last;//入队列时的下标Integer size;public ArrayQueue(int initsize) {if(initsize<0)throw new IllegalArgumentException("The init size is less than 0");elsearray=new Integer[initsize];size=0;last=0;first=0;}public void push(int num) {if(size==array.length)throw new ArrayIndexOutOfBoundsException("The queue is full");else {array[last]=num;last=last==array.length-1?0:last+1;size++;}}public Integer peek() {if(size==0)throw new ArrayIndexOutOfBoundsException("The queue is empty");else return array[first];}public Integer poll() {if(size==0)throw new ArrayIndexOutOfBoundsException("The queue is empty");else {size--;first=first==array.length-1?0:first+1;return array[first];}}
}
public class ArrayToQueue {public static void main(String[] args) {ArrayQueue as=new ArrayQueue(3);as.push(7);System.out.println("peek:"+as.peek());as.push(6);System.out.println("pop:"+as.poll());//7出as.push(5);as.push(9);//as.push(4);System.out.println("pop:"+as.poll());//6System.out.println("pop:"+as.poll());//5}
}

运行结果：

5. 实现一个特殊的栈， 在实现栈的基本功能的基础上， 再实现返回栈中最小元素的操作。

【要求】
1． pop、 push、 getMin操作的时间复杂度都是O(1)。
2． 设计的栈类型可以使用现成的栈结构。

5.1 方法一

5.1.1 分析：

准备两个栈：data、min

入栈：

第一个元素，压入data、min栈；

后面剩余元素，依次压入data栈；若当前入栈元素比min栈栈顶元素小，则入min栈，否则再一次压入min栈栈顶元素。

出栈：

两个栈同时弹出元素。

5.1.2 代码实现

package Solution;import java.util.Stack;class MyStack{Stack data;Stack min;public MyStack() {this.data=new Stack();this.min=new Stack();}public void push(int num) {if(data.isEmpty()) {data.push(num);min.push(num);}if(num<=min.peek()) {data.push(num);min.push(num);}else {data.push(num);min.push(min.peek());}}public Integer pop() {if(data.isEmpty())throw new RuntimeException("Your stack is empty.");min.pop();return data.pop();}public Integer getMin() {if(data.isEmpty())throw new RuntimeException("Your stack is empty.");return min.peek();}
}
public class StackGetMin {public static void main(String[] args) {MyStack ms=new MyStack();ms.push(4);ms.push(5);ms.push(3);ms.push(6);System.out.println("min:"+ms.getMin());System.out.println(ms.pop());System.out.println(ms.pop());System.out.println("min:"+ms.getMin());}
}

运行结果：

5.2 方法二

5.2.1 分析：

准备两个栈：data、min

入栈：

第一个元素，压入data、min栈；

后面剩余元素，依次压入data栈；若当前入栈元素比min栈栈顶元素小，则入min栈，否则不如min栈。

出栈：

若当前弹出的data栈顶元素=min栈栈顶元素，两个栈都弹出栈顶元素，否则只有data栈弹出栈顶元素。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！