栈兑现队列（维护最大值）

package alogrithm;

import java.util.EmptyStackException;

public class MyStack {
	
	private int stackTop ;
	
	private int maxStackItemIndex ;
	
	private final int MAX = 20;
	
	private int data[];
	
	private int nextMaxItem[];
	public MyStack(){
		stackTop = -1;
		maxStackItemIndex = -1;
		data = new int[MAX];
		nextMaxItem  = new int[MAX];
	}
	
	public void push(int x){
		stackTop ++;
		if(stackTop>=MAX)
			;
		else{
			data[stackTop] = x;
			if(x > max()){
				nextMaxItem[stackTop] = maxStackItemIndex;
				maxStackItemIndex = stackTop;
			}
			else
				nextMaxItem[stackTop] = -1;
		}
	}
	
	public int pop(){
		int ret;
		if(stackTop<0)
			throw new EmptyStackException();
		else{
			ret = data[stackTop];
			if(stackTop==maxStackItemIndex){
				maxStackItemIndex = nextMaxItem[stackTop];
			}
			stackTop--;
		}		
		return ret;
	}
	
	public boolean isEmpty(){
		return stackTop==-1?true:false;
	}
	
	public int max(){
		if(maxStackItemIndex >=0)
			return data[maxStackItemIndex];
		else
			return Integer.MIN_VALUE;
	}
}

package alogrithm;

public class MyQueue {
	
	private MyStack stackA;
	private MyStack stackB;
	
	
	public MyQueue(){
		stackA = new MyStack();
		stackB = new MyStack();
	}
	
	
	public int maxValue(int x,int y){
		return x>y?x:y;
	}
	
	public int max(){
		return maxValue(stackA.max(), stackB.max());
	}
	
	public void enQueue(int x){
		stackA.push(x);
	}
	
	public int Dequeue(){
		if(stackA.isEmpty()){
			while(!stackB.isEmpty())
				stackA.push(stackB.pop());
		}
		
		return stackA.pop();
	}
}