Question: On [C#/.NET Little Wonders article for ConcurrentStack / Concurrent Queue](http://geekswithblogs.net/BlackRabbitCoder/archive/2011/02/10/c.net-little-wonders-the-concurrent-collections-1-of-3.aspx), the following is mentioned regarding the `.Count` operation on the `ConcurrentStack`:

> 
> Count takes a snapshot of the stack
>  and then counts the items. This means
>  it is a O(n) operation, if you just
>  want to check for an empty stack, call
>  IsEmpty instead which is O(1).
> 
> 
> 

I'm not greatly experienced in multi-threaded programming yet, but I understand why you can't just loop through the items on the collection and count them, because the collection may be changing by other threads at the same time. However, if you have to lock the `ConcurrentStack` long enough to make a snapshot, wouldn't it be easier just to count the items while you have it locked, return that count, and release the lock, instead of taking the overhead and time cost of generating an entire snapshot before releasing the lock?

I may be missing something basic about how this works, and I would appreciate any thoughts or insight you may have.

Answer: 
I don't know for sure, but here's a guess.

The stack could be implemented as a singly-linked list, consisting of *immutable* cells, where each cell points to the cell underneath it on the stack. Then a "snapshot" would simply be to make a copy of the top of the stack; because the cells are immutable, this pulls along the rest of the current stack as well.

Thus, the snapshot would be an O(1) operation, but counting the actual items is still O(n).
ConcurrentStack and ConcurrentQueue are thread safe collections, so no locking is involved. in ConcurrentStack for example, the count is calculated by reading the head node then traversing the list accumulation the count