双栈队列实现快速获取队列最大值最小值

含有记录栈的数组栈实现，两个记录栈，一个记录最大值，一个记录最小值。

[java] view plaincopy
import java.util.ArrayList;  
import java.util.Date;  
import java.util.List;  
import java.util.Random;  
  
public class MaxStack<E extends Comparable<E>> {  
  
    private List<E> stack;  
    private List<E> maxStack;  
    private List<E> minStack;  
  
    public MaxStack() {  
        stack = new ArrayList<E>();  
        maxStack = new ArrayList<E>();  
        minStack = new ArrayList<E>();  
    }  
  
    public int size() {  
        return stack.size();  
    }  
  
    public boolean isEmpty() {  
        return stack.size() == 0;  
    }  
  
    public E push(E e) {  
        if (e == null)  
            return null;  
  
        int count = stack.size();  
        if (count == 0) {  
            stack.add(e);  
            maxStack.add(e);  
            minStack.add(e);  
            return e;  
        }  
  
        stack.add(e);  
        if (maxStack.get(count - 1).compareTo(e) > 0)  
            maxStack.add(maxStack.get(count - 1));  
        else  
            maxStack.add(e);  
  
        if (minStack.get(count - 1).compareTo(e) < 0)  
            minStack.add(minStack.get(count - 1));  
        else  
            minStack.add(e);  
  
        return e;  
    }  
  
    public E pop() {  
        if (stack.size() == 0)  
            return null;  
  
        maxStack.remove(stack.size() - 1);  
        minStack.remove(stack.size() - 1);  
  
        return stack.remove(stack.size() - 1);  
    }  
  
    public E peek() {  
        return stack.size() == 0 ? null : stack.get(stack.size() - 1);  
    }  
  
    public E getMaxE() {  
        return stack.size() == 0 ? null : maxStack.get(stack.size() - 1);  
    }  
  
    public E getMinE() {  
        return stack.size() == 0 ? null : minStack.get(stack.size() - 1);  
    }  
  
    @Override  
    public String toString() {  
        StringBuffer sBuffer = new StringBuffer("STACK");  
        StringBuffer aBuffer = new StringBuffer("MAX");  
        StringBuffer iBuffer = new StringBuffer("MIN");  
        for (int i = 0; i < stack.size(); i++) {  
            sBuffer.append("|" + stack.get(i));  
            aBuffer.append("|" + maxStack.get(i));  
            iBuffer.append("|" + minStack.get(i));  
        }  
        sBuffer.append("
" + aBuffer + "
" + iBuffer + "
");  
        return sBuffer.toString();  
    }  
  
    public static void main(String[] arg) {  
        MaxStack<Integer> maxStack = new MaxStack<Integer>();  
        Random random = new Random(new Date().getTime());  
        int cur = 0;  
        for (int i = 0; i < 15; i++) {  
            cur = random.nextInt(20);  
            if (cur % 4 != 0)  
                maxStack.push(cur);  
            else  
                maxStack.pop();  
            System.out.println(maxStack);  
        }  
    }  
}  
使用上述记录栈实现的可以快速获取队列最值的队列

[java] view plaincopy
import java.util.Date;  
import java.util.Random;  
  
public class MaxQueue<E extends Comparable<E>> {  
  
    private MaxStack<E> inStack;  
    private MaxStack<E> outStack;  
  
    public MaxQueue() {  
        inStack = new MaxStack<E>();  
        outStack = new MaxStack<E>();  
    }  
  
    public boolean isEmpty() {  
        return inStack.isEmpty() && outStack.isEmpty();  
    }  
  
    public int size() {  
        return inStack.size() + outStack.size();  
    }  
  
    public E getMaxE() {  
        E in = inStack.getMaxE();  
        E out = outStack.getMaxE();  
        if (in == null && out == null)  
            return null;  
        if (in == null)  
            return out;  
        if (out == null)  
            return in;  
        return in.compareTo(out) > 0 ? in : out;  
    }  
  
    public E getMinE() {  
        E in = inStack.getMinE();  
        E out = outStack.getMinE();  
        if (in == null && out == null)  
            return null;  
        if (in == null)  
            return out;  
        if (out == null)  
            return in;  
        return in.compareTo(out) < 0 ? in : out;  
    }  
  
    private void moveFromInToOut() {  
        while (inStack.size() != 0)  
            outStack.push(inStack.pop());  
    }  
  
    public E peek() {  
        if (outStack.size() == 0 && inStack.size() == 0)  
            return null;  
        if (outStack.size() == 0)  
            moveFromInToOut();  
        return outStack.peek();  
    }  
  
    public E deQueue() {  
        if (outStack.size() == 0 && inStack.size() == 0)  
            return null;  
        if (outStack.size() == 0)  
            moveFromInToOut();  
        return outStack.pop();  
    }  
  
    public E enQueue(E e) {  
        return inStack.push(e);  
    }  
  
    public static void main(String[] arg) {  
        MaxQueue<Integer> maxQueue = new MaxQueue<Integer>();  
        Random random = new Random(new Date().getTime());  
        int cur = 0;  
        for (int i = 0; i < 15; i++) {  
            cur = random.nextInt(20);  
            if (cur % 4 != 0)  
                System.out.print(maxQueue.enQueue(cur) + "<-");  
            else  
                System.out.print("<-" + maxQueue.deQueue());  
  
            System.out.println("|Max:" + maxQueue.getMaxE() + "Min|:"  
                    + maxQueue.getMinE());  
        }  
    }  
}