在队列中选择特定的对象（即查看+1）

Question

如果 Peek 返回队列中的下一个对象，那么有没有一种方法可以使用来获取特定的对象呢？例如，我想找到队列中的第三个对象并更改其值？

目前，我只是通过对队列进行 foreach 循环来实现这一点，这可能是最好的解决方案，但我不知道是否可以使用与 Peek 相关的特殊功能。例如 Queue.Peek(2)。

- Leroy Jenkins

Answer 1

如果你想直接访问元素(使用O(1)操作)，请使用数组而不是队列，因为队列具有不同的功能(先进先出)。

在队列上进行随机访问操作将是O(n)，因为它需要遍历集合中的每个元素...这反过来使它成为顺序访问，而不是直接随机访问。

---

不过，由于您使用C#，您可以使用System.Linq中的queue.ElementAt(n)(因为Queue实现了IEnumerable)，但这仍然不是O(1)，即它仍然需要迭代元素。

- Andreas Grech

---

使用循环缓冲实现的队列，例如Queue<T>，访问随机元素是一个O(1)操作。 Queue <T>甚至有一个GetElement（int）方法可以做到这一点，但不幸的是，它被标记为internal。当然，一个人可以实现自己的队列类以允许随机访问，或者使用C5通用集合库中的CircularQueue<T>类，它具有O(1)入队、出队和随机访问项（甚至包括推送和弹出）。 - Allon Guralnek

这仅适用于内置队列类。.NET Queue<T>类不公开索引器，但显然可以计算第n个项目的索引... function peek(n) { return _buffer[ (currentIndex + n) % _buffer.length ]; 不同的实现可以轻松提供此功能。 - snarf

Answer 2

虽然这仍然是O(n)的时间复杂度，但如果您使用LINQ扩展方法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);

编辑 如果您决定采用将队列转换为数组的其他建议来执行此操作，则需要确定您的队列的可能大小以及您要查找的索引距离队列开头的距离是否足以证明调用.ToArray()。ElementAt(m)的O(n)操作，更不用说创建它的辅助存储位置所需的空间要求了。

- John Pappin

---

@Andreas：说得好，我只是举了一个对象的例子，现在已经修改为使用泛型参数。 - John Pappin

Answer 3

遍历队列需要使用foreach，有点矛盾。

然而，如果您可以使用foreach，则它是IEnumerable类型，因此可以应用常规的linq扩展：

queue.Skip(1).FirstOrDefault()

或者

queue.ElementAt(1)

- sehe

Answer 4

你可以像这样做一次性的操作：

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

我不建议经常使用它，因为它会将整个队列复制到一个数组中，从而无论如何都要遍历整个队列。

- Chris Wallis

---

如果需要获取多个元素，这个特别有用。 - HerpDerpington

这是一个糟糕的想法，但既然你认识到了，我就不会点踩。 - johnny 5