正文

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

IP云
IP云V管理员/11 阅读
11/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

原文：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)

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

相关阅读

目录[+]