Why do Queue(T) and Stack(T) not implement ICollection(T)?

Before I even ask, let me get the obvious answer out of the way: The ICollection<T> interface includes a Remove method to remove an arbitrary element, which Queue<T> and Stack<T> can't really support (since they can only remove "end" elements).

OK, I realize that. Actually, my question is not specifically about the Queue<T> or Stack<T> collection types; rather, it's about the design decision of not implementing ICollection<T> for any generic type that is essentially a collection of T values.

Here's what I find odd. Say I have a method that accepts an arbitrary collection of T, and for the purpose of the code I'm writing it would be useful to know the size of the collection. For example (the below code is trivial, for illustration only!):

// Argument validation omitted for brevity.
static IEnumerable<T> FirstHalf<T>(this ICollection<T> source)
{
    int i = 0;
    foreach (T item in source)
    {
        yield return item;
        if ((++i) >= (source.Count / 2))
        {
            break;
        }
    }
}

Now, there's really no reason why this code couldn't operate on a Queue<T> or a Stack<T>, except that those types don't implement ICollection<T>. They do implement ICollection, of course—I'm guessing mainly for the Count property alone—but that leads to weird optimization code like this:

// OK, so to accommodate those bastard Queue<T> and Stack<T> types,
// we will just accept any IEnumerable<T>...
static IEnumerable<T> FirstHalf<T>(this IEnumerable<T> source)
{
    int count = CountQuickly<T>(source);
    /* ... */
}

// Then, assuming we've got a collection type with a Cou