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?

Genhis
  • 1,484
  • 3
  • 27
  • 29
bernie2436
  • 22,841
  • 49
  • 151
  • 244
  • Use an ArrayList as a stack. You can use get(x) when you need a specific item. – Ryan Amos Mar 09 '12 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? – dardo Mar 09 '12 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. – wkl Mar 09 '12 at 16:38

5 Answers5

19

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.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
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).

Mark Peters
  • 80,126
  • 17
  • 159
  • 190
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..!!

Ramandeep Singh
  • 5,063
  • 3
  • 28
  • 34
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

Cratylus
  • 52,998
  • 69
  • 209
  • 339
  • Just a note that getting the nth element of a `LinkedList` is equivalent to iterating through the `Queue` to the nth element. – Mark Peters Mar 09 '12 at 16:42
  • @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 – Cratylus Mar 09 '12 at 16:44
  • @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. – Mark Peters Mar 09 '12 at 16:52
  • 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. – BryanT Jan 25 '16 at 18:06
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).

Hauke Ingmar Schmidt
  • 11,559
  • 1
  • 42
  • 50