问题：
假设有这样一个拥有3个操作的队列：
1.EnQueue（v）看，将v加入队列中
2.DeQueue：使队列中的队首元素删除并返回此元素
3.MaxElement：返回队列中的最大元素
设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能的降低。
分析与解法：
先实现一个带有max函数的栈，然后用两个栈实现一个队列
[java]
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 datalist = new LinkedList();
LinkedList helplist = new LinkedList();
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