实现O(1)获取最大最小值的栈----java

原文：http://blog.csdn.net/sheepmu/article/details/38459165

实现O(1)获取最大最小值的栈和队列----java

一.如何实现包含获取最小值函数的栈

问题：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的getMin函数。在该栈中，调用getMin、push及pop的时间复杂度都是O(1).

最小值思路：用一个辅助栈stack2记住每次入栈stack1的当前最小值:在stack1入栈时，往stack2中加入当前最小值；stack1元素出栈时，stack2也出栈一个元素。最小值从stack2中获取及栈顶元素。O(1)

最大值思路：同上O(1)

中间值思路：对栈排序，取中间值，但是时间不是O(1)

[java] view plaincopy

 

1. package com.sheepmu;  
2.   
3. import java.util.Arrays;  
4. import java.util.Stack;  
5.   
6. public class SpecialStack<E extends Comparable<E>>  
7. {  
8.     Stack<E> stack1=new Stack<E>();  
9.     Stack<E> stackMin=new Stack<E>();//存放求最小值的栈  
10.     Stack<E> stackMax=new Stack<E>();//存放求最大值的栈  
11.     public void push(E e)  
12.     {  
13.         stack1.push(e);   
14.           
15.         if(stackMin.isEmpty()||e.compareTo(stackMin.peek())<0)  
16.             stackMin.push(e);//若最小栈为空push进stack时就同时把它push进stackMin;  
17.         else if(e.compareTo(stackMin.peek())>0)  
18.             stackMin.push(stackMin.peek());  
19.           
20.         if(stackMax.isEmpty()||e.compareTo(stackMin.peek())>0)  
21.             stackMax.push(e);  
22.         else if(e.compareTo(stackMax.peek())<0)  
23.             stackMin.push(stackMax.peek());  
24.     }  
25.     public E pop()//一定要记着，非空才能pop()  
26.     {  
27.         if(!stack1.isEmpty()&&!stackMin.isEmpty()&&!stackMax.isEmpty())  
28.         {     
29.             E e=stack1.pop();  
30.             stackMin.pop();  
31.             stackMax.pop();  
32.             return e;  
33.         }  
34.         else  
35.         {  
36.             System.out.println("栈已经为空了");  
37.             return null;  
38.         }  
39.            
40.     }  
41.     public E getMin()  
42.     {  
43.         return  stackMin.peek();  
44.     }  
45.     public E getMax()  
46.     {  
47.         return stackMax.peek();  
48.     }  
49.     public E getMed()  
50.     {  
51.         E[] ss=stack1.toArray(new E[stack.size()]);//stack1.toArray()返回的是Object[],  栈----->数组;不能toArray后再强制转换，会报错  
52.         Arrays.sort(ss);  
53.         return ss[ss.length/2];  
54.     }  
55.       
56. }  

实现O(1)获取最大最小值的栈----java

原文：http://www.cnblogs.com/zhizhan/p/4882971.html