7

I have a number of queues and priority queues in my application. I would like to easily access the nth items in these queues, but don't see an easy way to do that using the API.

I guess I could create an Iterator and iterate to the nth element or use toArray()[index], but it seems like there should be an easier way.

Am I missing something?

Improve this question
3
  • Use an ArrayList as a stack. You can use get(x) when you need a specific item. Commented Mar 9, 2012 at 16:37
  • 1
    Doesn't that go against the idea of a queue? Queues are supposed to be FIFO structures, not on demand access like maps or arrays. Is there a reason you're using a Queue over something like a List? Commented Mar 9, 2012 at 16:38
  • The Queue interface doesn't expose direct element access to its elements, only to the front, and access via iterators. For your use you probably want a List-based collection. Commented Mar 9, 2012 at 16:38

5 Answers 5

Reset to default
20

Am I missing something?

Yes - the fact that accessing elements by index is not part of the concept of a queue.

If you need to access elements by index, you want a list, not a qeue.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

The simplest solution for you is to use a binary search tree that is self-balancing, e.g. AVL tree, splay tree or red-black tree. It allows you to access elements by their key in O(log n) time and iterate through the objects in their order in O(log n + k) where k is the number of elements iterated..!!

Improve this answer

2 Comments

Any of these options is overkill IMO.
An array-based queue or list will give you O(1). And a very fast O(1), at that.
2

The entire point of a queue is to expose access only to the head (the first element). If you want arbitrary access to elements in a linear data structure, use a List (if you're doing a lot more lookups than push/pops, consider using an ArrayList as LinkedLists are not optimized for random access).

Improve this answer

2 Comments

LinkedList implements Queue, ArrayList doesn't.
@his: The point of my answer was that he shouldn't be using the Queue ADT since it doesn't support random access, but he should be using List (which both implement). So I don't see the relevance.
1

I have a number of queues and priority queues in my application

What concrete data type are you using for Queues? A LinkedList?In this case you should be able to get the nth element by casting back to linked list.

But this is not how you would use a Queue

As for the priority queue, from you question it seems that you are also not using the correct data structures.

Priority Queue will always return the min element (by ordering).
So what do you mean the n element here?The n smallest or the n inserted or what? So we can't really say what to do in this case

Improve this answer

4 Comments

Just a note that getting the nth element of a LinkedList is equivalent to iterating through the Queue to the nth element.
@MarkPeters:You are right, but this is not the proper use of a Queue and it is awkward to see this in code.So it would be best to use e.g. as LinkedList directly because it reflects what you are trying to do better
@user: I would agree that just using a List is better, but iterating over a Queue is in my mind better than casting back to a LinkedList because that is coupling yourself to an implementation detail. If the OP has the ability to change the code providing the Queue I agree completely.
I have an application where I believe I can justify using a queue and still need access to an item in the queue. I am recording clock time every time a button is pressed and pushing an object (contains time and other attributes - yet to be assigned) onto the queue. They appear in a List View. The user can assign the attributes to them and dismiss them (pop them off the queue) from the top, to be saved. The Queue is exactly what I need to push and pop them, and I only have five or six lines of code, in one place, to re-find a Queue item.
1

Queues don't allow random, indexed access by concept so it is a good thing that the interface does not allow this either. If you need both kinds of access at the same time (which is a bad sign for design) then you could use a datatype that implements both List and Queue (e.g. LinkedList).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.