MaxWithinWindow.java allows you to query for the maximum within the last n items added.

MaxWithinWindow.java

package com.seanpont.structs;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Add items. Query which is the largest within the last n additions.
 * User: spont200
 * Date: 8/17/13
 */
public class MaxWithinWindow<T extends Comparable<T>> {

    private final int window;
    private long counter;
    protected Deque<IndexWrapper<T>> deque;

    public MaxWithinWindow(int window) {
        this.window = window;
        deque = new ArrayDeque<IndexWrapper<T>>(window);
    }

    /**
     * Add to the tail. But first remove all smaller / out of scope items
     * @param item the item to add
     */
    public void add(T item) {
        final long horizon = getHorizon();
        IndexWrapper<T> last;
        while ((last = deque.peekLast()) != null && (last.index < horizon || last.item.compareTo(item) < 0)) {
            deque.removeLast();
        }
        deque.addLast(new IndexWrapper<T>(item, counter++));
    }

    /**
     * Poll from the front, but first remove all out-of-scope items.
     * @return the max item
     */
    public T max() {
        final long horizon = getHorizon();
        IndexWrapper<T> first;
        while ((first = deque.peekFirst()) != null && first.index < horizon) {
            deque.removeFirst();
        }
        return first.item;
    }

    /**
     * items with an index lower than this number are out of scope
     * @return the horizon
     */
    private long getHorizon() {
        return counter - window;
    }

    /**
     * A tuple: the item and the index (the count when added)
     * @param <T>
     */
    static class IndexWrapper<T> {
        T item;
        long index;

        public IndexWrapper(T item, long index) {
            this.item = item;
            this.index = index;
        }

        public String toString() {
            return item.toString();
        }
    }
}