Queue vs List

问题:

I'm currently using a List<T> as a queue (use lst[0] then lst.removeAt(0)) to hold objects. There's about 20 items max at a given time. I realized there was an actual Queue<T> class. I'm wondering if there's any benefit (performance, memory, etc.) to using a Queue<T> over a List<T> acting like a queue?

回答1:

Performance can be profiled. Though in this case of so few items, you may need to run the code millions of times to actually get worthwhile differences.

I will say this: Queue<T> will expose your intent more explicitly, people know how a queue works.

A list being used like a queue is not as clear, especially if you have a lot of needless indexing and RemoveAt(magicNumber) code. Dequeue is a lot more consumable from a code maintenance point of view.

If this then gives you measurable performance issues, you can address it. Don't address every potential performance issue upfront.

回答2:

Short answer:
Queue<T> is faster than List<T> when it's used like a queue. List<T> is faster than Queue<T> when used like a list.

Long answer:
A Queue<T> is faster for dequeuing operation, which is an O(1) operation. The entire block of subsequent items of the array is not moved up. This is possible because a Queue<T> need not facilitate removal from random positions, but only from the top. So it maintains a head (from which the item is pulled upon Dequeue) and tail position (to which the item is added upon Enqueue). On the other hand removing from the top of a List<T> requires itself to shift positions of every subsequent item one up. This is O(n) - worst case if you're removing from the top, which is what a dequeue operation is. The speed advantage can be noticeable if you're dequeuing in a loop.

A List<T> is more performant if you need indexed access, random retrieval etc. A Queue<T> will have to enumerate fully to find the appropriate index position (it doesn't expose IList<T>).

That said, a Stack<T> vs List<T> is much closer, there is no performance difference in pushing and popping operations. They both push to end and remove from end of array structures (both of which are O(1)).

---

Of course you should use the correct structure that reveals the intent. In most cases they will perform better as well since they are tailor-made for the purpose. I believe had there been no performance difference at all, Microsoft wouldn't have included Queue<T> and Stack<T> in the framework for merely different semantics. It would have been simply easily extensible if that was the case. Think about SortedDictionary<K, V> and SortedList<K, V>, both of which do exactly the same but is differentiated by only performance characteristic; they find a place in BCL.

回答3:

Besides the fact that the Queue<T> class implements a queue and the List<T> class implement a list there is a performance difference.

Every time you remove the first element from List<T> all elements in the queue are copied. With only 20 elements in the queue it may not be noticeable. However, when you dequeue the next element from Queue<T> no such copying is happening and that will always be faster. If the queue is long the difference can be significant.

回答4:

I wanted to emphasize what HugoRune already pointed out. Queue is significantly faster than List, where memory accesses are 1 vs. n for List in this use case. I have a similar use case but I have hundreds of values and I will use Queue because it is an order of magnitude faster.

A note about Queue being implemented on top of List: the key word is "implemented". It doesn't copy every value to a new memory location upon dequeue, rather using a circular buffer. This can be done on "top of List" without the penalties of copies that direct usage of List implies.