在队列中选择特定对象(即peek +1)

Question

如果Peek返回队列中的下一个对象,是否有可用于获取特定对象的方法？例如,我想在队列中找到第三个对象并更改其中一个值？

现在我只是通过队列做一个foreach,这可能是最好的解决方案,但我不知道是否有一些特殊的你可以使用peek？即Queue.Peek(2)

Answer 1

如果要直接访问元素(使用O(1)操作),请使用数组而不是队列,因为队列具有不同的功能(FIFO).

队列上的随机访问操作将是O(n)因为它需要迭代集合中的每个元素......这反过来使其成为顺序访问,而不是直接随机访问.

然后,再次,因为你正在使用C#,你可以使用queue.ElementAt(n)from System.Linq(自Queue工具IEnumerable),但不会,O(1)即它仍将迭代元素.

访问使用循环缓冲区实现的队列中的随机元素,如`Queue <T>`,是一个"O(1)"操作.`Queue <T>`甚至有一个`GetElement(int)`方法可以做到这一点,但不幸的是它被标记为`internal`.当然可以实现自己的队列类,允许随机访问,或使用[`CircularQueue <T>`](https://github.com/sestoft/C5/blob/master/C5/arrays/CircularQueue.cs)来自[C5 Generic Collection Library](http://www.itu.dk/research/c5/)的类,它具有"O(1)`入队,出队和项目随机访问(甚至推送和弹出). (5认同)

Answer 2

虽然这仍然是O(n)的,它肯定更容易阅读,如果你使用LINQ extention方法ElementAt()或者ElementAtOrDefault(),这些都是一些推广IEnumerable<T>,它Queue<T>实现了.

using System.Linq;

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

编辑如果您确实执行了将Queue转换为数组的其他建议,只需执行此操作,您需要确定队列的可能大小以及您从队列开始查找索引的距离证明调用.ToArray()的O(n)操作是正确的.ElementAt(m),更不用说为它创建二级存储位置的空间要求.