14

if Peek returns the next object in a queue, is there a method I can use to get a specific object? For example, I want to find the third object in the queue and change one of its values?

right now Im just doing a foreach through the queue which might be the best solution, but I didnt know if there was something special you can use with peek? ie Queue.Peek(2)

Leroy Jenkins
  • 2,680
  • 6
  • 25
  • 33

4 Answers4

23

If you want to access elements directly (with an O(1) operation), use an array instead of a queue because a queue has a different function (FIFO).

A random access operation on a queue will be O(n) because it needs to iterate over every element in the collection...which in turn makes it sequential access, rather than direct random access.

Then again, since you're using C#, you can use queue.ElementAt(n) from System.Linq (since Queue implements IEnumerable) but that won't be O(1) i.e. it will still iterate over the elements.

Andreas Grech
  • 105,982
  • 98
  • 297
  • 360
  • 5
    Accessing a random element in a queue implemented with a cyclic buffer, like `Queue`, is an `O(1)` operation. `Queue` even has a `GetElement(int)` method that does that, but unfortunately it's marked as `internal`. Of course one can implement their own queue class that allows random access, or use the [`CircularQueue`](https://github.com/sestoft/C5/blob/master/C5/arrays/CircularQueue.cs) class from the [C5 Generic Collection Library](http://www.itu.dk/research/c5/) which has an `O(1)` enqueue, dequeue, and item random access (and even push and pop). – Allon Guralnek Oct 07 '12 at 11:12
  • This only applies to the built-in queue class. The .NET Queue class does not expose an indexer, but obviously you can compute the index of the nth item... `function peek(n) { return _buffer[ (currentIndex + n) % _buffer.length ];` A different implementation could easily provide this functionality. – snarf Oct 10 '18 at 22:48
10

Although this is still O(n), it's certainly easier to read if you use the LINQ extention methods ElementAt() or ElementAtOrDefault(), these are extentions of IEnumerable<T>, which Queue<T> implements.

using System.Linq;

Queue<T> queue = new Queue<T>();
T result; 
result = queue.ElementAt(2);
result = queue.ElementAtOrDefault(2);

Edit If you do go with the other suggestions of converting your Queue to an array just for this operation that you need to decide if the likely sizes of your queue and the distance of the index you'll be looking for from the start of your queue justify the O(n) operation of calling .ToArray(). ElementAt(m), not to mention the space requirements of creating a secondary storage location for it.

John Pappin
  • 578
  • 3
  • 11
4

foreach through a queue. Kind of a paradox.

However, if you can foreach, it is an IEnumerable, so the usual linq extensions apply:

queue.Skip(1).FirstOrDefault()

or 

queue.ElementAt(1)
sehe
  • 374,641
  • 47
  • 450
  • 633
1

You could do something like this as a one off:

object thirdObjectInQueue = queue.ToArray()[2];

I wouldn't recommend using it a lot, however, as it copies the whole queue to an array, thereby iterating over the whole queue anyway.

Chris Wallis
  • 1,263
  • 8
  • 20