Is there an efficient way to find out whether a queue item is "before" another one?

For my Java application, I need some method that finds out if item1 is "before" item2 in my Queue Q. Of course, I can just use an iterator and start traversing the list. However, maybe there is another way of finding this out?

For my specific application, I can't use a LinkedList (which provides indexes and makes i开发者_如何学Got easy to determine if one object is before another).

No, there isn't. By definition, the only operations on a queue are enqueuing and dequeuing, so if your application requires other operations, then a queue isn't the right structure.

If you only need to find out if item2 is already in the queue, you could use a java.util.LinkedHashMap which maintains insertion order and can be used as a LIFO queue.

If knowing the order rapidly is a big concern, then consider adding an 'order' field to your element - and override your queue implementation to fill that field.

I would not consider the LinkedList 'index' as a solution. It is implemented as a list traversal.

I would keep a separate HashMap from queue objects to Integers, and a running count of the total number of objects you've ever added to the queue (so when you insert object X, the counter means that object X is the Nth object inserted). Every time you add an object to the queue, add it to the HashMap as the key; the value is the current value of the counter.

When you need to ask which of two objects is first, look them up in the HashMap and compare the ordinals. Whichever one has a lower value came first.

A Queue is a Collection, so you can always copy its elements to another Collection that lets you retrieve the order, e.g.

List<YourType> copy = new ArrayList<YourType>(yourQueue);
if(copy.indexOf(obj1)<copy.indexOf(obj2)){
    // some code here
}

Of course this is horribly inefficient, but it works. (You will probably have to synchronize the queue while doing this)

Another way would be a to do it via iterator():

/**
 * Returns -1 if a occurs in the collection before b, 1 if b occurs before a
 * and 0 otherwise.
 */
public static <T> int comparePositionInCollection(final T a,
    final T b,
    final Collection<T> collection){

    // todo: check for a==null, b==null, a.equals(b)

    final Iterator<T> iterator = collection.iterator();
    boolean foundA = false;
    boolean foundB = false;
    int result = 0;
    while(iterator.hasNext()){
        final T t = iterator.next();
        if(a.equals(t)){
            if(foundB){
                result = 1;
                break;
            }
            foundA = true;
        } else if(b.equals(t)){
            if(foundA){
                result = -1;
                break;
            }
            foundB = true;
        }
    }
    return result;
}

Of course you would have to synchronize the queue before accessing the iterator, so this is also horribly inefficient.

LinkedList is such a basic class it hard to imagine something which I could suggest as an alternative. except ArrayList which supports random access and can be much faster for indexed access. ArrayList is not as efficient as queue however.

In general, queues will offer a "peek" operation which will let you see what's at the top of the queue without removing it, but anything else requires a different data structure. Or else you pop things off the queue and onto another queue until you figure it out, at which point you need to requeue the values you popped off.

I recommend priority queue that could reference a lookup table. That way, you get constant performance for the element you want to get, and polynomial insert costs. However, this may be specialized for your uses if you're simply trying to do a comparision, rather than find the best or worst priority item. However, the constant performance is always nice. and then you're not iterating an array necessarily, but just looking up.