设计包含max函数的队列
问题：
假设有这样一个拥有3个操作的队列：
1.EnQueue（v）看，将v加入队列中
2.DeQueue：使队列中的队首元素删除并返回此元素
3.MaxElement：返回队列中的最大元素
设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能的降低。
分析与解法：
先实现一个带有max函数的栈，然后用两个栈实现一个队列
import java.util.LinkedList;public class Test_3_7 {/** * @param args */public static void main(String[] args) {Queue queue = new Queue();queue.EnQueue(4);System.out.println(queue.MaxElement());queue.EnQueue(1);System.out.println(queue.MaxElement());queue.EnQueue(5);System.out.println(queue.MaxElement());queue.EnQueue(3);System.out.println(queue.MaxElement());queue.DeQueue();System.out.println(queue.MaxElement());queue.DeQueue();System.out.println(queue.MaxElement());queue.DeQueue();System.out.println(queue.MaxElement());}}//先实现一个具有查找最大值功能的栈class Stack{LinkedList<Integer> datalist = new LinkedList<Integer>();LinkedList<Integer> helplist = new LinkedList<Integer>();public void push(int i){if(datalist.size()==0){datalist.add(i);helplist.add(0);}else{int max =datalist.get(helplist.getLast());if(i>max){helplist.add(datalist.size());}else{helplist.add(helplist.getLast());}datalist.add(i);}}public Integer pop(){if(datalist.size()==0){System.out.println("栈中已无数据！");return null;}helplist.removeLast();return datalist.removeLast();}public Integer max(){if(datalist.size()==0){System.out.println("栈中已无数据！");return null;}return datalist.get(helplist.getLast());}public boolean isEmpty(){if(datalist.size()==0)return true;else return false;}}//用两个栈实现一个队列class Queue{Stack stack1 = new Stack();Stack stack2 = new Stack();public void EnQueue(int i){stack1.push(i);}public Integer DeQueue(){int temp;if(stack2.isEmpty()==true){while(stack1.isEmpty()==false){temp = stack1.pop();stack2.push(temp);}}return stack2.pop();}public Integer MaxElement(){if(stack1.isEmpty())return stack2.max();else if(stack2.isEmpty()){return stack1.max();}return stack1.max()>stack2.max()?stack1.max():stack2.max();}}输出结果：
4
4
5
5
5
5
3