编程之美3.7：队列中取最大值操作问题_修改1中的“出队”函数dequeue,使得每次出队的是队列元素中的最大值;

import java.util.ArrayList;
 
public class Solution2 {
	public static void main(String[] args){
		HeapQueue heapQueue = new HeapQueue();
		heapQueue.enQueue(11);
		heapQueue.enQueue(78);
		heapQueue.enQueue(30);
		heapQueue.enQueue(9);
		heapQueue.enQueue(8);
		heapQueue.enQueue(4);
		heapQueue.enQueue(7);
		heapQueue.enQueue(15);
		System.out.println(heapQueue);
		System.out.println(heapQueue.deQueue());
		System.out.println(heapQueue);
		System.out.println(heapQueue.maxValue());
	}
}
 
class HeapQueue{
	MaxHeap max = new MaxHeap();
	public void enQueue(int x) {
		max.insert(x);
	}
	
	public int deQueue(){	
		int temp = max.head.value;
		max.deleteLast();
		return temp;
	}
	public int maxValue(){
		return max.getMax();
	}
    public String toString() {  
        return max.toString();    
    }  	
}
 
class MaxHeap {
    private ArrayList<Node> array = new ArrayList<>();  //用来堆排序
    Node tail; //记录链表尾
    Node head; 
    
    //删除最后一个元素   O(2n)
    public void deleteLast() {  
    	Node temp = head;
		head = head.next;
		array.remove(temp);
    }
    
    //获取最大值
    public int getMax(){
    	return array.get(0).value;
    }
    
    //插入一个值     O(2n)
    public void insert(Integer x){         
        Node temp = new Node();
        temp.value = x;
        if(tail == null){
        	tail = temp;
        	head = temp;
        } else {
        	tail.next = temp;
        	tail = temp;
        }
        int i = 0;
        for (; i < array.size(); i++) {
        	if(array.get(i).value < temp.value)
        		break;
        }
        array.add(i, temp);
    } 
    
    //用于显示结果（先显示排序结果，后显示插入顺序，以**为分割）
    public String toString() {  
        StringBuffer sb = new StringBuffer();
        Node temp = head;
        for (int i = 0; i < array.size(); i++)  
            sb.append(array.get(i).value + " ");
        sb.append("**");
        while(temp!= null){
        	sb.append(" " + temp.value);
        	temp = temp.next;
        }
        return new String(sb);    
    } 
    
    //用链表来记录插入顺序，参考LinkedHashMAp
    class Node{
	   Integer value;
	   Node next;
    }
} 

import java.util.Enumeration;
 
class Queue_T{
	private java.util.Stack<Integer> stackA;
	private java.util.Stack<Integer> stackB;
	private int max_index;
	
	public Queue_T() {
		stackA = new java.util.Stack<Integer>();
		stackB = new java.util.Stack<Integer>();
		max_index = -1;
	}
	void EnQueue(int v) {
		stackB.push(v);
		if(v > max_index) {
			max_index = v;
		}				
	}
	Integer DeQueue() {
		if(stackA.isEmpty()) {
			while(!stackB.isEmpty()) {
				stackA.push(stackB.pop());
			}
		}
		int peek = stackA.pop();
		if(peek == max_index) {
			max_index = LookMax();
		}
		return peek;
	}
	int Max() {
		return max_index;
	}
	int LookMax() {
		int maxA = -1;
		int maxB = -1;
		Enumeration<Integer> itemsA = stackA.elements();
		while(itemsA.hasMoreElements()) {
			if(itemsA.nextElement() > maxA) {
				maxA = itemsA.nextElement();
			}
		}
		if(!stackB.isEmpty()) {
			Enumeration<Integer> itemsB = stackB.elements();
			while(itemsB.hasMoreElements()) {
    			if(itemsB.nextElement() > maxB) {
    				maxB = itemsB.nextElement();
    			}
    		}
		}
		if(maxA > maxB)
			return maxA;
		else
			return maxB;
	}
}