如何实现具有最大值、最小值和中间值的栈和队列
在研究“如何实现具有最大值、最小值和中间值的栈和队列”前，我们先考虑以下问题，然后由此过度到题目问题。
1）如何用两个栈实现队列
2）如何用两个队列实现栈
3）如何实现包含获取最小值函数getMin()的栈
4）如何实现包含获取中间值函数getMedian()的栈
5）如何实现包含获取最小值函数getMin()的队列
1 如何用两个栈实现队列在研究问题前，我们可以用2个栈模拟一下具体操作过程，可以总结出以下规律：
入队：元素插入stack1;
出队：如果stack2中为空，先将stack1中元素入栈stack2，然后再将stack2的栈顶元素出栈。否则直接将stack2中元素出栈。
队列为空：stack1和stack2同时为空
队列大小：为stack1和stack2大小之和
具体过程见下图（图来自《剑指offer》）
Java实现代码如下
3 如何实现包含获取最小值函数的栈问题：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的getMin函数。在该栈中，调用getMin、push及pop的时间复杂度都是O(1).
思路：用一个辅助栈stack2记住每次入栈stack1的当前最小值:在stack1入栈时，往stack2中加入当前最小值；stack1元素出栈时，stack2也出栈一个元素。最小值从stack2中获取及栈顶元素。
4 如何实现包含获取中间值函数的栈如果能对栈中元素进行排序，那么排序好的中间值即为所求。问题3和问题4的具体代码如下，代码中同时实现了获取栈的最大值、最小值和中间值
public class ExmaPeekableQueue<E extends Comparable<E>> implements IExamPeekableQueue{Stack stack1=new Stack();Stack stack2=new Stack();@Overridepublic void enqueue(Comparable e) {stack1.push(e);}//end enqueue()@Overridepublic Comparable<E> dequeue() {if(stack2.isEmpty()){stack2.push(stack1.pull());}//end ifreturn stack2.pull();}//end dequeue()@Overridepublic Comparable<E> peekMedian() {Comparable[] arr=null; //用于存储队列中当前元素的数组if(stack1.isEmpty()){arr=stack2.toArray();}//end ifelse if(stack2.isEmpty()){arr=stack1.toArray();}//end ifelse{arr=new Comparable[size()];Comparable[] arrE1=stack1.toArray();Comparable[] arrE2=stack2.toArray();//将2个栈中的元素复制到一个数组中int i=0; for(;i<stack1.size();i++){ arr[i]=arrE1[i]; }//end for for(int j=0;j<stack2.size();j++){ arr[++i]=arrE2[j]; }//end for}//end elseArrays.sort(arr);return arr[arr.length/2];}//end peekMedian()@Overridepublic Comparable peekMaximum() {Comparable max1=stack1.getMax();Comparable max2=stack2.getMax();if(max1.compareTo(max2)>0){return max1;}//end ifelsereturn max2;}@Overridepublic Comparable<E> peekMinimum() {Comparable min1=stack1.getMin();Comparable min2=stack2.getMin();if(min1.compareTo(min2)>0){return min2;}//end ifelsereturn min1;}//end peekMinimum()@Overridepublic int size() {return (stack1.size()+stack2.size());}//end size()}//end class
