Why is there no queue in Cocoa?

Question

I recently found out that there is no queue built into Cocoa (Touch, in this case). Why not? A queue is one of the most fundamental data structures in computer programming.

I've seen some people suggesting the use of NSMutableArray, but this is extremely inefficient for pops/dequeues, because it requires removing the object at index 0. That will shift all of the elements down (towards the now empty entry), thus taking O(n) time for each remove operation. Am I missing something or was there just no reason that queues were not added to Cocoa?

Answer 1

Apple releases the CFTypes as OpenSource — and they are the core data types for the object orientated collections as NSArray, NSDictionary,… ("Toll-free bridging")

So if we have a look at CFArray.c we just can see by looking at the includes #include "CFStorage.h". This must be the type that sores the data for real.

ok, having a look at CFStorage.h, we find this in it's comment

CFStorage uses a balanced tree to store the values, and is most appropriate for situations where potentially a large number values (more than a hundred bytes' worth) will be stored and there will be a lot of editing (insertions and deletions).

Getting to an item is O(log n), although caching the last result often reduces this to a constant time.

ergo
The name "NS(Mutable)Array" does not describe, how it is implemented, but how it works on a higher level. And the implementation is much more sophisticated, than just a list, that an array would imply.

note
We don't know, if apple is changing the CFTypes when entering the closed source, so not all things might be explainable by looking at the CFTypes sources.

some numbers and charts: http://ridiculousfish.com/blog/posts/array.html

Answer 2

I've seen some people suggesting the use of NSMutableArray, but this is extremely inefficient for pops/dequeues, because it requires removing the object at index 0. That will shift all of the elements down (towards the now empty entry), thus taking O(n) time for each remove operation.

This is incorrect. NSMutableArray handles head insertion very efficiently and can be used for a number of different data structures, including queues and stacks.