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

Question

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 Count property,
// we'll use that...
static int CountQuickly<T>(IEnumerable collection)
{
    // Note: I realize this is basically what Enumerable.Count already does
    // (minus the exception); I am just including it for clarity.
    var genericColl = collection as ICollection<T>;
    if (genericColl != null)
    {
        return genericColl.Count;
    }

    var nonGenericColl = collection as ICollection;
    if (nonGenericColl != null)
    {
        return nonGenericColl.Count;
    }

    // ...or else we'll just throw an exception, since this collection
    // can't be counted quickly.
    throw new ArgumentException("Cannot count this collection quickly!");
}

Wouldn't it make more sense to just abandon the ICollection interface completely (I don't mean drop the implementation, of course, as that would be a breaking change; I just mean, stop using it), and simply implement ICollection<T> with explicit implementation for members that don't have a perfect match?

I mean, look at what ICollection<T> offers:

• Count -- Queue<T> and Stack<T> both have this.
• IsReadOnly -- Queue<T> and Stack<T> easily could have this.
• Add -- Queue<T> could implement this explicitly (with Enqueue), as could Stack<T> (with Push).
• Clear -- Check.
• Contains -- Check.
• CopyTo -- Check.
• GetEnumerator -- Check (duh).
• Remove -- This is the only one that Queue<T> and Stack<T> don't have a perfect match for.

And here's the real kicker: ICollection<T>.Remove returns a bool; so an explicit implementation for Queue<T> could totally (for example) check if the item to be removed is actually the head element (using Peek), and if so, call Dequeue and return true, otherwise return false. Stack<T> could easily be given a similar implementation with Peek and Pop.

All right, now that I've written about a thousand words on why I think this would be possible, I pose the obvious question: why didn't the designers of Queue<T> and Stack<T> implement this interface? That is, what were the design factors (which I am probably not considering) that led to the decision that this would be the wrong choice? Why was ICollection implemented instead?

I am wondering if, in designing my own types, there are any guiding principles I should consider with respect to interface implementation that I might be overlooking in asking this question. For example, is it just considered bad practice to explicitly implement interfaces that aren't fully supported in general (if so, this would seem to conflict with, e.g., List<T> implementing IList)? Is there a conceptual disconnect between the concept of a queue/stack and what ICollection<T> is meant to represent?

Basically, I sense that there must be a pretty good reason Queue<T> (for example) doesn't implement ICollection<T>, and I don't want to just go blindly forward designing my own types and implementing interfaces in an inappropriate manner without being informed and fully thinking through what I'm doing.

I do apologize for the super-long question.

Answer 1

I can't give the "what was the actual thinking" answer - perhaps one of the designers will give us the real thinkng and I can delete this.

However, putting myself in the mindset of "what if someone came to me to make this decision", I can think of an answer.. let me illustrate with this code:

public void SomeMethod<T>( ICollection<T> collection, T valueA, T valueB)
{

  collection.Add( valueA);
  collection.Add( valueB);

  if( someComplicatedCondition())
  {
    collection.Remove(valueA);
  }
}

(Sure, anyone can create a bad implementation of ICollection<T>, but we expect the framework to set the example). Let's assume Stack/Queue implement as you state in the question. So is the code above right, or does it have edge case bugs because ICollection<T>.Remove() should be checked? If valueA MUST be removed, how do I fix this to work with both Stack and Queue? There are answers, but obviously the code above is wrong in this case - even though it smells reasonable.

So both interpretations are valid, but I'm good with the decision made here - if I had the code above and knew I could be passed a Queue or Stack that I could design around it, but it sure would be an easy bug pit to fall into (everywhere you see ICollection<T>, remember the edge cases for remove!)

Answer 2

Ultimately perhaps they are just not ideal fits; if you want a list or collection - use a List<T> or Collection<T> ;p

Re Add - there is an implicit assumption that Add adds to the end of the collection, which is not true of a stack (although it is for a queue). In some ways, it actually confuses me that the enumerator for stack/queue does not dequeue/pop, since I largely expect items in a queue/stack to be fetched once each (and once only).

Maybe also (again, using my enumerator as just an example) people simply couldn't agree on exactly how it should behave in some of those scenarios, and lacking complete agreement, simply not implementing them was a better choice.

Answer 3

Philip has given a good answer (+1). There is another conceptual promise that Remove will break for Stack<T>. The ICollection<T>.Remove is documented as:

Removes the first occurrence of a specific object from the ICollection.

Stack<T> is LIFO, even if Remove was implemented, it will have to remove the last occurrence in case of duplicate objects.

If it doesnt make sense for Stack<T>, it's better avoidable for its equal and opposite cousin.

---

I would have liked it better if MS:

• didn't document Remove for ICollection<T> like that. Deleting an equal object somewhere would have made more sense considering how vastly different the internal implementations of various structures are. Forcing the removal of first item looks like influenced from linear searching of simple structures like arrays.

• had interfaces for queue structures. May be:

  public interface IPeekable<T> : IEnumerable<T> // or IInOut<T> or similar
  {
      int Count { get; }
  
      bool Contains(T item);
      T Peek();
      void Add(T item);
      bool Remove();
      void Clear();
  }